수학적 귀납법(Mathematical Induction)은 자연수에 대한 명제를 증명하는 강력한 방법으로, 특정 성질이 모든 자연수에 대해 성립함을 보이는 데 사용된다.

개요

수학적 귀납법은 다음 두 가지 단계로 구성된다.

1. 기본 단계(Base Case) - 가장 작은 자연수(보통 n = 1)에 대해 명제가 성립함을 증명한다.
2. 귀납 단계(Inductive Step) - 어떤 자연수 k에 대해 명제가 참이라고 가정(귀납 가정)하면, k+1에서도 성립함을 증명한다.

이 두 가지를 만족하면, 모든 자연수에 대해 명제가 참임을 증명할 수 있다.

수학적 귀납법의 원리

수학적 귀납법은 자연수가 선형적인 순서를 가지며, 정렬 원리(Well-Ordering Principle)에 의해 최소 원소부터 시작하여 증명할 수 있다는 개념에 기반한다. 이는 도미노가 넘어지는 과정과 유사하다.

수학적 귀납법의 유형

보편적 수학적 귀납법(Standard Induction)

가장 일반적인 귀납법으로, k에서 성립하면 k+1에서도 성립함을 보인다.

예제: 1부터 n까지의 합이 다음 공식을 따른다는 것을 증명하라.

• n개의 자연수 합 공식:
  • S(n) = 1 + 2 + ... + n = (n(n+1))/2

증명

1. 기본 단계: n = 1일 때,
   • S(1) = 1 = (1(1+1))/2 = 1
   • 참이므로 성립한다.
2. 귀납 가정: 어떤 k에 대해 성립한다고 가정한다.
   • S(k) = (k(k+1))/2
3. 귀납 단계: k+1에서도 성립함을 보인다.
   • S(k+1) = S(k) + (k+1)
   • = (k(k+1))/2 + (k+1)
   • = ((k(k+1) + 2(k+1)) / 2)
   • = ((k+1)(k+2)) / 2
   • 이는 공식과 동일하므로 성립한다.

따라서, 모든 자연수 n에 대해 성립한다.

강한 수학적 귀납법(Strong Induction)

k에서만이 아니라, 1부터 k까지 모든 경우가 참이라고 가정하여 k+1에서 성립함을 보인다.

예제: 모든 n ≥ 1에 대해 피보나치 수열이 다음 점화식을 만족함을 증명하라.

• 피보나치 점화식:
  • F(n) = F(n-1) + F(n-2), (n ≥ 3)

증명

1. 기본 단계: F(1) = 1, F(2) = 1이 성립한다.
2. 귀납 가정: 1 ≤ m ≤ k에 대해 성립한다고 가정한다.
3. 귀납 단계: F(k+1) = F(k) + F(k-1)이 성립함을 보인다.

점화식 자체가 이전 두 개의 값을 필요로 하므로, 강한 귀납법을 적용해야 한다.

하향 귀납법(Reverse Induction)

보통 n이 큰 값에서 참임을 알고 있을 때, 이를 이용하여 작은 값에서 참임을 보인다.

수학적 귀납법과 다른 방법 비교

수학적 귀납법의 활용

1. 수열과 수식 증명 - 등차수열, 등비수열, 피보나치 수열 등.
2. 부등식 증명 - 특정 함수가 항상 일정한 범위 내에 있음을 증명.
3. 그래프 이론 - 그래프의 성질(예: 색칠 가능성, 연결성)을 보일 때 사용.
4. 알고리즘 증명 - 재귀 함수나 동적 프로그래밍의 성능을 분석할 때 사용.

같이 보기

• 강한 수학적 귀납법
• 실수 귀납법
• 귀류법
• 조합론