수학적 귀납법 (Mathematical Induction)

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

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

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

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

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

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

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

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

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

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

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

양변에 $(n+1{)}^2$을 더하면

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

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