수학적 귀납법과 불변식

도미노를 한 줄로 세워 두고 모두 쓰러뜨리려면 두 가지가 필요합니다. 첫 도미노가 쓰러져야 하고, 어떤 도미노가 쓰러지면 그다음 도미노도 쓰러지도록 간격이 맞아야 합니다. 이 두 가지가 갖추어지면 도미노가 몇 개든 모두 쓰러집니다. 수학적 귀납법(mathematical induction)은 이 생각으로 끝없이 많은 자연수에 대한 명제를 증명합니다. 이 글에서는 직접증명을 바탕으로 귀납법의 구조를 익히고, 잘못 쓰기 쉬운 곳과 반복문을 이해하는 데 쓰이는 방식을 살펴봅니다.

기초 단계와 귀납 단계

1 이상의 모든 자연수 n에 대해 명제 $P(n)$이 참임을 보이고 싶다고 합시다. 귀납법은 두 가지를 증명합니다. 첫째, 기초 단계(base case)로 $P(1)$이 참임을 보입니다. 둘째, 귀납 단계(inductive step)로, 1 이상의 임의의 자연수 k에 대해 $P(k)$가 참이라고 가정하면 $P(k+1)$도 참임을 보입니다. 이때 가정하는 $P(k)$를 귀납 가정(inductive hypothesis)이라고 합니다.

두 가지가 증명되면, $P(1)$이 참이고, 귀납 단계로 $P(2)$가 참이고, 다시 귀납 단계로 $P(3)$이 참인 식으로 모든 자연수에서 참이 됩니다. 귀납 가정은 증명하려는 결론을 미리 믿는 것이 아닙니다. "$P(k)$가 참이라면 $P(k+1)$도 참이다"라는 조건명제를 증명하는 것이고, 이것이 첫 도미노에서 시작해 차례로 이어질 때만 결론이 나옵니다.

합의 공식 증명하기

1부터 n까지의 합이 $n(n+1)/2$라는 공식을 증명해 보겠습니다. 먼저 작은 n에서 확인하면 공식이 맞아 보입니다.

