컴퓨터공학 300 주제 시리즈의 004번째 글이다. 전체 지도는 여기.

한 줄 요약

수학적 귀납법은 “첫 경우가 참이고, 어떤 경우가 참이면 다음 경우도 참이다” 두 가지만 보여서 모든 자연수에 대한 명제를 증명하는 방법이다. 강한 귀납법은 “앞의 모든 경우가 참이면 다음도 참” 을 가정할 수 있게 넓힌 것이다.

왜 필요한가

자연수는 무한히 많다. 하나씩 확인해서는 끝나지 않는다. 귀납법은 무한한 확인을 유한한 두 단계로 줄여 준다.

컴퓨터공학에서 귀납법은 재귀와 같은 모양이다. 재귀 함수가 올바르다는 증명, 루프 불변식이 끝까지 유지된다는 증명, 트리·리스트 같은 재귀 자료구조의 성질, 분할 정복 알고리즘의 실행 시간 분석이 모두 귀납법으로 쓰인다. 재귀를 짤 줄 알면 귀납법을 이미 반쯤 아는 셈이고, 귀납법을 알면 재귀를 자신 있게 짤 수 있다.

핵심 개념

약한(보통) 귀납법

명제 P(n) 을 모든 n ≥ n₀ 에 대해 보이려면 다음 둘을 증명한다.

  1. 기저 단계(base case): P(n₀) 가 참이다.
  2. 귀납 단계(inductive step): 임의의 k ≥ n₀ 에 대해 P(k) 가 참이라고 가정하면(귀납 가정) P(k+1) 도 참이다.

도미노에 비유된다. 첫 조각이 넘어지고(기저), 어느 조각이 넘어지면 다음 조각도 넘어진다(귀납 단계). 그러면 모든 조각이 넘어진다.

정리. 모든 n ≥ 1 에 대해 1 + 2 + … + n = n(n+1)/2.

증명. 기저: n = 1 이면 좌변 1, 우변 1·2/2 = 1. 귀납 단계: k 에서 성립한다고 가정하자. 그러면 1 + … + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 이다. 이는 n = k+1 일 때의 식이다. ∎

정리. 모든 n ≥ 0 에 대해 2ⁿ - 1 은 1 + 2 + 4 + … + 2ⁿ⁻¹ 과 같다(n = 0 이면 빈 합 0).

이 식은 이진수 1111…1(n 자리)의 값이 2ⁿ - 1 이라는 뜻이다. 증명은 위와 같은 모양이니 확인 문제로 남긴다.

강한 귀납법

귀납 단계에서 P(k) 하나가 아니라 P(n₀), P(n₀+1), …, P(k) 모두를 가정하고 P(k+1) 을 보인다. 논리적 힘은 약한 귀납법과 같지만, 바로 앞 경우가 아니라 훨씬 앞의 경우가 필요할 때 훨씬 편하다.

정리. 2 이상의 모든 정수는 소수들의 곱으로 쓸 수 있다.

증명. 기저: 2 는 소수다. 귀납 단계: 2 부터 k 까지 모두 소수의 곱이라고 가정하고 k+1 을 보자. k+1 이 소수면 끝이다. 아니면 k+1 = a·b (2 ≤ a, b ≤ k) 로 쓸 수 있다. 가정에 따라 a 와 b 는 각각 소수의 곱이므로 그 곱인 k+1 도 소수의 곱이다. ∎

여기서 a, b 는 k 일 수도, 2 일 수도 있다. 바로 앞의 k 만 가정하는 약한 귀납법으로는 이 증명이 어색하다.

구조적 귀납법

자연수가 아니라 재귀적으로 정의된 대상(리스트, 트리, 수식)에도 같은 원리를 쓴다. “빈 트리에서 성립하고, 두 부분 트리에서 성립하면 그것을 합친 트리에서도 성립한다” 를 보이면 모든 유한 트리에서 성립한다. 010번 글(트리의 성질)에서 직접 쓴다.

귀납법과 재귀의 대응

귀납 증명 재귀 함수
기저 단계 종료 조건(base case)
귀납 가정 더 작은 입력에 대한 재귀 호출이 옳다고 믿기
귀납 단계 그 결과로 현재 입력의 답을 만드는 코드
기저가 빠지면 증명 무효 종료 조건이 빠지면 무한 재귀

재귀 함수를 짤 때 “재귀 호출이 더 작은 문제를 정확히 푼다고 믿고” 코드를 쓰는 것을 흔히 재귀적 믿음(recursive leap of faith)이라 부른다. 그 믿음의 근거가 귀납법이다.

