05편에서 수학적 귀납법의 기본형(단순 귀납법)과 강한 귀납법의 정의, 그리고 대표적인 오개념(귀납적 가정을 빠뜨리는 실수 등)을 다뤘다. 이 편은 그 도구를 실제로 어디에 어떻게 적용하는지에 집중한다. 독학사 시험에서 귀납법은 단독 문제로도 나오지만, 0913편의 조합·점화식, 1415편의 그래프·트리 문제 안에 “왜 그런지 증명하라”는 형태로 숨어서 나오는 경우가 더 많다. 이 편에서 그 결합 지점을 정면으로 다룬다.

강한 귀납법 다시 보기: 소인수분해의 존재성

쉽게 말하면: 강한 귀납법은 “바로 이전 하나”가 아니라 “그 이전 모든 경우”가 참이라고 가정해도 되는 귀납법이다.

05편에서 정리했듯, 단순 귀납법(simple induction)은 $n=k$일 때 참이라는 가정만으로 $n=k+1$을 보이는 방식이고, 강한 귀납법(strong induction)은 $n \le k$인 모든 경우가 참이라는 가정을 써도 되는 방식이다. 어떤 명제는 바로 이전 하나만으로는 다음 단계를 보일 수 없고, 그보다 더 앞의 값이 필요해서 강한 귀납법이 꼭 필요하다.

명제. 2 이상인 모든 정수는 소수(prime, 1과 자기 자신 외에 약수가 없는 2 이상의 정수)이거나, 소수들의 곱으로 나타낼 수 있다.

증명(강한 귀납법, 서술형 답안 형식).

1. 기저 단계. $n=2$는 소수이므로 명제가 성립한다.
2. 귀납 가정. $2 \le m < k$인 모든 정수 $m$에 대해 명제가 성립한다고 가정하자(즉 $m$이 소수이거나 소수들의 곱으로 나타난다).
3. 귀납 단계. $n=k$를 생각하자. $k$가 소수이면 그 자체로 명제가 성립한다. $k$가 소수가 아니라면, 정의에 따라 $k = a \cdot b$ ($2 \le a, b < k$)로 쓸 수 있다. $a$와 $b$는 모두 $k$보다 작고 2 이상이므로 귀납 가정을 그대로 적용할 수 있다 — $a$는 소수이거나 소수들의 곱, $b$도 소수이거나 소수들의 곱이다. 따라서 $k = a \cdot b$도 소수들의 곱으로 나타난다.
4. 결론. 수학적 귀납법에 의해 2 이상인 모든 정수에 대해 명제가 성립한다. $\blacksquare$

왜 강한 귀납법이 필요한가. 3단계에서 $k=a \cdot b$로 쪼갤 때 $a$, $b$는 $k-1$이 아니라 $k$보다 작은 임의의 값이 될 수 있다. 만약 단순 귀납법처럼 “$k-1$일 때만 참”이라는 가정만 있었다면 $a$나 $b$가 $k-1$이 아닌 이상 그 가정을 쓸 수 없다. 강한 귀납법은 $k$보다 작은 모든 값에 대한 가정을 허용하므로 이런 쪼개기 논증이 가능해진다.

작은 예로 검산. $k=12$라 하자. $12 = 3 \times 4$로 쪼갤 수 있다. $3$은 소수이고, $4 = 2\times 2$는 소수들의 곱이므로(귀납 가정에 의해 $4$까지는 이미 참이라고 가정), $12 = 3 \times 2 \times 2$로 소수들의 곱임이 확인된다(검산 완료).

구조적 귀납법: 재귀적으로 정의된 대상 위에서

쉽게 말하면: 구조적 귀납법은 정수 $n$이 아니라 “재귀적으로 만들어지는 대상”(트리, 논리식 등) 위에서 진행하는 귀납법이다.

구조적 귀납법(structural induction)은 대상이 자연수처럼 순서대로 나열되지 않고, 재귀적 정의(recursive definition, 기본 형태와 그것을 조합해 더 큰 형태를 만드는 규칙으로 이루어진 정의)를 따를 때 쓴다. 증명의 틀은 강한 귀납법과 비슷하지만, “$n=k$일 때”가 아니라 “재귀 정의의 기본 경우”와 “재귀 규칙으로 더 큰 대상을 만드는 경우”로 나눈다.

정의(재귀적). 정이진트리(full binary tree, 모든 내부 노드가 정확히 2개의 자식을 갖는 이진트리)를 다음과 같이 재귀적으로 정의한다.

• 기본 경우: 노드 하나로만 이루어진 트리는 정이진트리다(이 노드는 잎(leaf, 자식이 없는 노드)이다).
• 재귀 규칙: $T_1$, $T_2$가 정이진트리이면, 새 루트 노드에 $T_1$, $T_2$를 각각 왼쪽·오른쪽 자식으로 붙인 트리도 정이진트리다.

