수학적 귀납법 — 도미노처럼 모든 자연수 명제를 증명하는 법

수학적 귀납법은 '모든 자연수에서 성립한다'는 명제를 증명하는 강력한 방법입니다. 자연수는 무한히 많은데, 하나하나 확인할 수는 없죠. 귀납법은 이 무한을 단 두 단계로 정복합니다 — 마치 도미노를 쓰러뜨리듯이. 이 글은 귀납법의 두 단계가 무엇이고 왜 그것으로 충분한지, 그리고 수열의 합 공식 증명을 예제로 정리합니다. 대수 '수열'을 배우는 고2에게 맞습니다.

수학적 귀납법이란 무엇인가?

모든 자연수 n에 대한 명제 p(n)이 참임을 보이려면, 다음 두 단계만 증명하면 됩니다.

1단계 (기초): n = 1일 때 p(1)이 참이다. 2단계 (귀납): n = k일 때 p(k)가 참이라고 가정하면, n = k+1일 때 p(k+1)도 참이다.

이 두 가지가 모두 성립하면 모든 자연수 n에서 p(n)이 참입니다.

왜 두 단계만으로 충분한가?

도미노로 생각하면 명확합니다. 도미노가 전부 넘어지려면 두 가지가 필요합니다.

1. 첫 도미노가 넘어진다 (1단계: n=1 성립)
2. 어떤 도미노가 넘어지면 바로 다음 것도 넘어진다 (2단계: k→k+1)

이 둘이 보장되면, 첫 도미노가 넘어지고 → 두 번째도 → 세 번째도 → … 끝없이 이어집니다. 그래서 개별 확인 없이도 모든 자연수에서 참임이 보장됩니다.

핵심은 2단계의 귀납 가정입니다. "n=k일 때 참"이라고 가정하는 것은 결론을 미리 인정하는 반칙이 아닙니다. 'k에서 참이라면 k+1에서도 참'이라는 연결 고리를 만드는 것이지, k에서 참임을 확정하는 게 아니니까요. 이 고리 하나만 있으면 1단계의 출발점부터 도미노가 굴러갑니다.

예제: 합 공식 증명

[예제] 모든 자연수 n에 대해 1 + 2 + 3 + … + n = n(n+1)/2 임을 증명하시오.

풀이

1단계 (n=1): 좌변 = 1, 우변 = 1(1+1)/2 = 2/2 = 1. 좌변 = 우변이므로 참. ✓

2단계: n=k일 때 1+2+…+k = k(k+1)/2 라고 가정한다. 이때 n=k+1도 참임을 보인다.

• 좌변(n=k+1) = (1+2+…+k) + (k+1)
• 귀납 가정 대입 = k(k+1)/2 + (k+1)
• = (k+1)[k/2 + 1] = (k+1)(k+2)/2
• 이는 n=k+1을 공식에 넣은 값 (k+1)(k+1+1)/2 = (k+1)(k+2)/2 와 일치. ✓

검산(k=7): k(k+1)/2 + (k+1) = 7·8/2 + 8 = 28 + 8 = 36, 그리고 (k+1)(k+2)/2 = 8·9/2 = 36 — 일치합니다. ✓

두 단계가 모두 성립하므로, 모든 자연수 n에서 공식이 참이다.

어디서 자주 막히나 — 개념 점검

흔한 오해 3가지

1. "n=k일 때 참이라고 가정하면 순환논법 아닌가?" — 아닙니다. 가정은 'k에서 참이면 k+1에서도 참'이라는 함의를 만들 뿐입니다. k에서 참임을 결론으로 쓰는 게 아니라, 다음으로 넘기는 발판으로 씁니다.
2. "1단계는 당연하니 생략해도 된다" — 1단계가 없으면 도미노의 시작이 없습니다. 2단계만 있으면 '넘어지면 다음도 넘어진다'는 연결만 있고, 정작 처음 넘어지는 도미노가 없어 아무것도 증명되지 않습니다.
3. "귀납법은 몇 개 확인하고 규칙을 추측하는 것" — 그건 '추측'이지 증명이 아닙니다. 수학적 귀납법은 두 단계로 모든 자연수를 엄밀히 증명합니다. 이름의 '귀납'과 논리학의 귀납추론은 다릅니다.

한 줄로 남기는 핵심

수학적 귀납법은 "첫 도미노를 쓰러뜨리고(1단계), 넘어지면 다음도 넘어짐을 보이면(2단계) 전부 넘어진다"는 원리입니다.

무한히 많은 자연수를 하나씩 확인할 수 없을 때, 귀납법은 '출발'과 '연결' 두 가지만으로 무한을 정복한다.

이 방법은 수열의 합 공식이 참임을 뒷받침하고, 부등식·배수 명제 등 자연수에 관한 온갖 증명으로 확장됩니다. TimeLevelUp은 증명처럼 '논리의 순서'가 곧 실력인 단원을 단계별로 배치하고, 1단계 누락 같은 전형적 실수를 복습 계획에 반영해 증명 습관이 몸에 배도록 설계합니다.