귀납 단계가 맞아도 시작 명제가 거짓이면 증명은 끝나지 않는다

귀납 단계가 맞아도 시작 명제가 거짓이면 증명은 끝나지 않는다

평면 위에 놓인 흰 도미노 조각들의 근접 모습

사진: Dietmar Rabich · CC BY-SA 4.0 · 원본 출처

2n≥n+3(n=1,2,3,…)2^n\ge n+3\qquad(n=1,2,3,\ldots)

n=k에서 참이라고 가정하면 2ᵏ⁺¹≥2k+6≥k+4다. 이 전달 계산만으로 모든 양의 정수에서 증명했다고 할 수 있을까?

n=1에서는 2<4, n=2에서는 4<5라서 원래 주장은 거짓이다. 귀납 단계는 앞 명제가 참이라는 가정 아래 다음 명제를 보장한다. 시작의 참을 대신하지 못한다.

n=3에서는 8≥6이 참이다. k≥3에서

2k+1≥2(k+3)=2k+6≥k+42^{k+1}\ge2(k+3)=2k+6\ge k+4

이므로 n≥3에서는 성립한다. 마지막 부등식의 차는 k+2로 0 이상이다.

학생의 귀납 계산을 모두 지우지 않고 ‘주장 범위가 어디부터인가’를 고치게 하자. n=1,2의 반례, n=3의 시작 확인, k에서 k+1로의 전달을 각각 기록하면 맞는 계산이 어느 범위의 결론을 주는지 드러난다.

출처·착안: Lin McMullin, 「Good Question 14」. 문항과 풀이는 새로 작성했다.