11강 / 20강

수학적 귀납법 — 도미노 쓰러뜨리기

무한히 많은 것을 두 줄로 증명하는 법

"1부터 n까지 더하면 n(n+1)/2 이다." 이걸 어떻게 증명할까요? n = 1, 2, 3… 무한히 많은데 하나씩 확인할 수는 없습니다.

도미노를 생각해 보세요. 도미노가 무한히 늘어서 있어도, 딱 두 가지만 확인하면 전부 넘어진다고 말할 수 있습니다.

👆

기초 단계

첫 장이 넘어진다
n = 1 에서 참

➡️

귀납 단계

k가 넘어지면 k+1도 넘어진다

🎉

결론

모든 n에 대해 참

이것이 수학적 귀납법(mathematical induction)입니다. 무한한 확인을 두 줄로 바꾸는 마법이에요.

고등학생도미노 쓰러뜨리기

무한히 많은 것을 두 줄로 증명하는 법입니다.

① 첫 번째가 참 · ② n 이 참이면 n+1 도 참

왜 이걸로 충분한가

단계	—
1이 참 (①)	—
1이 참이니 2도 참 (②)	—
2가 참이니 3도 참	—
…	영원히

두 줄이 무한한 연쇄를 만든다

비유 — 도미노

확인할 것	대응
첫 도미노를 민다	기초 단계
넘어지면 다음도 넘어진다	귀납 단계

도미노가 백만 개여도 이 둘만 확인하면 됩니다. 하나하나 밀어 볼 필요가 없죠.

"전부 확인" 을 두 개 확인으로 바꾼 것

비유가 깨지는 곳

도미노는 실제로 시간이 걸립니다. 백만 번째가 넘어지려면 기다려야 하죠.

증명은 기다리지 않는다 — 이미 참임을 안다

이게 수학의 힘입니다. 무한한 과정을 유한한 논증으로 끝내요.

8개를 확인했습니다. 나머지 무한 개는요?

Python 브라우저에서 실행

# 먼저 식이 맞는지 감을 잡아 봅시다
print(" n |  1+2+...+n  |  n(n+1)/2  | 같은가")
print("-" * 44)
for n in range(1, 9):
    직접 = sum(range(1, n + 1))
    공식 = n * (n + 1) // 2
    print(f"{n:>2} |{직접:>12} |{공식:>11}  | {직접 == 공식}")
print()
print("맞아 보입니다. 하지만 이건 확인이지 증명이 아닙니다 (6강).")

🎮 도미노를 직접 세워 보세요

기초 단계를 빼면 어떻게 되는지, 귀납 단계가 끊기면 어떻게 되는지 도미노를 넘어뜨리며 확인해 보세요. 둘 중 하나만 빠져도 전체가 무너집니다.

고등학생귀납 가정을 쓴다는 것

초보자가 가장 헷갈리는 부분입니다.

"n 일 때 참이라고 가정" — 이게 순환논법 아닌가?

아닙니다. 왜냐면

증명하는 것	—
"n 일 때 참이다"	아니다
"n 이 참이면 n+1 도 참"	이것 ✔

조건문 P(n) → P(n+1) 을 증명하는 것이다 — 3강

3강에서 봤듯 조건문을 증명할 때는 가정을 참으로 놓고 시작합니다. 정상적인 방법이에요.

비유 — 사다리

보이는 것	—
첫 칸에 올라설 수 있다	기초
어느 칸에 있으면 다음 칸으로 갈 수 있다	귀납

"어느 칸에 있으면" 은 실제로 거기 있다는 뜻이 아닙니다. "만약 있다면" 이죠.

가정은 사실 주장이 아니라 조건이다

강한 귀납법

때로는 n 하나 가 아니라 1부터 n 전부 를 가정합니다.

종류	가정	언제
보통	P(n)	한 단계 전만 필요
강한	P(1)…P(n)	여러 단계 전이 필요

피보나치처럼 두 칸 전이 필요하면 강한 귀납법을 쓴다

증명 써 보기

주장 : 모든 자연수 n에 대해 1 + 2 + … + n = n(n+1)/2

[기초] n = 1 일 때, 좌변 = 1, 우변 = 1·2/2 = 1. 참이다.

[귀납 가정] n = k 일 때 참이라고 하자. 즉 1 + 2 + … + k = k(k+1)/2.

[귀납 단계] n = 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에 대해 참이다. ∎

핵심은 귀납 가정을 어디서 쓰는가입니다. 그 한 줄이 없으면 증명이 아니에요.

귀납 단계는 '식 정리'가 전부입니다.

Python 브라우저에서 실행

# 귀납 단계의 계산이 정말 맞는지 컴퓨터로 확인
def 좌변(k): return sum(range(1, k + 2))            # 1+...+(k+1)
def 우변(k): return k * (k + 1) // 2 + (k + 1)       # k(k+1)/2 + (k+1)
def 목표(k): return (k + 1) * (k + 2) // 2           # (k+1)(k+2)/2