print(all(sum(range(1, n + 1)) == n * (n + 1) // 2 for n in range(1, 101)))

True

1부터 100까지의 n에서 모두 맞았지만, 존재증명과 반례에서 본 것처럼 이것만으로는 모든 n에서 맞는다고 말할 수 없습니다. 이제 귀납법으로 증명합니다.

기초 단계로 n = 1이면 좌변은 1이고 우변은 $1\cdot2/2=1$이라 같습니다. 귀납 단계로, 1 이상의 임의의 k에 대해 $1+2+\cdots+k=k(k+1)/2$라고 가정합니다. 그러면 k + 1까지의 합은 다음과 같습니다.

마지막 식은 공식의 n에 k + 1을 넣은 것과 같으므로 $P(k+1)$이 참입니다. 귀납 가정을 쓴 곳은 첫 등호에서 $1+\cdots+k$를 $k(k+1)/2$로 바꾼 부분입니다. 귀납 단계를 쓸 때는 이렇게 $P(k)$를 어디에 썼는지가 드러나야 하고, 증명해야 할 $P(k+1)$을 처음부터 가정하면 안 됩니다.

부등식과 시작 범위

귀납법은 0이나 다른 수에서 시작할 수도 있습니다. 0 이상의 모든 정수 n에 대해 $2^n\ge n+1$임을 증명해 보겠습니다. 기초 단계로 n = 0이면 $2^0=1$이고 $0+1=1$이라 성립합니다. 귀납 단계로 $2^k\ge k+1$이라고 가정하면, 양변에 2를 곱해 $2^{k+1}\ge2k+2$입니다. 그런데 k가 0 이상이므로 $2k+2\ge k+2$이고, 따라서 $2^{k+1}\ge k+2=(k+1)+1$이 성립합니다.

부등식의 귀납 단계는 이처럼 가정에서 얻은 식과 목표 사이를 한두 줄의 비교로 이어 줍니다. "지수가 커지니까 당연하다"처럼 넘어가지 말고, 이어 주는 비교가 어떤 범위의 k에서 성립하는지까지 적어야 합니다. 여기서는 $2k+2\ge k+2$가 $k\ge0$에서 성립한다는 것을 썼습니다.

강한 귀납법

어떤 명제는 바로 앞의 $P(k)$ 하나만으로는 $P(k+1)$을 보이기 어렵고, 더 앞의 경우들이 필요합니다. 이때는 시작값부터 k까지의 모든 $P$가 참이라고 가정하고 $P(k+1)$을 보이는 강한 귀납법(strong induction)을 씁니다. 대표적인 예가 "2 이상의 모든 정수는 소수의 곱으로 나타낼 수 있다"입니다.

기초 단계로 2는 그 자체가 소수이므로 성립합니다. 귀납 단계로, 2 이상 k 이하의 모든 정수가 소수의 곱으로 나타난다고 가정하고 k + 1을 봅니다. k + 1이 소수이면 그 자체가 소수 하나의 곱입니다. 소수가 아니면 $k+1=ab$이고 a와 b는 2 이상 k 이하입니다. 가정에 따라 a와 b를 각각 소수의 곱으로 나타낼 수 있으므로, 두 곱을 이으면 k + 1도 소수의 곱입니다. 여기서는 k가 아니라 그보다 작은 a와 b의 경우가 필요했으므로 강한 가정이 자연스럽습니다. 이 증명을 그대로 재귀 함수로 옮기면 다음과 같습니다.

def factorize(n):
    for d in range(2, int(n ** 0.5) + 1):
        if n % d == 0:
            return factorize(d) + factorize(n // d)
    return [n]


print(factorize(360), factorize(97), factorize(2))

[2, 2, 2, 3, 3, 5] [97] [2]

n을 나누는 수 d를 찾으면 n을 d와 n // d로 나누어 각각을 재귀로 분해한 뒤 잇고, 찾지 못하면 n이 소수이므로 [n]을 돌려줍니다. d와 n // d가 n보다 작다는 것이 강한 귀납 가정을 쓰는 부분이고, 소수인 경우가 기초 단계에 해당합니다. 재귀가 맞는 이유를 귀납법으로 설명하는 것은 이처럼 같은 구조이기 때문입니다.

더 깊이: 귀납법이 옳은 이유와 가장 작은 반례

수학적 귀납법이 옳다는 것은 자연수의 다른 성질로 보일 수 있습니다. 자연수의 비어 있지 않은 부분집합에는 언제나 가장 작은 원소가 있다는 성질을 정렬 원리(well-ordering principle)라고 합니다. 기초 단계와 귀납 단계가 모두 성립하는데도 $P(n)$이 거짓인 n이 있다고 가정하면, 그런 n을 모은 집합은 비어 있지 않으므로 가장 작은 원소 m이 있습니다. 기초 단계 때문에 m은 시작값이 아니므로 $m-1$도 범위 안에 있고, m이 가장 작은 반례이니 $P(m-1)$은 참입니다. 그러면 귀납 단계에 따라 $P(m)$도 참이어야 하므로 모순입니다.

강한 귀납법도 같은 방식으로 정당화됩니다. 가장 작은 반례 m보다 작은 경우는 모두 참이므로, 강한 귀납 단계가 $P(m)$을 참으로 만들어 모순이 생깁니다. 반대로 보통의 귀납법만으로 강한 귀납법을 얻을 수도 있는데, "시작값부터 k까지의 P가 모두 참"을 $Q(k)$로 두고 Q에 보통의 귀납법을 쓰면 됩니다. 그래서 자연수에서 세 원리는 서로를 증명할 수 있는 같은 힘을 가집니다.

정렬 원리는 그 자체로도 증명의 도구가 됩니다. "반례가 있다면 가장 작은 반례를 잡고, 그보다 작은 반례를 만들어 모순을 낸다"는 방식이 그것이며, 앞의 소인수분해에서 소수의 곱으로 나타나지 않는 가장 작은 수를 가정해도 같은 증명을 할 수 있습니다. 이 성질이 없는 집합에는 귀납법을 그대로 쓸 수 없습니다. 예를 들어 양의 유리수 전체에는 가장 작은 원소가 없어서, 어떤 양의 유리수 q에 대해서도 그 절반인 $q/2$가 더 작습니다.

잘못된 귀납법 찾기

귀납법의 두 단계 가운데 하나라도 빠지거나 성립하지 않으면 증명이 무너집니다. 먼저 기초 단계를 빠뜨리는 경우를 보겠습니다. $P(n)$을 "$n>n+1$"이라고 하면 이 명제는 모든 n에서 거짓입니다. 그런데 $P(k)$를 가정하면 $k>k+1$이고, 양변에 1을 더해 $k+1>k+2$, 곧 $P(k+1)$이 나옵니다. 귀납 단계는 성립하는 것입니다. 하지만 $P(0)$이 거짓이므로 첫 도미노가 쓰러지지 않아 아무 결론도 나오지 않습니다.

귀납 단계가 어느 한 곳에서 끊기는 경우도 있습니다. "모든 말은 같은 색이다"를 귀납법으로 "증명"하는 유명한 오류가 그 예입니다. 말이 한 마리이면 당연히 같은 색입니다. 말 k + 1마리가 있을 때, 앞의 k마리는 가정에 따라 같은 색이고 뒤의 k마리도 같은 색이며, 두 무리가 겹치는 말을 통해 모두 같은 색이라고 주장합니다. 이 논증은 k가 2 이상일 때는 두 무리가 겹치지만, k = 1에서 두 마리를 볼 때는 앞의 한 마리와 뒤의 한 마리가 겹치지 않아 성립하지 않습니다. 귀납 단계는 모든 k에서 성립해야 하는데 k = 1에서 끊어진 것입니다.

반복문의 불변식

귀납법은 반복문이 맞는지 설명할 때도 쓰입니다. 1부터 n까지 더하는 반복문에서 "i번째 반복이 끝났을 때 total은 1부터 i까지의 합이다"라는 성질을 생각해 봅시다. 반복을 시작하기 전, 곧 i = 0일 때 total은 0이라 성립합니다. i번째 반복이 끝났을 때 성립한다면, 다음 반복에서 i + 1을 더하므로 그다음에도 성립합니다. 이것은 기초 단계와 귀납 단계 그대로이고, 반복이 n번 끝나면 total은 1부터 n까지의 합입니다.

total = 0
for i in range(1, 6):
    total += i
    assert total == i * (i + 1) // 2
print(total)

15

이렇게 반복하는 동안 늘 참으로 남는 성질을 불변식(invariant)이라고 합니다. assert는 조건이 거짓이면 오류를 내므로, 불변식이 실제 실행에서 지켜지는지 확인하는 데 쓸 수 있습니다. 다만 불변식이 유지된다는 것과 반복이 끝난다는 것은 별개의 문제입니다. 이 반복은 range(1, 6)이 다섯 번만 돌기 때문에 끝나는 것이고, 끝나는 이유는 따로 설명해야 합니다. 알고리즘에서 불변식과 종료를 함께 설명하는 방법은 불변조건·종료와 반례 찾기에서 자세히 다룹니다.

정리

• 수학적 귀납법은 기초 단계 $P(1)$과 귀납 단계 "$P(k)$이면 $P(k+1)$"을 증명해, 끝없이 많은 자연수에서 명제가 참임을 보입니다.
• 귀납 단계에서는 귀납 가정을 어디에 썼는지 드러나야 하며, 증명할 $P(k+1)$을 미리 가정하면 안 됩니다.
• 부등식의 귀납 단계에서는 가정과 목표를 잇는 비교가 어떤 범위에서 성립하는지 밝힙니다.
• 강한 귀납법은 시작값부터 k까지의 모든 경우를 가정하며, 소수의 곱으로 나타내기처럼 더 작은 여러 경우가 필요할 때 씁니다.
• 기초 단계가 없거나 귀납 단계가 어느 k에서 끊기면 증명이 무너지며, 반복문의 불변식도 같은 구조로 설명합니다.

연습 문제

1. 홀수의 합

1 이상의 모든 n에 대해 $1+3+5+\cdots+(2n-1)=n^2$임을 귀납법으로 증명하세요.

2. 기초 단계가 필요한 이유

귀납 단계 "$P(k)$이면 $P(k+1)$"만 증명하고 기초 단계를 빠뜨리면 왜 결론을 얻을 수 없는지, 본문과 다른 예를 들어 설명하세요.

3. 말의 색 오류 따라가기

본문의 "모든 말은 같은 색이다" 논증이 말 세 마리에서 네 마리로 갈 때는 성립하는 이유와, 한 마리에서 두 마리로 갈 때 성립하지 않는 이유를 설명하세요.

귀납 단계가 막히면 목표인 $P(k+1)$을 따로 적어 두고, $P(k)$와 다른 부분만 찾아보세요. 트리처럼 구조가 반복되는 대상에 대한 귀납법은 트리에서, 탐색 알고리즘의 불변식은 탐색에서 다시 만납니다. 다음 장의 집합의 표현과 연산에서는 원소를 모은 집합과 그 연산을 다룹니다.