명제. 정이진트리에서 내부 노드(internal node, 자식을 가진 노드)의 개수를 $i$, 잎의 개수를 $l$이라 하면 항상 $l = i+1$이다.

증명(구조적 귀납법, 서술형 답안 형식).

1. 기저 단계. 노드 하나짜리 트리는 내부 노드가 0개($i=0$), 잎이 1개($l=1$)다. $l=i+1$, 즉 $1=0+1$이 성립한다.
2. 귀납 가정. 정이진트리 $T_1$이 내부 노드 $i_1$개, 잎 $l_1$개를 가지고 $l_1=i_1+1$을 만족하며, 정이진트리 $T_2$가 내부 노드 $i_2$개, 잎 $l_2$개를 가지고 $l_2=i_2+1$을 만족한다고 가정하자.
3. 귀납 단계. $T_1$, $T_2$를 새 루트에 붙여 만든 트리 $T$를 생각하자. $T$의 내부 노드 수는 $T_1$의 내부 노드, $T_2$의 내부 노드에 새로 생긴 루트를 더한 것이므로 $i = i_1+i_2+1$이다. $T$의 잎 수는 $T_1$의 잎과 $T_2$의 잎을 그대로 합친 것이므로(루트는 자식이 있으니 잎이 아니다) $l = l_1+l_2$다. 귀납 가정을 대입하면

한편 $i+1 = (i_1+i_2+1)+1 = i_1+i_2+2$이므로 $l = i+1$이 성립한다.

4. 결론. 구조적 귀납법에 의해 모든 정이진트리에서 $l=i+1$이 성립한다. $\blacksquare$

작은 예로 검산. 루트에 잎 2개를 붙인 가장 작은 “진짜” 정이진트리를 보면 내부 노드는 루트 1개($i=1$), 잎은 2개($l=2$)다. $l=i+1$, 즉 $2=1+1$이 맞다(검산 완료). 이 트리는 15편에서 다룬 트리의 “정점 수 = 간선 수 + 1” 성질과도 통한다 — 노드 수는 $i+l = 1+2=3$개, 트리이므로 간선 수는 노드 수 $-1=2$개다.

점화식의 닫힌해를 귀납법으로 증명하기

쉽게 말하면: 13편에서 특성방정식으로 구한 공식이 정말 맞는지, 귀납법으로 다시 한번 확인할 수 있다.

13편에서 점화식 $a_n = 2a_{n-1}+1$ ($a_1=1$)의 닫힌해(closed form, 재귀 없이 $n$만으로 바로 값을 구하는 식)를 특성방정식으로 구하면 $a_n = 2^n - 1$이 나온다. 이 결과가 맞는지 귀납법으로 검증해보자.

증명(단순 귀납법, 서술형 답안 형식).

1. 기저 단계. $n=1$일 때 공식은 $a_1 = 2^1-1 = 1$이고, 실제 초기조건도 $a_1=1$이므로 일치한다.
2. 귀납 가정. $a_k = 2^k - 1$이 성립한다고 가정하자.
3. 귀납 단계. 점화식 정의에 따라 $a_{k+1} = 2a_k+1$이다. 귀납 가정을 대입하면

이는 $n=k+1$일 때의 공식 $2^{k+1}-1$과 정확히 같다.

4. 결론. 수학적 귀납법에 의해 모든 $n \ge 1$에 대해 $a_n = 2^n-1$이 성립한다. $\blacksquare$

작은 예로 검산. 점화식을 직접 손으로 계산하면 $a_1=1$, $a_2=2(1)+1=3$, $a_3=2(3)+1=7$이다. 공식으로는 $a_2=2^2-1=3$, $a_3=2^3-1=7$로 정확히 일치한다(검산 완료).

조합 항등식의 귀납 증명: 이항계수의 합

쉽게 말하면: 파스칼의 규칙을 이용하면 이항계수를 전부 더한 값이 왜 항상 2의 거듭제곱이 되는지 귀납적으로 보일 수 있다.

09편에서 배운 이항계수(binomial coefficient) $\binom{n}{k}$와 파스칼의 규칙(Pascal’s rule) $\binom{n}{k} = \binom{n-1}{k-1}+\binom{n-1}{k}$을 이용해 다음 항등식을 증명한다.

명제. 모든 $n \ge 0$에 대해 $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$이다.

증명(단순 귀납법, 서술형 답안 형식).