흔한 함정

  • 기저 단계 생략. “P(k) → P(k+1)” 만으로는 아무것도 증명되지 않는다. “n = n + 1” 같은 거짓 명제도 귀납 단계는 성립한다(양변에 1 을 더하면 된다).
  • 귀납 단계가 모든 k 에서 통하지 않음. 유명한 “모든 말은 같은 색이다” 오류는 k = 1 에서 k+1 = 2 로 넘어가는 단계가 깨지는데도 일반 단계가 맞는 것처럼 보이게 만든다.
  • 강한 귀납법에서 기저가 부족함. P(k+1) 이 P(k) 와 P(k-1) 을 쓰면 기저 단계도 두 개가 필요하다. 피보나치 수열이 F(0), F(1) 두 값으로 시작하는 이유다.

직접 해 보기

재귀로 소인수분해를 구현해 보자. 코드의 구조가 강한 귀납법 증명과 똑같다. 그리고 합 공식을 작은 범위에서 확인한다.

def factorize(n):
    """n >= 2 를 소수들의 곱(리스트)으로. 강한 귀납법의 증명을 그대로 옮긴 코드."""
    assert n >= 2
    d = 2
    while d * d <= n:
        if n % d == 0:
            # n = d * (n // d), 둘 다 n 보다 작으므로 '귀납 가정'(재귀)을 쓴다
            return factorize(d) + factorize(n // d)
        d += 1
    return [n]          # n 이 소수: 기저와 같은 역할

for n in [2, 12, 97, 360, 1001, 2**10]:
    print(n, factorize(n))

# 합 공식: 1+...+n == n(n+1)/2
print(all(sum(range(1, n + 1)) == n * (n + 1) // 2 for n in range(1, 2001)))

# 기저가 두 개인 재귀: 피보나치
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print([fib(i) for i in range(12)])

실행 결과다.

2 [2]
12 [2, 2, 3]
97 [97]
360 [2, 2, 2, 3, 3, 5]
1001 [7, 11, 13]
1024 [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
True
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

factorize 가 반드시 끝나는 이유도 귀납적이다. 재귀 호출의 인자 d 와 n // d 는 모두 2 이상이고 n 보다 엄격히 작다. 자연수는 무한히 작아질 수 없으므로 언젠가 소수에 도달한다. 이것을 정렬 원리(well-ordering principle)라 하며 귀납법과 동치다.

현업에서는

  • 재귀 코드 리뷰. 트리 순회, JSON 평탄화, 디렉터리 탐색 같은 재귀 코드를 볼 때 두 가지만 묻는다. 종료 조건이 모든 기저 입력을 덮는가(빈 리스트, None, 리프)? 재귀 호출의 입력이 매번 엄격히 작아지는가? 둘 중 하나가 깨지면 무한 재귀나 스택 오버플로가 난다. 파이썬은 기본 재귀 깊이 제한이 있어서 깊은 재귀는 RecursionError 로 끝난다(sys.getrecursionlimit).
  • 루프 불변식. “반복을 시작할 때마다 result 는 앞의 i 개 원소의 합이다” 라는 불변식은 반복 횟수에 대한 귀납법으로 증명된다. 기저는 루프 진입 전, 귀납 단계는 루프 몸체 한 번이다.
  • 재귀 CTE. SQL 의 WITH RECURSIVE 는 기저 질의(non-recursive term)와 재귀 질의(recursive term)를 UNION 으로 잇는다(PostgreSQL, WITH Queries). 조직도, 카테고리 트리, 의존성 체인을 조회할 때 쓰며, 구조가 귀납적 정의 그대로다.
  • 점진적 롤아웃. 쿠버네티스 롤링 업데이트를 “지금 상태가 건강하면 한 단계 더 진행해도 건강하다” 는 귀납 단계로 보면, 각 단계의 준비 확인(readiness)이 귀납 가정을 검증하는 장치라는 것이 보인다. 첫 단계(기저)에서 확인을 건너뛰면 나머지 확인은 의미가 없다.

확인 문제

  1. 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ - 1 을 귀납법으로 증명하라.
  2. 모든 n ≥ 4 에 대해 2ⁿ ≥ n² 을 증명할 때 기저는 무엇인가?
  3. 4 원과 5 원 우표로 12 원 이상의 모든 금액을 만들 수 있음을 강한 귀납법으로 보일 때 필요한 기저 단계는?
  4. 종료 조건 없는 재귀 함수는 귀납 증명의 어떤 부분이 빠진 것과 같은가?

풀이

  1. 기저 n = 0: 빈 합 0 = 2⁰ - 1. 귀납: 2ᵏ - 1 + 2ᵏ = 2ᵏ⁺¹ - 1.
  2. n = 4 에서 16 ≥ 16. (귀납 단계: 2ᵏ⁺¹ = 2·2ᵏ ≥ 2k² ≥ (k+1)² 은 k ≥ 3 이면 성립한다.)
  3. 12 = 4+4+4, 13 = 4+4+5, 14 = 4+5+5, 15 = 5+5+5 네 개. 그 뒤 n 은 n - 4 에 4 원짜리를 하나 더 붙이면 된다.
  4. 기저 단계다.

더 읽을거리 (References)