수학적 귀납법

Mathematical Induction

수학적 귀납법은 무한히 많은 명제를 도미노처럼 한 줄로 쓰러뜨리는 증명 방법이에요. 먼저 첫 번째 도미노가 쓰러지는 것(n = 1일 때 성립)을 보이고, 다음으로 어떤 도미노가 쓰러지면 바로 다음 것도 쓰러진다는 것(n = k이면 n = k + 1도 성립)을 보여요. 이 두 가지만 확인하면 모든 자연수에 대해 명제가 참임이 한꺼번에 보장돼요. 이 페이지에서는 도미노가 차례로 넘어가는 과정을 따라가며 귀납법의 두 단계를 직접 확인해 봐요.

도미노 효과: 귀납법의 직관

쓰러진 도미노 수3

💡 도미노와 귀납법의 핵심 비유

①첫 번째 도미노를 넘어뜨린다 (n=1 확인)

②하나가 쓰러지면 다음도 쓰러진다 (k → k+1)

③이 두 조건만 있으면 모든 도미노가 쓰러진다

④이것이 수학적 귀납법의 핵심 아이디어!

증명의 구조: 3단계

📐 각 단계의 역할

①1단계 (기저): n=1일 때 직접 성립을 보인다

②2단계 (가정): n=k일 때 성립한다고 가정한다

③3단계 (증명): 가정을 이용하여 n=k+1일 때도 성립함을 보인다

④세 단계를 모두 완료하면 모든 자연수에 대해 증명 완료

예제: 1+2+...+n = n(n+1)/2 증명

1단계: n=1

좌변 = 1, 우변 = 1×22 = 1 ✓ 성립

n=1일 때 양변이 같음을 직접 확인

2단계: n=k 가정

1+2+...+k = k(k+1)2 (가정)

n=k일 때 성립한다고 가정

3단계: n=k+1 증명

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

가정을 이용하여 k+1일 때도 성립함을 보임

✅ 증명 완료!

①n=1일 때 성립 확인 ✓

②n=k 성립 가정 → n=k+1 성립 증명 ✓

③따라서 모든 자연수 n에 대해 1+2+...+n = n(n+1)/2

귀납법 활용 팁

⚠️ 자주 하는 실수

①기저 단계(n=1)를 빠뜨리면 증명이 성립하지 않는다

②가정 단계에서 '증명할 것'을 가정으로 써야 한다

③k+1 단계에서 가정(k일 때)을 반드시 사용해야 한다

④가정을 사용하지 않으면 귀납법이 아니다

📐 귀납법이 필요한 상황

①자연수 n에 대한 등식/부등식 증명

②수열의 합 공식 증명

③나눗셈 관련 명제 (3^n - 1은 2의 배수)

④기하학적 성질 (n각형 내각의 합)

총정리

수학적 귀납법

P(1) 성립 ∧ [P(k) → P(k+1)] ⟹ ∀n∈ℕ, P(n)

기저 + 귀납 단계 → 모든 자연수에 대해 성립

🎯 시험 포인트

①3단계 구조: 기저(n=1) → 가정(n=k) → 증명(n=k+1)

②기저 단계를 절대 생략하지 말 것

③귀납 단계에서 가정을 반드시 활용

④부등식 귀납법: k+1일 때 좌변을 변형하여 가정 대입

⑤n=1이 아닌 n=2부터 시작하는 경우도 있음

예제와 기출

예제 1

모든 자연수 n에 대하여 1 + 2 + ... + n = n(n+1)/2 임을 수학적 귀납법으로 증명할 때, 가장 먼저 확인해야 하는 단계는?

수학적 귀납법은 (i) n=1에서 성립, (ii) n=k 성립을 가정하면 n=k+1에서도 성립의 두 단계로 이루어진다.

(i) n = 1 확인, (ii) P(k) ⟹ P(k+1)

가장 먼저 기저 단계 n=1에서 좌변과 우변이 같은지 확인한다.

n=1: 좌변 = 1, 우변 = 1×22 = 1

▸ 기저 단계: n = 1 일 때 성립함을 먼저 확인한다.

귀납법은 출발점(n=1)을 먼저 확인하지 않으면 전체 증명이 무너진다.

예제 2

수학적 귀납법에서 n=k일 때 성립을 가정한 뒤, 그 가정을 이용하여 무엇을 보여야 하는가?

n=k에서 성립한다고 가정한다 (귀납 가정).

가정: P(k) 성립

이 가정을 디딤돌로 삼아 n=k+1에서도 성립함을 보인다.

보일 것: P(k+1) 성립

▸ n = k+1 일 때도 성립함을 보인다.

귀납 가정 P(k)를 반드시 사용하여 P(k+1)을 이끌어내야 한다.

2023 수능 수학 유형 변형

도미노가 모두 넘어지는 상황에 대응하는 수학적 귀납법의 두 단계로 옳은 것은?

①n=1 성립, 그리고 P(k) ⟹ P(k+1)

②n=1 성립만 확인

③P(k) ⟹ P(k+1) 만 확인

④모든 n을 직접 대입

⑤n=2 성립, 그리고 P(k) ⟹ P(k−1)

▸ ① n=1 성립, 그리고 P(k) ⟹ P(k+1)

첫 번째 도미노가 넘어진다 = 기저 단계 n=1에서 성립.

(i) n = 1 에서 성립

k번째가 넘어지면 (k+1)번째도 넘어진다 = 귀납 단계 P(k) ⟹ P(k+1).

(ii) P(k) ⟹ P(k+1)