수학적 귀납법 (Mathematical Induction)

수학적 귀납법(Mathematical Induction)이란

정수 n에 관한 어떤 명제가 모든 \(n \geq n_0\)에 대해 참임을 증명하는 일반적인 방법

 

 

수학적 귀납법의 단계

• 기초(Basis) 단계
  • n의 가장 작은 값 \(n_0\)에 대해 증명
• 귀납(Induction) 단계
  • (명제가 \(n_0\)에서 n-1까지의 값들에 대해 이미 증명되었다는 가정 하에)
    \(n > n_0\)에 대해 명제를 증명

 

 

예제: 하노이의 탑

한 기둥에서 원반 n개를 다른 한 기둥으로 옮기는 데 필요한 최소한의 이동 횟수를 \(T_n\)라고 하면 아래 식은 자명합니다

\begin{align}
T_0 &= 0 \\
T_1 &= 1 \\
T_2 &= 3
\end{align}

n개의 원반을 옮기는 문제에 대해 생각해보면, 작은 원반 n-1개를 다른 기둥으로 옮기고(\(T_{n-1}\)), 가장 큰 원반을 또다른 원반으로 옮기고(이동횟수: 1), 마지막으로 옮겨놨던 작은 원반 n-1개를 큰 원반 위로 옮기는 과정(\(T_{n-1}\))이 필요합니다. 따라서 원반 n개(n>0)의 이동 횟수는 \(2T_{n-1}+1\)를 넘지 않습니다.

이보다 적은 수의 이동으로 탑을 옮길 수 없으니 \(T_n = 2T_{n-1}+1\)이 됩니다.

 

몇 개의 사례를 살펴보면 아래와 같습니다

\begin{align}
T_3 &= 2 \times 3 + 1 = 7 \\
T_4 &= 2 \times 7 + 1 = 15 \\
T_5 &= 2 \times 15 + 1 = 31
\end{align}

여기서 일반항을 다음과 같이 추측할 수 있습니다 (이를 귀납적 비약(inductive leap)이라고 합니다)

\[T_n = 2^n-1~~(n \leq 0) \tag{1} \]

 

이 식을 검증하기 위해 수학적 귀납법을 적용합니다.

• 기초 단계
  • \(T_0 = 2^0 - 1 = 0\)이므로 만족
• 귀납 단계
  • \(T_n = 2T_{n-1}+1 = 2(2^{n-1}-1)+1 = 2^n - 1\)이므로 만족

따라서 점화식의 일반해는 (1)이 됩니다.