cki_math_lab logo Home
홈/ 선행학습/ 수학적 귀납법

선행학습 · PREREQUISITE

수학적 귀납법

Mathematical Induction

원문 : blog.naver.com/cki_math_lab/220728667307

序

수학적 귀납법1)은 수학에서 가장 기본적인 추론2)의 방법이다. 이것은 자연수의 '전체'와 관계가 있다. 수학적 귀납법은 개개의 n3)이 아니라 '임의의 n'에 대하여 성립하는 명제를 증명하는 방법을 제시한다. 이것은 본질적으로 '무한의 반복'인 추론을 간결하게 단 하나의 추론으로 요약해서 보여준다. 수학적 귀납법에서 우리는 비로소 '무한'을 멋지게 다루는 방법에 접하게 될 것이다.

History

수학적 귀납법을 간결한 형태로 설명한 최초의 수학자는 파스칼4)이다. 당시 파스칼은 '임의의 n'이라는 기호를 쓰지는 않았다. 19세기 말 이탈리아의 수학자 페아노5)는 수학적 귀납법을 공리6) 속에 끌어들여 '페아노의 공리계'라 불리는 자연수에 관한 공리계를 제시하고, 자연수론의 기초를 만들었다.

페아노 공리계 (Peano System)

ⅰ원천 공리N에 1이라는 원소가 존재한다.
ⅱ후수 공리임의의 원소 n에 대해 '다음 원소'인 n′은 오직 하나 존재한다.
ⅲ출발 공리임의의 다음 원소 n′은 1이 될 수 없다.
ⅳ전개 공리임의의 두 원소 m과 n이 서로 다르면 다음 원소인 m′과 n′도 서로 다르다.
ⅴ귀납 공리임의의 집합 P가 있는데, 1이 P에 속하고 n이 P에 속할 경우 n′도 P에 속하면, P는 곧 N이다.

위 공리를 만족하는 집합을 '자연수 집합'이라 부르고, N으로 나타낸다.

수학적 귀납법

자연수 n에 관한 명제 P(n)이 모든 자연수 n에 대하여 성립한다는 것을 증명하려면 다음의 Ⅰ, Ⅱ를 증명하면 된다.
Ⅰn=1일 때 P(n)이 성립한다. 즉 P(1)이 성립한다.
Ⅱn=k일 때 P(n)이 성립한다고 가정하면, n=k+1일 때에도 P(n)이 성립한다. 즉 P(k) ⟹ P(k+1)이 성립한다.

이 증명법의 Ⅱ 부분에서는 P(k)가 성립하는 것을 가정하고, 그 가정 아래 P(k+1)이 성립하는 것을 증명했다. 이 가정을 '귀납법의 가정'이라고 한다.

例 1

임의의 자연수 n에 대하여 등식 1+3+5+⋯+(2n−1) = n² ⋯ ⓐ 이 성립하는 것을(수열을 배운 학생들은) 이미 알고 있다. 이 식은 등차수열의 합의 공식에서 이끌어냈던 것이다. 이 등식을 지금 다른 방법으로 다시 증명해보자.

위의 등식 ⓐ는 자연수 n에 관한 명제이다. 이 명제를 P(n)이라 하자. P(n)이 n=1,2,3 등에 대하여 성립하는 것은 식에 대입을 해보면 알 수 있다. 즉

좌변우변
n=111²=1
n=21+3=42²=4
n=31+3+5=93²=9

가 된다. 이러한 예에서 P(n)이 임의의 n에 대하여 성립하는 것이 예상되지만, 그러나 이러한 예를 아무리 많이 나열해도, 그것만으로는 P(n)이 일반적으로 성립한다고 볼 수는 없다.(증명으로 인정할 수 없다.)

그러나 수학적 귀납법에서 Ⅰ, Ⅱ를 증명하면 P(n)이 임의의 n에 대하여 성립하는 것이 명백히 증명되는 셈이다.

