6강. 수학적 귀납법과 재귀

'모든 자연수 n에 대해 ~이다'를 어떻게 증명할까요? 예를 몇 개 확인해서는 끝까지 증명할 수 없습니다. 수학적 귀납법은 첫 경우와 '한 경우에서 다음 경우로 넘어가는 규칙'만 보이면 무한히 많은 경우를 한꺼번에 증명하는 방법입니다. 고등학교에서 본 귀납법을 강한 귀납법과 재귀적 정의까지 넓힙니다.

자연수 전체에 대한 명제 $\forall n\, P(n)$은 반례를 하나씩 확인해서는 끝까지 증명할 수 없습니다(3강의 $n^2 + n + 41$ 예). 수학적 귀납법은 무한히 많은 경우를 두 단계로 끝내는 방법입니다.

6.1 귀납법

정리 6.1 (수학적 귀납법). 자연수에 대한 명제 $P(n)$에 대해

1. (기초 단계) $P(n_0)$이 참이고
2. (귀납 단계) 모든 $k \ge n_0$에 대해 $P(k) \to P(k+1)$이 참이면

$n \ge n_0$인 모든 $n$에 대해 $P(n)$이 참입니다.

도미노에 비유합니다: 첫 도미노가 넘어지고, 어느 도미노든 넘어지면 다음 것을 넘어뜨린다면, 모두 넘어집니다. 귀납 단계에서 가정하는 $P(k)$를 귀납 가정(induction hypothesis)이라 합니다. 귀납 가정은 “모든 $k$에서 $P(k)$가 참”이라는 뜻이 아니라, 임의의 하나의 $k$에서 참이라고 놓고 $P(k+1)$을 끌어내는 것입니다.

6.2 합 공식

정리 6.2. 모든 $n \ge 1$에 대해 $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.

증명. 기초: $n = 1$이면 양변이 1입니다. 귀납: $1 + \cdots + k = k(k+1)/2$라 가정하면

이므로 $P(k+1)$이 참입니다. □

정리 6.3. $1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$.

증명. 기초 $n = 1$: $1 = 1 \cdot 2 \cdot 3/6$. 귀납: 가정에 $(k+1)^2$을 더하면 $\frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)(2k^2 + 7k + 6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$입니다. □

정리 6.4 (등비수열의 합). $r \ne 1$이면 $1 + r + \cdots + r^n = \dfrac{r^{n+1} - 1}{r - 1}$.

6.3 부등식과 나누어떨어짐

정리 6.5. $n \ge 4$이면 $2^n < n!$.

증명. 기초 $n = 4$: $16 < 24$. 귀납: $2^k < k!$이면 $2^{k+1} = 2 \cdot 2^k < 2 \cdot k! < (k+1) \cdot k! = (k+1)!$입니다($k \ge 4$이므로 $2 < k+1$). □

기초 단계가 $n_0 = 4$인 것에 주의합니다. $n = 1, 2, 3$에서는 부등식이 거짓입니다.

정리 6.6. 모든 $n \ge 0$에 대해 $3 \mid n^3 + 2n$.

증명. 기초: $0$. 귀납: $(k+1)^3 + 2(k+1) = (k^3 + 2k) + 3(k^2 + k + 1)$이고, 첫 항은 귀납 가정으로 3의 배수, 둘째 항도 3의 배수입니다. □

6.4 강한 귀납법

귀납 단계에서 $P(k)$ 하나만이 아니라 $P(n_0), \dots, P(k)$를 모두 가정해도 됩니다.

정리 6.7 (강한 귀납법). $P(n_0)$이 참이고, 모든 $k \ge n_0$에 대해 “$P(n_0) \land \cdots \land P(k)$이면 $P(k+1)$”이면, $n \ge n_0$인 모든 $n$에서 $P(n)$이 참입니다.

정리 6.8. 2 이상의 모든 정수는 소수들의 곱으로 쓸 수 있습니다.

증명. $n = 2$는 소수입니다. $2, \dots, k$가 모두 소수의 곱이라 가정합시다. $k+1$이 소수이면 끝입니다. 아니면 $k + 1 = ab$($2 \le a, b \le k$)이고, 귀납 가정으로 $a$와 $b$가 소수의 곱이므로 $k+1$도 그렇습니다. □

여기서는 $k+1$의 약수 $a$, $b$가 $k$보다 훨씬 작을 수 있으므로 $P(k)$ 하나로는 부족합니다.

6.5 재귀적 정의

수열이나 집합을 “처음 것”과 “앞의 것에서 다음 것을 만드는 규칙”으로 정의하는 것을 재귀적 정의(recursive definition)라 합니다.

정의 6.9 (피보나치 수). $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$ ($n \ge 2$).

처음 몇 항은 $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$입니다. 재귀로 정의한 대상의 성질은 자연스럽게 귀납법으로 증명합니다.

정리 6.10. $F_1 + F_2 + \cdots + F_n = F_{n+2} - 1$.

증명. 기초 $n = 1$: $1 = F_3 - 1 = 2 - 1$. 귀납: 가정에 $F_{k+1}$을 더하면 $F_{k+2} - 1 + F_{k+1} = F_{k+3} - 1$입니다. □

정리 6.11. $F_n < 2^n$ ($n \ge 0$).

증명. 강한 귀납법: $F_0 = 0 < 1$, $F_1 = 1 < 2$. $n \ge 2$에서 $F_n = F_{n-1} + F_{n-2} < 2^{n-1} + 2^{n-2} < 2^n$. □

닫힌 꼴 $F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$($\varphi = \frac{1 + \sqrt{5}}{2}$, $\psi = \frac{1 - \sqrt{5}}{2}$)은 9강에서 점화식을 풀어 구합니다.

6.6 정렬 원리

정리 6.12 (정렬 원리). 공집합이 아닌 자연수의 집합에는 가장 작은 원소가 있습니다.

정렬 원리는 귀납법과 동치이고, “가장 작은 반례”를 잡아 모순을 끌어내는 증명에 씁니다. 예를 들어 정리 6.8은 “소수의 곱으로 쓸 수 없는 가장 작은 수 $m$”을 잡으면, $m$이 소수가 아니므로 $m = ab$이고 $a, b < m$은 소수의 곱이 되어 모순이라고 증명할 수도 있습니다.

쓰이는 곳. 알고리즘의 정확성 증명(반복문 불변식), 재귀 함수의 분석, 재귀 신경망의 정의, 프로그래밍 언어의 재귀적 자료구조가 귀납법과 재귀를 씁니다.

6.7 이 장의 요약

• 귀납법 = 기초 단계 + 귀납 단계. 기초 단계의 시작값을 확인합니다.
• 뒤의 경우가 훨씬 앞의 경우에 기대면 강한 귀납법을 씁니다.
• 재귀로 정의한 대상은 귀납법으로 다룹니다.

문제

5050

2870

4

55
610
6765

143