for k in range(1, 7):
    print(f"k={k}  좌변 {좌변(k):>3} = 우변 {우변(k):>3} = 목표 {목표(k):>3} "
          f"→ {좌변(k) == 우변(k) == 목표(k)}")

고등학생기초 단계를 빼먹으면

note 의 이 경고를 재미있는 예로 봅시다.

귀납 단계만 맞으면 — 거짓도 증명된다

가짜 증명

"모든 자연수는 같다"

단계	—
가정	"n 개의 수는 전부 같다"
n+1 개	앞 n 개가 같고, 뒤 n 개도 같다
겹치니	전부 같다 ✔?

어디가 틀렸나 — n=1 일 때 두 무리가 안 겹친다 ⚠

기초 단계에서 n=2 를 확인했어야 하는데 n=1 만 봤기 때문입니다.

기초를 어디서부터 확인하느냐도 중요하다

더 단순한 예

"모든 자연수 n 에 대해 n = n+1"

단계	—
귀납	n = n+1 이면 양변에 1 → n+1 = n+2 ✔
기초	1 = 2 가 거짓 ⚠

귀납 단계는 완벽하게 성립한다 — 기초가 없을 뿐

비유 — 도미노를 안 밀면

준비	결과
도미노를 완벽하게 배열	—
안 민다	아무것도 안 넘어진다 ⚠

연쇄가 아무리 완벽해도 시작이 없으면 소용없다

그래서 증명을 검토할 때 기초 단계부터 봅니다. 가장 짧은데 가장 자주 빠뜨리거든요.

강한 귀납법

때로는 바로 앞 한 장이 아니라 앞의 전부가 필요할 때가 있습니다. "k일 때 참"이 아니라 "1부터 k까지 모두 참"을 가정하는 것을 강한 귀납법(strong induction)이라고 해요.

대표적인 예가 "2 이상의 모든 정수는 소수들의 곱으로 쓸 수 있다"입니다. n이 소수가 아니면 n = a × b 인데, 여기서 a와 b는 n-1이 아니라 n보다 작은 아무 수거든요.

재귀 호출이 곧 '더 작은 경우를 가정한다'입니다.

Python 브라우저에서 실행

# 강한 귀납법의 구조를 재귀로 그대로 옮긴 것 — 소인수분해
def 소인수분해(n, 깊이=0):
    들여쓰기 = "  " * 깊이
    d = 2
    while d * d <= n:
        if n % d == 0:
            print(f"{들여쓰기}{n} = {d} × {n // d}   ← 둘 다 {n}보다 작으니 가정을 쓸 수 있다")
            return 소인수분해(d, 깊이 + 1) + 소인수분해(n // d, 깊이 + 1)
        d += 1
    print(f"{들여쓰기}{n} 은 소수 (기초 단계)")
    return [n]

print("60 =", " × ".join(map(str, sorted(소인수분해(60)))))

고등학생귀납법과 재귀는 쌍둥이입니다

note 의 이 대목이 수학과 프로그래밍을 잇습니다.

귀납법	재귀
기초 단계	종료 조건
귀납 단계	자기 호출
n 에서 n+1 로	n 을 n−1 로 줄인다

방향만 반대다 — 증명은 올라가고 계산은 내려온다

그래서 이런 일이 가능합니다

일	도구
재귀 함수가 맞는지 증명	귀납법 ✔
재귀가 끝나는지 증명	줄어드는 양을 찾는다

종료 조건이 없는 재귀 = 기초 단계가 없는 귀납법

/ds 9강과 연결

재귀를 따라가며 이해하지 말고 믿고 맡기라고 했죠.

태도	대응
"작은 문제는 이미 풀렸다고 치자"	귀납 가정 ⭐

재귀를 쓰는 사고방식이 곧 귀납법이다

그리고 12강으로

점화식은 재귀의 수학적 표현입니다.

—	—
a₁ = 1	기초
aₙ = aₙ₋₁ + 2	귀납

세 가지 이름 — 귀납법 · 재귀 · 점화식 — 이 같은 구조다

수학 시간에 배운 것과 프로그래밍이 같은 것이라는 걸 알면 둘 다 쉬워집니다.

🤔 확인 문제

수학적 귀납법에서 기초 단계가 하는 일은?

해설 귀납 단계는 "넘어지면 다음도 넘어진다"는 조건부 주장일 뿐입니다. 실제로 하나라도 넘어뜨려 주지 않으면 아무 도미노도 넘어지지 않아요 — n = n+1 가짜 증명이 그 예입니다.

🤔 확인 문제

귀납 단계에서 하는 일을 바르게 말한 것은?

🤔 확인 문제

"2 이상의 정수는 모두 소수의 곱이다"를 증명할 때 강한 귀납법이 필요한 이유는?