Proof.
ⅠP(1)은 1 = 1² 이라는 등식을 의미하는데, 이것이 성립하는 것은 자명하다.7)
Ⅱ P(k)가 성립한다. 즉 1+3+5+⋯+(2k−1) = k² 이 성립한다고 가정한다. 이 양변에 (2k+1)8) 더하면 1+3+5+⋯+(2k−1)+(2k+1) = k²+(2k+1)
∴ 1+3+5+⋯+(2k−1)+(2k+1) = (k+1)² 이 등식은 바로 ⓐ에 n=k+1을 대입한 경우이다. 즉 이것은 P(k+1)이 성립한다는 것을 뜻한다.

이것으로 'P(k) ⟹ P(k+1)' 이 증명되었다. 위의 Ⅰ, Ⅱ로부터 명제 P(n)9)은 모든 자연수 n에 대해 성립한다. 는 것이 증명된 것이다. 그 이유는 다음과 같다.

Ⅱ로부터 임의의 자연수 k에 대하여 P(k) ⟹ P(k+1) 이 성립하므로, k에 차례로 1, 2, 3, ⋯을 대입하면 P(1)⟹P(2)
P(2)⟹P(3)
P(3)⟹P(4)
⋮ 가 모두 성립하는 것이 된다.

그런데 Ⅰ로부터 P(1)이 성립되었다. 따라서 차례차례 P(1)이 참이고 P(1)⟹P(2)가 참이므로 P(2)는 참,
P(2)가 참이고 P(2)⟹P(3)가 참이므로 P(3)는 참,
P(3)가 참이고 P(3)⟹P(4)가 참이므로 P(4)는 참,
⋮ 이 되어, 결국 명제 P(n)이 모든 자연수 n에 대하여 성립한다는 것을 알 수 있다. 그러므로 명백히 명제 P(n)은 증명된 것이다. 위에서 다룬 증명법이 수학적 귀납법이다.

例 2

임의의 자연수 n에 대하여 6ⁿ−5n−1은 25의 배수이다.

Proof. aₙ = 6ⁿ−5n−1로 두자.

Ⅰa₁ = 6−5−1 = 0 이며, 이것은 25로 나누어떨어진다.
Ⅱ n=k일 때 aₖ = 6ᵏ−5k−1 이 25로 나누어떨어진다고 가정하자. 이때 ak+1 = 6k+1−5(k+1)−1 도 25로 나누어떨어짐을 보이면 된다. 이 증명을 위해 ak+1에서 6aₖ를 빼면 ak+1 − 6aₖ = {6k+1−5(k+1)−1} − 6{6ᵏ−5k−1} = 25k ∴ ak+1 = 6aₖ + 25k 여기서 aₖ는 25로 나누어떨어진다고 가정했으므로 위 식의 우변은 25로 나누어떨어진다. 그러므로 ak+1도 25로 나누어떨어진다.

Ⅰ, Ⅱ에 의해서 명제는 모든 자연수 n에 대해서 성립한다는 것이 증명되었다.

例 3 (베르누이 부등식10))

h>0일 때, 2 이상의 임의의 자연수 n에 대하여 부등식 (1+h)ⁿ > 1+nh 가 성립한다.

Proof. 주어진 부등식을 P(n)이라 하자.

Ⅰ n=2일 때11) (1+h)² = 1+2h+h² > 1+2h (∵ h>0) 따라서 P(2)가 성립한다.
Ⅱ k≥2로 하고, n=k일 때 P(n)이 성립하는 것으로 가정하자. 즉 (1+h)ᵏ > 1+kh 가 성립한다고 가정하자. 이 부등식의 양변에 (1+h)를 곱하면 (1+h)k+1 > (1+kh)(1+h) (∵ 1+h>0) 가 된다. 그리고 (1+kh)(1+h) = 1+(k+1)h+kh² > 1+(k+1)h (∵ h>0, k>0 ⟹ kh²>0) 이므로 부등식의 추이법칙12)에 의해 ∴ (1+h)k+1 > 1+(k+1)h 이것은 n=k+1일 때에도 P(n)이 성립한다는 것을 의미한다.

Ⅰ, Ⅱ에 의해서 부등식 P(n)은 n≥2인 모든 자연수 n에 대해서 성립한다는 것이 증명되었다.

