수학적 귀납법(Mathematical Induction)

수학적 귀납법(Mathematical Induction)은 일련의 명제들이 모두 참이라는 것을 증명하는 데 사용되는 강력한 수학적 기법입니다. 이 기법은 특히 자연수 집합에 대한 명제를 다룰 때 유용하며, 귀납법의 주요 생각은 "도미노 효과"에 비유할 수 있습니다.

 

귀납법을 이해하려면 귀납법의 두 가지 주요 단계, 즉 "기초 단계"와 "귀납 단계"를 이해하는 것이 중요합니다.

 

1. 기초 단계 (Base Step):

귀납법의 첫 번째 단계는 명제가 가장 간단한 경우, 즉 n=1일 때 참임을 보이는 것입니다. 이 단계에서는 주어진 문제를 가장 간단한 형태로 끓여내고 그것이 참임을 확인합니다. 예를 들어, 합의 공식 1+2+...+n = n(n+1)/2의 경우 n=1을 대입하면 1=1*(1+1)/2가 되어 참이 됩니다.

 

2. 귀납 단계 (Inductive Step):

귀납 단계에서는 "n=k일 때 명제가 참이면, n=k+1에서도 참이다"라는 것을 증명합니다. 다시 말해, 만약 명제가 어떤 수에 대해 참이라면, 그 다음 수에 대해서도 참임을 보여줍니다. 이 단계에서는 일반적으로 주어진 명제의 형태를 이용해 새로운 식을 도출하고, 그 식이 참임을 증명합니다.

이 두 단계를 완료하면 주어진 명제가 모든 자연수에 대해 참임이 증명됩니다. 다시 말해, 도미노가 한 개 넘어지면 그 다음 도미노도 넘어질 것이라는 원리를 적용하는 것입니다.

 

예제:

 

수학적 귀납법의 간단한 예를 살펴봅시다. 명제 "1 + 2 + 3 + ... + n = n(n+1)/2"가 모든 자연수 n에 대해 참임을 증명하려면 다음 단계를 따릅니다.

• 기초 단계: n=1일 때, 왼쪽은 1이고 오른쪽은 1*(1+1)/2=1이므로 명제는 참입니다.
• 귀납 단계: n=k일 때 명제가 참이라고 가정합니다. 즉, 1+2+...+k = k(k+1)/2입니다. 그러면 n=k+1일 때 명제가 참인지 확인해야 합니다. 왼쪽을 k+1까지 더하면 1+2+...+k+(k+1)가 되고, 이는 [k(k+1)/2] + (k+1)로 쓸 수 있습니다. 이를 정리하면, (k+1)(k+2)/2 = (k+1)((k+1)+1)/2가 됩니다. 따라서 n=k+1일 때도 명제는 참입니다.

따라서 이 명제는 모든 자연수 n에 대해 참임이 증명되었습니다. 이렇게 수학적 귀납법을 통해 주어진 명제가 모든 자연수에 대해 참임을 증명할 수 있습니다. 이 방법은 무한한 경우의 수를 다루는 문제에서 특히 유용합니다.