1. 기저 단계. $n=0$일 때 좌변은 $\binom{0}{0}=1$뿐이고, 우변은 $2^0=1$이다. 일치한다.
2. 귀납 가정. $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$이 성립한다고 가정하자.
3. 귀납 단계. $n+1$에 대해 파스칼의 규칙을 각 항에 적용하면(양 끝 $\binom{n+1}{0}=\binom{n}{0}$, $\binom{n+1}{n+1}=\binom{n}{n}$은 그대로 두고 나머지에만 규칙을 적용해도 결과는 같다), 전체 합이 귀납 가정의 합을 두 번 겹쳐 더한 것과 같아진다는 것이 핵심이다.

귀납 가정을 대입하면 우변은 $2 \cdot 2^n = 2^{n+1}$이 되어, $n+1$에 대한 명제와 일치한다.

4. 결론. 수학적 귀납법에 의해 모든 $n \ge 0$에 대해 $\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n$이 성립한다. $\blacksquare$

작은 예로 검산. $n=3$이면 $\binom{3}{0}+\binom{3}{1}+\binom{3}{2}+\binom{3}{3} = 1+3+3+1=8$이고, $2^3=8$로 일치한다(검산 완료).

트리의 간선 수를 귀납법으로 증명하기

쉽게 말하면: 트리는 “잎 하나를 떼어내면 더 작은 트리가 된다”는 성질을 이용해 정점 수와 간선 수의 관계를 귀납적으로 보일 수 있다.

15편에서 이미 확인한 성질 “정점이 $n$개인 트리는 간선이 항상 $n-1$개다”를 이번에는 귀납법으로 직접 증명해본다. 이 증명에는 “정점이 2개 이상인 모든 트리는 차수가 1인 정점(잎)을 적어도 하나 갖는다”는 사실을 쓴다(14편의 차수 개념을 이용한 사실이며, 순환이 없다는 트리의 정의에서 나온다).

증명(강한 귀납법, 서술형 답안 형식).

1. 기저 단계. 정점이 1개뿐인 트리는 간선이 0개다. $n-1=1-1=0$이므로 성립한다.
2. 귀납 가정. 정점이 $k$개 이하인 모든 트리는 간선이 정점 수 $-1$개라고 가정하자.
3. 귀납 단계. 정점이 $k+1$개인 트리 $T$를 생각하자. $T$는 정점이 2개 이상이므로 잎 $v$가 적어도 하나 존재한다. $v$와 $v$에 연결된 간선 하나를 제거하면 정점 $k$개, 간선은 원래보다 1개 줄어든 트리 $T'$가 남는다($T'$도 여전히 연결되어 있고 순환이 없으므로 트리다). 귀납 가정에 의해 $T'$의 간선 수는 $k-1$개다. 제거했던 간선 1개를 다시 더하면 $T$의 간선 수는 $(k-1)+1=k$개이고, 이는 $T$의 정점 수 $(k+1)$에서 1을 뺀 값과 같다.
4. 결론. 강한 귀납법에 의해 정점이 $n$개인 모든 트리는 간선이 $n-1$개다. $\blacksquare$

작은 예로 검산. 정점 5개짜리 트리 하나를 아무렇게나 그려보자(예: 한 정점에서 나머지 4개로 뻗어나가는 별 모양). 간선은 4개이고, $n-1=5-1=4$로 일치한다(검산 완료).

자주 틀리는 점

• 기저 단계를 생략한다. 강한 귀납법이든 구조적 귀납법이든 기저 단계 없이 귀납 단계만 쓰면 증명이 성립하지 않는다.
• 단순 귀납법으로 충분한지 확인하지 않고 무조건 강한 귀납법 형식만 외워 쓴다. 강한 귀납법이 틀린 것은 아니지만(단순 귀납법 명제는 강한 귀납법 가정으로도 증명 가능), 서술형 답안에서는 실제로 여러 이전 값이 필요한 경우에만 강한 귀납법이라고 명시하는 것이 감점을 피하는 데 유리하다.
• 구조적 귀납법에서 재귀 정의의 기본 경우를 빠뜨린다. 트리·논리식처럼 재귀로 정의된 대상은 “가장 작은 형태”가 무엇인지부터 정확히 짚어야 한다.
• 귀납 단계에서 귀납 가정을 실제로 사용하지 않는다. 귀납 단계 계산 중 어느 줄에서 귀납 가정을 대입했는지 스스로 표시하는 습관이 필요하다.

핵심 정리

• 강한 귀납법은 $k$보다 작은 모든 값에 대한 가정을 쓸 수 있어, 소인수분해 존재성처럼 “더 작은 임의의 값으로 쪼개는” 증명에 필요하다.
• 구조적 귀납법은 재귀적으로 정의된 대상(트리 등)에 대해 기본 경우와 재귀 규칙 경우로 나눠 증명한다.
• 점화식의 닫힌해, 조합 항등식, 트리의 정점-간선 관계는 모두 “기저 단계 → 귀납 가정 → 귀납 단계에서 가정 대입 → 결론”의 같은 틀로 증명한다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 
• MathWorld - Mathematical Induction