정수론 #7 :: 수학적 귀납법

하노이의 탑

하노이의 탑은 한쪽 기둥에 쭉 쌓여있는 원판들을 다른 쪽 기둥으로 하나씩 옮기는 문제이다. 이때 작은 원판 위에는 큰 원판을 올릴 수 없다.

 

 

하노이의 탑은 풀리는 문제일까?

 

1. 원판이 1개라면 그냥 자유롭게 옮길 수 있다. 즉, 풀린다.

2. 원판이 n개일 때 풀린다고 가정한다면, n+1개일 때는 위쪽 n개의 원판을 B로 옮긴 다음에 제일 아래 원판을 C로 옮기고,

B의 원판 n개를 C에 있는 제일 아래 원판 위로 올리면 된다. 

 

n개의 원판을 옮기려면 몇 번 이동해야 할까?

 

필요한 이동 작업을 a_n이라 하자.

 

$\begin{gather*}a_{n+1}=a_n+1+a_n=2a_n+1 \\ \end{gather*}$

 

a_n+1일 때는 위에서 했던 것처럼 

n+1개일 때는 위쪽 n개의 원판을 B로 옮긴 다음에 => a_n번의 이동

제일 아래 원판을 C로 옮기고, => 1번의 이동

B의 원판 n개를 C에 있는 제일 아래 원판 위로 올리면 된다. => a_n번의 이동

 

a_n은 몇일까?

 

직접 n을 증가시켜 보며 계산해 보자.

n	1	2	3	4	...
a_n	1	3	7	15	...

 

추측 : a_n = 2^n - 1

 

1. n = 1 일 때 a_1 = 2^1 - 1 = 1 이므로 맞다.

2. a_n = 2^n-1이라 가정하면

 

$\begin{gather*}a_{n+1}=2^{n+1}-1\\ =2\cdot 2^n - 1 \\ =2 \cdot (a_n + 1) -1 \\ = 2 \cdot a_n +1 \end{gather*}$

 

이므로 추측은 정확하다.

 

---

 

수학적 귀납법 (Induction)

자연수 n에 대한 성질 p(n)이 임의의 n에 대하여 성립한다.

위와 같은 명제를 증명하려면 다음을 보이면 된다.

 

1. Base step : p(1)이 성립한다.

2. Induction step : p(n)이 성립하면(귀납 가정), p(n+1)이 성립한다.

 

p(n)이 잘 증명되었는지 확인하려면 직접 n번 계산해 보면 된다.

 

수학적 귀납법은 자연수에 관한 무한히 많은 성질들 p(n)을 한꺼번에 증명하는 연역법이다.

 

---

 

변형

1. Base step은 꼭 n=1부터 시작할 필요는 없다.

    ex) n >= 100

2. Strong induction : 귀납 가정은 p(n)뿐만 아니라 p(1), p(2), ..., p(n) 모두를 가정해도 된다.

 

---

 

Double Induction

임의의 n개의 연속되는 자연수는 n!의 배수이다.

따라서 아래는 정수이다.

 

$\begin{gather*} {m+n \choose n} = \frac{(m+n)(m+n-1)...(m+1)}{n!} \end{gather*}$

 

증명

 

P(k, n) = (k+1)(k+2)...(k+n)이라 하고 임의의 자연수 k, n에 대하여 P(k, n)이 n!의 배수임을 보이면 된다.

 

1. n = 1, k = 1일 때는 자명하다.

2. n, k > 1일 때 P(k-1, n)은 n!의 배수, P(k, n-1)은 n-1!의 배수라고 가정하자.

 

$\begin{gather*}P(k,n)=(k+1)(k+2)...(k+n-1)k +(k+1)(k+2)...(k+n-1)n \end{gather*}$

 

P(k, n)은 위와 같이 변형할 수 있다.

이때 첫 항은 P(k-1, n)에 해당하고, 둘째 항은 P(k, n-1)*n에 해당하므로 둘 다 n!의 배수이다.

따라서 P(k, n)도 n!의 배수이다.

 

---

 

피보나치 수열

피보나치 수열은 다음과 같은 점화식을 가진다.

 

$\begin{gather*}F_1=1, \ \ F_2=1 \ \ F_n=F_{n-2}+F_{n-1} \ \ \ \ for \ \ n \geq 3 \end{gather*}$

 

Binet's formula

 

$\begin{gather*}F_n=\frac{1}{\sqrt{5}} \Bigl\{ \left( \frac{1+\sqrt{5}}{2} \right)^n + \left( \frac{1-\sqrt{5}}{2} \right)^n \Bigr\} \end{gather*}$

 

가 피보나치 수열의 일반항임을 수학적 귀납법을 사용하여 증명해 보자.

 

1. n=1일 때 성립한다.

2. n일 때 Binet's formula가 성립한다고 가정하고, n+1일 때의 점화식에 대입해 보면

 

$\begin{gather*}F_{n+1}=F_{n}+F_{n-1} \\ \Rightarrow \frac{1}{\sqrt{5}} \Bigl\{ \left( \frac{1+\sqrt{5}}{2} \right)^{n+1} + \left( \frac{1-\sqrt{5}}{2} \right)^{n+1} \Bigr\} \\ = \frac{1}{\sqrt{5}} \Bigl\{ \left( \frac{1+\sqrt{5}}{2} \right)^{n} + \left( \frac{1-\sqrt{5}}{2} \right)^{n} \Bigr\} + \frac{1}{\sqrt{5}} \Bigl\{ \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} + \left( \frac{1-\sqrt{5}}{2} \right)^{n-1} \Bigr\} \end{gather*}$

 

이므로 n+1일 때도 성립한다.