[자료구조] 수학적 귀납법 증명

 

 

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다.

다들 아는 일반적인 수학적 귀납법 설명하려고 이글 쓰는것이 아닙니다. 사실 귀납법 자체는 고등학교만 정상적으로 나왔으면 다 아는내용이다. 문제는 다음 2가지 측면에서 교수님의 가르침에 큰 놀라움을 얻었기에 이를 공유하고자 글을 써본 것 이다.

 

1) P(n-1)을 왜 참이라고 가정하는가? 참인지는 어찌알지??

2) 귀납법을 통해 재귀함수를 어떻게 인식해야 하는가?

 

수학적 귀납법

● 수학적 귀납법의 기본형

(1) Base: P(1)이 참이고

(2) Step: P(n-1) -> p(n) 이 참이라면

(3) Result: P(n)은 모든 자연수 n에 대해서 참이다.

 

Base와 Step을 각각 따로 증명해서 나중에 합치면 Result가 나오는 구성이다.

 

예제

● 모든 자연수 n에 대하여 다음이 성립함을 귀납법으로 증명해 보자.

$1\ +\ 2\ + ...\ +\ n\ =\ \frac{n\left(n+1\right)}{2}$

 

(1) Base: n 이 1인경우 위의 식에 1을 대입해보면 1 = 1(2)/2 가 되니 참이다.

(2) Step: P(n-1) -> p(n)을 증명해야한다. 일단 잠시 P(n-1)이 참이라고 가정하자.

즉, 1 + 2 + ... n-1 = n(n - 1)/2 가 참이라고 믿어보자.

 

이후 양 변에 n을 똑같이 더해준다.

1 + 2 + ... n-1 + n = n(n - 1)/2 + n = n(n + 1)/2 또한 참이된다.

 

따라서 P(n-1) -> p(n) 또한 참으로 증명되었다.

 

(3) Result: base와 step이 둘다 증명되었기 때문에 P(n)은 모든 자연수 n에 대해서 참이다.

 

(4) But !!: 아니 근데 P(n-1)이 참인지는 어떻게 알고 가정한 것 일까? 모르지 않나? 우리 맘대로 가정했으니 말이다.

이부분은 고등학교때 배울때도 항상 증명이 복잡하기때문에 그냥 넘어갔었고, 나또한 그냥 믿고 끝냈다.

 

여기서 P이면 Q이다의 명제가 활용된다.

가정 P가 참이고, 결론Q가 참이면 전체는 참이된다. P가 참이고, Q가 거짓이면 전체는 거짓이 된다. 여기까지는 당연하다.

문제는 파란박스 안의 2문장이 한눈에 들어오지 않는다.

 

● P가 거짓이고, Q가 참이면 -> 전체는 참이된다 ???

● P가 거짓이고, Q가 거짓이면 -> 전체는 참이된다 ???

 

위의 2 문장이 처음보면 이해가지 않는다. 아니 조건 부터 거짓인 문장이 어째서 참이된다는 말인가??

좀더 이해하기 쉽게 실생활의 예를 살펴보자

 

ex) 100점 받으면 에어팟 사준다. 라는 문장이 있다고 해보자.

여기서 P는 100점 받으면 이고 Q는 에어팟 사준다 이다.

P(100점 받으면)	Q(에어팟 사준다)	약속(전체문장)
O	O	O
O	X	X
X	X	O
X	O	O

3번째 행을보자. 100점을 받지 못했다고 가정하고있다. 이때 에어팟을 안사주면 약속을 어긴 것 일까?

아니다 약속을 지킨것 이다. 전체 문장이 참이된다.

 

4번째 행을보자. 100점을 받지 못했다고 가정하고있다. 이때 에어팟을 사줬다면 약속을 어긴 것 일까? 아니다 100점 못받았다고해서 에어팟을 사주면 안된다는 조건은 없었다. 이분법적으로 약속을 어긴것이 아니니까 지킨것 이다. 따라서 참이다.

 

