수학적 귀납법

수학적 귀납법은 자연수 $n$ 에 대해 어떤 명제 $P(n)$ 이 참임을 보이는 중요한 증명 기법입니다. 우리가 귀납적으로 사고하는 방식과 연관이 깊으며, 특히 자연수 전체에 대해 명제를 증명할 때 강력한 도구가 됩니다. 왜냐하면, 자연수는 무한히 많기 때문에 개별적으로 증명할 수 없기 때문입니다.

“귀납”이라는 단어는 일상적인 언어에서 개별적인 사례를 관찰한 후, 이를 바탕으로 일반적인 결론을 내리는 방식을 의미합니다. 예를 들어,

• 여러 마리의 백조를 관찰했더니 모두 흰색이었다.
• 그러므로 모든 백조는 흰색일 것이다. (이것은 귀납적 추론이지만 반드시 참은 아님)

예를 들어, $P(n)$ 이 $1$부터 $100$까지 참이라고 해서, $P(101)$ 도 참이라고 보장할 수는 없습니다. 따라서, 우리는 논리적 연결 고리를 만들어서 $n$ 에 대한 명제를 확장할 수 있어야 합니다.

수학적 귀납법의 증명 구조

어떤 명제 $P(n)$ 이 모든 자연수 $n$ 에 대해 참임을 보이려면 다음을 증명하면 충분합니다.

1. 기초 단계 (Base Case):

   • $n=1$ 일 때 명제 $P(1)$ 이 성립함을 보인다.

2. 귀납 단계 (Inductive Step):

   • $n=k$ 일 때 명제 $P(k)$ 가 성립한다고 가정한다. (귀납 가정)
   • 이때 $n=k+1$ 에 대해서도 명제 $P(k+1)$ 이 성립함을 보인다.

이 두 가지가 성립하면, 모든 자연수 $n$ 에 대해 명제가 참임을 보일 수 있습니다.
즉, 첫 번째 칸이 도미노처럼 쓰러지면 그다음 칸도 연쇄적으로 쓰러지는 것과 같은 원리입니다.

홀수의 합 공식 증명

자연수 $n$ 에 대해, 다음 등식이 성립함을 수학적 귀납법으로 증명해 보겠습니다.

$$1+3+5+7+\cdots +(2n-1)=n^2$$

이 공식은 “연속된 홀수의 합이 제곱수와 같다”는 것을 나타냅니다.

기초 단계

$n=1$ 일 때 등식이 성립하는지 확인합니다.

$$1=1^2$$

좌변과 우변이 같으므로, $n=1$ 일 때 등식이 성립합니다.

귀납 단계

$n=k$ 일 때 등식이 성립한다고 가정합니다. 즉,

$$1+3+5+\cdots +(2k-1)=k^2$$

이제 $n=k+1$ 일 때도 등식이 성립함을 보이면 됩니다.

• 양변에 다음 홀수 $2k+1$ 을 더합니다.

$$1+3+5+\cdots +(2k-1)+(2k+1)=k^2+(2k+1)$$

• 우변을 정리하면,

$$k^2+2k+1=(k+1{)}^2$$

즉,

$$1+3+5+\cdots +(2(k+1)-1)=(k+1{)}^2$$

이로써 $n=k+1$ 일 때도 등식이 성립함을 보였습니다.

결론

귀납법의 두 조건을 만족하므로, 모든 자연수 $n$ 에 대해 다음 공식이 성립합니다.

$$1+3+5+\cdots +(2n-1)=n^2$$

예제

1. 1부터 $n$ 까지의 합 공식 자연수 $n$ 에 대해 다음 등식이 성립함을 증명하시오.

$$1+2+3+\cdots +n=\frac{n(n+1)}{2}$$

2. 홀수의 합 공식 자연수 $n$ 에 대해 다음 등식이 성립함을 증명하시오.

$$1+3+5+\cdots +(2n-1)=n^2$$

3. 거듭제곱의 합 공식
   자연수 $n$ 에 대해 다음 등식이 성립함을 증명하시오.

$$1^2+2^2+3^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}$$

4. 세제곱의 합 공식 자연수 $n$ 에 대해 다음 등식이 성립함을 증명하시오.

$$1^3+2^3+3^3+\cdots +n^3={\left(\frac{n(n+1)}{2}\right)}^2$$

5. 거듭제곱 수열의 성질 자연수 $n$ 에 대해 다음 부등식이 성립함을 증명하시오.

$$2^n>n^2\text{(단, n≥5 )}$$

6. 피보나치 수열의 성질
   피보나치 수열 $F_n$ 이 다음 성질을 만족함을 증명하시오.

$$F_1+F_2+F_3+\cdots +F_n=F_{n+2}-1$$