수학적 귀납법 Ⅱ의 추가사항

수학적 귀납법의 Ⅱ 부분은 명백히 다음의 Ⅲ으로 대치13)할 수 있다.

Ⅲ n=k−1 (단, k≥2)일 때 P(n)이 성립한다고 가정하면, n=k일 때도 P(n)이 성립한다. 즉 P(k−1)⟹P(k) 가 성립한다.

실제로 Ⅲ은 단지 Ⅱ의 k, k+1을 k−1, k로 치환14)한 것에 지나지 않는다.

여기서 수학적 귀납법의 다른 형식을 배워보자. 지금까지와 마찬가지로 P(n)은 자연수 n에 관한 명제로 한다. 지금 P(n)에 대해서 Ⅰ과 다음의 Ⅳ가 증명되었다고 하자.

Ⅳ n≤k인 모든 n에 대하여 P(n)이 성립한다. 즉 P(1), P(2), ⋯, P(k)가 성립한다고 가정하면 P(k+1)도 성립한다.

이 경우도 P(n)은 역시 모든 자연수 n에 대하여 성립한다. 왜냐하면 Ⅳ는 P(1), P(2), ⋯, P(k) ⟹ P(k+1) 이라는 것을 뜻하므로, k에 차례로 1, 2, 3, ⋯을 대입하면 P(1) ⟹ P(2)
P(1), P(2) ⟹ P(3)
P(1), P(2), P(3) ⟹ P(4)
⋮ 이 성립한다. 그리고 Ⅰ에 의해 P(1)이 성립한다. 그러므로 例1과 같은 논의15)에 의해서 차례로 P(2), P(3), P(4), ⋯ 도 성립한다는 것을 알 수 있다.

앞의 Ⅱ가 Ⅲ과 대치할 수 있듯이 Ⅳ는 다음의 Ⅴ로 대치할 수 있다.

Ⅴ n<k (단, k≥2)인 모든 n에 대하여 P(n)이 성립한다. 즉 P(1), P(2), ⋯, P(k−1)가 성립한다고 가정하면 P(k)도 성립한다.

실제 문제에서는 Ⅰ,Ⅳ 또는 Ⅰ,Ⅴ의 꼴인 수학적 귀납법을 사용할 경우는 거의 없을지도 모른다. 하지만 이 형태의 귀납법을 알아두는 것은 가치 있는 일이다. Ⅳ 또는 Ⅴ의 형태에서는 '귀납법의 가정' 부분이 앞의 Ⅱ 또는 Ⅲ보다 강한 가정이 된다. 게다가 이 형태의 귀납법도 유용성16)이 있다.

例 4

실수들의 수열 a₁, a₂, ⋯ 이 ai+j ≤ aᵢ+aⱼ (단, i,j=1,2,⋯)를 만족할 때, 모든 양의 정수 n에 대하여 a₁1 + a₂2 + a₃3 + ⋯ + aₙn ≥ aₙ 이 성립한다.

Proof. 주어진 부등식을 P(n)이라 하자.