결론: P(가정)가 거짓이면 "P이면 Q이다"는 논의할 의미가 없는 문장이 되버린다. 하지만 참인 문장이다.

 

(5) P(n-1) -> P(n) 이다:

위의 문장에서 P(n-1)이 False 라면 이 문장은 의논할 의미가 없지만 자동으로 True가 된다.

만약 P(n-1)이 True 라면 논의할수가 있다.

 

자 이제 다시 원래의 의문이였던 P(n-1)이 참인지는 어떻게 아는가? 로 돌아와 보자.

step을 증명할 당시에 P(n-1)이 참이라고 가정하자고 했는데, 이는 P(n-1)이 사실인 경우 말고는 의논할 여지가 없어지기 때문이다.

만약 P(n-1)이 거짓이면 자동으로 참인 문장이 되니 논의할 의미가 없다.

따라서 P(n-1)이 참인 경우에 대해서만 논의해야하며, 이를 참이라 믿는것은 당연해야 한다.

 

겉보기에는 그냥 True라고 믿는 것 처럼 보이지만, 실상은 그렇게만 믿어야하는! 이것 말고는 의논할 여지가 없기에 당연한 믿음이다.

 

 

총합을 구하는 재귀 함수

위의 수학적 귀납법을 통해서 재귀 함수를 바라보는 시각이 바뀌었다. 이부분이 진짜 충격이였다.

int sum(int x){
	if (x == 0) return 0;
	return x + sum(x-1);
}

 

위의 총합을 구하는 함수는 사실 너무 간단해서 어떻게 생각해도 상관없지만 위의 식이 복잡한 함수라 생각하고 다음을 읽어달라.

 

보통 재귀 함수를 보면 그 다음단계로 호출하는 과정을 생각하며 굴파면서 게속 들어가기 마련이다. 다음처럼 말이다.

물론 이글을 읽어주시는 분이 이렇게 생각하지 않았다면 어쩔수 없지만, 나를 포함한 일반인들은 재귀함수의 설명을 위와같이 들었거나 혹은 생각한적이 많을 것 이다.

 

결론 부터 말하면 재귀호출이 그냥 정답을 return 한다고 믿으면 된다.

 

이를 귀납법으로 증명해보자. Sum(x)는 항상 1 + 2 + .. + X 를 return 함을 증명해야한다.

 

(1) Base: P(1)이 참인지 확인해야한다. 실제 함수에 1을 대입해보면 1을 반환한다. 따라서 참이다.

 

(2) Step: P(n-1) -> p(n) 이 참이지 확인해야한다.

위에서 했듯 P(n-1)이 참이라 가정하자. 즉! Sum(x-1)이 1 + 2 + ... + (X-1)을 return 한다고 믿어보자(사실은 당연한 믿음).

이를 믿은후 Sum(X)의 코드를 보면 X + Sum(X-1)을 return한다. Sum(X-1)은 1 + 2 + ... + (X-1)을 반환한다고 믿었으니 여기에 X를 더하면 Sum(x)는 1 + 2 + ... + (X-1) + X 를 반환함을 알수있다.

 

(3) Result: 따라서 P(n)은 모든 자연수 n에 대해서 참이다.

 

느낀점이 있는가??

위의 증명에서 P(n-1)이 결과를 반환한다고 믿었다. 이는 당연한 믿음이기 때문이다. 여기서 배울점이 있다. 다시 함수보자.

int sum(int x){
	if (x == 0) return 0;
	return x + sum(x-1);
}

 

아직도 Sum(X-1)을 보고 굴파듯 끝까지 내려가는가?? 아니다 시각을 바꿔야 한다. sum(X-1)이 합을 return한다고 믿으면 된다.

호출과정을 생각할 필요가 없다!. 그냥 믿으면 결과가 나온다!

 

결론: 재귀호출이 그냥 정답을 return 한다고 믿으면 된다.