수학적 귀납법 (Mathematical Induction)

명제 P가 다음 두 조건을 만족한다고 하자.

● P(1)이 성립한다.
● n∈N(자연수 전체의 집합)에 대하여 P(n)이 성립하면, P(n+1) 역시 성립한다.

그러면 모든 n∈N에 대하여 P(n)이 성립한다. 이 공리(公理)를 수학적 귀납법이라 한다.

[예제 1] 자연수의 합의 공식
\[1+2+3+\cdots+n={n(n+1)\over2}\]
이 임의의 자연수 n에 대하여 성립함을 증명하여라.

<증명>
n에 대하여 성립한다면 \(1+2+3+\cdots+n={n(n+1)\over2}\) 이다.
n=1에 대하여 \(1={(1)(1+1)\over2}=1\) 이므로 자명하게 성립한다.
양변에 n+1을 더하면 \(1+2+3+\cdots+n+(n+1)={n^2+3n+2\over2}={(n+1)(n+2)\over2}\)
이므로 역시 성립한다.
수학적 귀납법에 따라 임의의 n∈N에 대하여도 성립한다.

[예제 2] k≥2인 자연수 k에 대하여 다음 부등식 \(k!\ge2^{k-1}\)이 성립함을 증명하여라.

<증명>
k=2 일 때 \(2!=2^1\) 이므로 명백히 성립한다.

k 일 때 성립한다고 가정하면 \((k+1)!=k!(k+1)\ge2^{k-1}(k+1)>2^k\) 이므로 역시 성립한다.

수학적 귀납법에 따라 k≥2인 임의의 자연수 k에 대하여도 성립한다.

[예제 3] 자연수의 제곱합의 공식
\[1^2+2^2+3^2+\cdots+n^2={n(n+1)(2n+1)\over6}\]
이 임의의 자연수 n에 대하여 성립함을 증명하여라.

<증명>
n=1 에 대하여 \(1^2={(1)(1+1)(2\cdot1+1)\over6}=1\) 이므로 자명하게 성립한다.
n에 대하여 성립한다면 \(1^2+2^2+3^2+\cdots+n^2={n(n+1)(2n+1)\over6}\) 이다.

양변에 \((n+1)^2\)을 더하면

\(1^2+2^2+3^2+\cdots+n^2+(n+1)^2={n(n+1)(2n+1)\over6}+(n+1)^2={(n+1)(n+2)(2n+3)\over2}\)로 역시 성립한다.

수학적 귀납법에 따라 임의의 n∈N에 대하여도 성립한다.