Ⅰn=1일 때, a₁1 ≥ a₁이 되어 P(1)이 성립한다.
Ⅳ n≤k에 대하여 P(n)이 참이라고 가정하자. 즉 a₁1 ≥ a₁
a₁1+a₂2 ≥ a₂
⋮
a₁1+a₂2+a₃3+⋯+aₖk ≥ aₖ 가 성립한다. 양변을 변변 더하면 k·a₁1 + (k−1)·a₂2 + (k−2)·a₃3 + ⋯ + 1·aₖk ≥ a₁+a₂+a₃+⋯+aₖ 가 성립한다. 양변에 a₁+a₂+a₃+⋯+aₖ를 더하고 정리하면 (k+1)a₁1 + {(k−1)+2}a₂2 + {(k−2)+3}a₃3 + ⋯ + (1+k)aₖk ≥ 2(a₁+a₂+a₃+⋯+aₖ)
(k+1)(a₁1+a₂2+a₃3+⋯+aₖk) ≥ 2(a₁+a₂+a₃+⋯+aₖ)
= (a₁+aₖ)+(a₂+ak−1)+(a₃+ak−2)+⋯+(aₖ+a₁) 가정에서 ai+j ≤ aᵢ+aⱼ이므로 a₁+aₖ ≥ ak+1
a₂+ak−1 ≥ ak+1
a₃+ak−2 ≥ ak+1
⋮
aₖ+a₁ ≥ ak+1
∴ (a₁+aₖ)+(a₂+ak−1)+⋯+(aₖ+a₁) ≥ k·ak+1 이다. 그러므로 부등식의 추이법칙에 의해 (k+1)(a₁1+a₂2+⋯+aₖk) ≥ k·ak+1 위 부등식의 양변에 ak+1을 더하면 (k+1)(a₁1+⋯+aₖk) + (k+1)·ak+1k+1 ≥ k·ak+1 + ak+1
(k+1)(a₁1+⋯+aₖk+ak+1k+1) ≥ (k+1)ak+1
∴ (a₁1+⋯+aₖk+ak+1k+1) ≥ ak+1 (∵ k+1>0) 즉 P(k+1)이 성립한다.

Ⅰ, Ⅳ에 의해서 부등식 P(n)은 모든 자연수 n에 대해서 성립한다는 것이 증명되었다.

  1. 1) 歸納法, Inductive Method — 개별적인 특수한 사실이나 원리로부터 그러한 사례들이 포함되는 좀 더 확장된 일반적 명제를 이끌어내는 것을 귀납(歸納, induction)이라 하며, 이러한 귀납적 추리의 방법과 절차를 논리적으로 체계화한 것을 귀납법이라 한다.
  2. 2) 推論 : 어떠한 판단을 근거로 삼아 다른 판단을 이끌어 냄
  3. 3) 여기서 n은 n∈N을 말한다.
  4. 4) Pascal, Blaise, 1623~1662, 프랑스
  5. 5) Peano, Giuseppe, 1858~1932
  6. 6) 公理, axiom : 수학이나 논리학 따위에서 증명이 없이 자명한 진리로 인정되며, 다른 명제를 증명하는 데 전제가 되는 원리
  7. 7) 自明하다 : 설명하거나 증명하지 아니하여도 저절로 알 만큼 명백(明白, 의심할 바 없이 아주 뚜렷하다)하다.
  8. 8) P(k)의 좌변에 열거된 항을 순서대로 a₁=1, a₂=3, ⋯, aₙ=(2k−1)이라 하면 ak+1 = 2k+1이다.
  9. 9) 등식 ⓐ
  10. 10) Bernoulli's inequality
  11. 11) Ⅰ에서 n=2일 때 명제가 성립하는 것을 증명하고, 이것과 Ⅱ로부터 2 이상의 임의의 자연수 n에 대하여 명제가 성립된다는 결론을 내렸다. 여기서는 '출발점'이 1에서 2로 바뀌었다. 그러나 수학적 귀납법에 의한 증명법이라는 것에는 변함이 없다. 수학적 귀납법의 '출발점'은 항상 하나로 정해진 것이 아니다. 예를 들면, P(n)이 l 이상의 정수에 관한 명제이고, l 이상의 모든 정수 n에 대하여 P(n)을 증명하고 싶은 경우 출발점은 n=l이 된다.
  12. 12) 推移法則 : 논리의 추이법칙 (p→q)∧(q→r)⟹(p→r), 부등식의 추이법칙 a<b이고 b<c이면 a<c이다.(공리) — 자세한 설명은 추론의 타당성 참고
  13. 13) 代置 : 다른 것으로 바꾸어 놓음
  14. 14) 置換 : 바꾸어 놓음
  15. 15) 論議 : 어떤 문제에 대하여 서로 의견을 내어 토의(어떤 문제에 대하여 검토하고 협의함)함
  16. 16) 有用性 : 소용(所用, 쓸 곳)에 닿고 이용할 만한 특성
← 증명법 간접증명법 →
prerequisite:logic source:cki_math_lab-blog