📝 수학적 귀납법이란?

수학적 귀납법은 자연수에 대한 명제의 참 여부를 증명하는 데 사용되는 강력한 수학적 증명 기법입니다.
이를 통해 무한히 많은 경우에 대해 명제가 참임을 보일 수 있습니다.

수학적 귀납법은 주로 ‘기본 단계’ 와 ‘귀납 단계’ 로 이루어집니다.

1️⃣ 기본 단계(Base Case)

명제가 첫 번째 자연수 n = 1(또는 특정 시작점 n = k)에 대해 참임을 증명합니다.

2️⃣ 귀납 단계(Inductive Step)

명제가 임의의 자연수 n = k에 대해 참이라고 가정했을 때, n = k + 1에도 참임을 증명합니다.

이를 좀 더 형식적으로 설명하면 다음과 같습니다.

1. 기본 단계:

   P(1)이 참임을 증명합니다.
   

2. 귀납 단계:

   P(k)가 참이라고 가정합니다.(귀납 가정)
   P(k+1)이 참임을 증명합니다.
   

기본 단계와 귀납 단계가 모두 성립하면, 수학적 귀납법에 의해 모든 자연수 n에 대해 명제 P(n)이 참임을 증명할 수 있습니다.

3️⃣ 예제

자연수 n에 대해 다음 명제를 증명해봅시다:

1+2+3+...+n= n(n+1)/2

1. 기본 단계:
   n = 1일때,

   1 = 1(1+1)/2 = 2/2 = 1
   

따라서 P(1)은 참입니다.

1. 귀납 단계:
   P(k)가 참이라고 가정합니다 즉,

   1+2+3+...+k = k(k+1)/2
   

   이 가정하에 P(k+1)이 참임을 증명합니다.

1+2+3+...+k+(k+1) = k(k+1)/2+(k+1)

우변을 정리하면,

k(k+1)/2 + (k+1) = (k(k+1)+2(k+1))/2 = ((k+1)(k+2))/2

이는 P(k+1) 입니다.

기본 단계와 귀납단계가 모두 성립했으므로, 수학적 귀납법에 의해 모든 자연수 n에 대해 1+2+3+...+n = n(n+1)/2임을 증명할 수 있습니다.