증명하는 법: 직접 증명, 귀납법, 귀류법

코드를 짜고 테스트 몇 개를 통과하면 "잘 동작한다"고 말하기 쉬워요. 하지만 테스트는 확인한 경우에만 맞다는 걸 보여 줄 뿐이에요. 모든 경우에 맞다는 걸 보이는 방법이 증명이에요. 증명을 익히면 수학 책이 읽히기 시작하고, 내 알고리즘이 정말 올바른지 따져 볼 수 있게 돼요.

예시는 증명이 아니다

$n^2 + n + 41$에 $n = 0, 1, 2, \ldots$을 넣어 볼게요. 41, 43, 47, 53, 61, 71... 모두 소수예요. $n = 39$까지 계속 소수가 나와요. 그럼 모든 $n$에 대해 소수일까요?

$n = 40$을 넣으면 $1600 + 40 + 41 = 1681 = 41^2$이라 소수가 아니에요. 40번 연속 맞았지만 41번째에 깨졌어요.

거꾸로, 반례 하나면 일반적인 주장이 틀렸음을 보이기에 충분해요. "모든 경우에 성립한다"는 주장은 증명으로 보이고, 반박은 반례 하나로 해요. 이 비대칭을 기억하세요.

증명을 읽고 쓰기 위한 준비

증명은 이미 받아들인 사실(정의, 공리, 이미 증명된 정리)에서 출발해 논리 규칙만으로 결론까지 가는 글이에요. 자주 쓰는 정의 몇 개를 먼저 정해 둘게요.

• 정수 $n$이 짝수라는 것은 어떤 정수 $k$가 있어서 $n = 2k$라는 뜻이에요.
• 정수 $n$이 홀수라는 것은 어떤 정수 $k$가 있어서 $n = 2k + 1$이라는 뜻이에요.
• 정수 $a$가 $b$를 나눈다($a \mid b$)는 것은 어떤 정수 $k$가 있어서 $b = ak$라는 뜻이에요.

증명이 막히면 대부분 정의로 돌아가면 풀려요. "짝수"라는 말을 보면 곧바로 "$2k$"로 바꿔 쓰는 습관을 들이세요.

직접 증명

가정에서 출발해 한 단계씩 결론으로 가는 가장 기본적인 방법이에요.

정리. 두 홀수의 곱은 홀수다.

증명. 두 홀수를 $a = 2m + 1$, $b = 2n + 1$이라고 하자($m$, $n$은 정수). 그러면

$2mn + m + n$은 정수이므로 $ab$는 $2 \times (\text{정수}) + 1$ 꼴, 즉 홀수다. $\blacksquare$

마지막의 네모는 "증명 끝"이라는 표시예요. 구조를 보세요. 정의로 바꾸고 → 계산하고 → 다시 정의의 모양으로 맞췄어요. 대부분의 직접 증명이 이 흐름이에요.

대우 증명

$p \to q$를 직접 보이기 어려우면, 진릿값이 같은 대우 $\lnot q \to \lnot p$를 보여도 돼요(수와 논리 강의에서 배웠죠).

정리. $n^2$이 짝수이면 $n$도 짝수다.

직접 하려면 $n^2 = 2k$에서 $n$을 끌어내야 하는데 막막해요. 대우는 "$n$이 홀수이면 $n^2$도 홀수다"인데, 이건 바로 앞에서 증명한 것(두 홀수의 곱은 홀수)에서 $a = b = n$인 경우예요. $\blacksquare$

귀류법: 모순을 이끌어 내기

결론이 거짓이라고 가정한 뒤, 그 가정에서 말이 안 되는 결과(모순)가 나온다는 걸 보여요. 그러면 가정이 틀렸으니 결론이 참이에요.

루트 2는 분수로 나타낼 수 없다

증명. $\sqrt{2}$가 분수라고 가정하자. 그러면 더 이상 약분되지 않는 정수 $a$, $b$로 $\sqrt{2} = a/b$라고 쓸 수 있다. 양변을 제곱하면

$a^2$이 짝수이므로 앞의 정리에 따라 $a$도 짝수, 즉 $a = 2c$다. 대입하면 $4c^2 = 2b^2$, 곧 $b^2 = 2c^2$이므로 $b$도 짝수다. 그런데 $a$와 $b$가 둘 다 짝수면 2로 약분된다. 더 이상 약분되지 않는다고 했던 가정과 모순이다. 따라서 $\sqrt{2}$는 분수가 아니다. $\blacksquare$

소수는 무한히 많다

2천 년도 더 전에 유클리드가 남긴 아름다운 증명이에요.

증명. 소수가 유한하다고 가정하고, 모든 소수를 $p_1, p_2, \ldots, p_k$라고 하자. 이들을 모두 곱하고 1을 더한 수 $N = p_1 p_2 \cdots p_k + 1$을 생각하자. $N$을 어떤 $p_i$로 나눠도 나머지가 1이므로, 목록의 어떤 소수로도 나누어떨어지지 않는다. 그런데 1보다 큰 모든 정수는 어떤 소수로 나누어떨어진다. 그러면 목록에 없는 소수가 있어야 하므로 "모든 소수를 나열했다"는 가정과 모순이다. $\blacksquare$

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

자연수 $n$에 대한 주장 $P(n)$이 모든 $n$에 대해 참임을 보이는 강력한 도구예요. 두 가지만 보이면 돼요.

1. 기저 단계: $P(1)$이 참이다. (첫 도미노가 넘어진다)
2. 귀납 단계: $P(k)$가 참이면 $P(k+1)$도 참이다. (하나가 넘어지면 다음 것도 넘어진다)

이 둘이 성립하면 도미노가 끝없이 넘어지듯 모든 $n$에 대해 참이에요.

정리. $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$

증명.

• 기저 단계: $n = 1$이면 좌변은 1, 우변은 $1 \cdot 2 / 2 = 1$로 같다.
• 귀납 단계: $n = k$일 때 성립한다고 가정하자. 즉 $1 + \cdots + k = \frac{k(k+1)}{2}$. 양변에 $k + 1$을 더하면

이는 $n = k + 1$일 때의 식과 정확히 같다. 따라서 모든 자연수 $n$에 대해 성립한다. $\blacksquare$

귀납 단계에서 "$P(k)$가 참이라고 가정"하는 것이 순환 논리처럼 느껴질 수 있어요. 하지만 우리는 $P(k)$ 자체를 주장하는 게 아니라, "$P(k)$에서 $P(k+1)$이 따라 나온다"는 연결 고리를 보이는 거예요. 기저 단계가 첫 도미노를 넘어뜨리니, 연결 고리를 따라 전부 넘어가요.

귀납법과 재귀

귀납법은 프로그래밍의 재귀와 같은 구조예요.

def total(n):
    if n == 1:          # 기저 단계
        return 1
    return total(n - 1) + n   # 귀납 단계: n-1의 답으로 n의 답을 만든다

재귀 함수가 올바르다는 것은 귀납법으로 증명해요. "가장 작은 경우를 맞게 처리하고, 작은 경우가 맞으면 큰 경우도 맞게 만든다"는 걸 보이면 돼요. 알고리즘 트랙의 재귀와 동적 계획법 강의에서 이 생각을 계속 써요.

알고리즘이 올바름을 증명하기: 반복문 불변식

반복문이 올바른지는 불변식으로 보여요. 불변식은 반복이 몇 번 돌든 매번 시작할 때 참인 성질이에요.

리스트의 최댓값을 찾는 코드를 볼게요.

def find_max(nums):
    best = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > best:
            best = nums[i]
    return best

불변식: 매 반복을 시작할 때 best는 nums[0]부터 nums[i-1]까지 중 최댓값이다.

1. 처음: i = 1일 때 best = nums[0]이고, 앞부분은 nums[0] 하나뿐이니 참이에요.
2. 유지: 참인 상태에서 nums[i]와 비교해 더 크면 바꾸니, 반복이 끝나면 nums[0]부터 nums[i]까지의 최댓값이 돼요. 다음 반복 시작에서도 참이에요.
3. 종료: 반복이 끝나면 i가 길이와 같아지고, 불변식에 따라 best는 전체의 최댓값이에요.

귀납법과 똑같은 구조죠. 실무에서 매번 이렇게 엄밀하게 쓰지는 않지만, 까다로운 반복문을 짤 때 "이 반복이 지키는 약속이 뭐지?"를 묻는 습관은 버그를 크게 줄여 줘요. 이진 탐색처럼 경계값 실수가 잦은 코드에서 특히 위력을 발휘해요.

흔한 증명 오류

• 예시로 증명하기. 몇 개 확인한 것은 증명이 아니에요.
• 결론을 가정하기. 증명할 것을 은근슬쩍 중간에 써 버리는 순환 논리예요.
• 역을 증명하기. $p \to q$를 증명해야 하는데 $q \to p$를 보였다면 증명이 아니에요.
• 0으로 나누기. 식을 정리하다 0일 수도 있는 값으로 나누면 "1 = 2" 같은 엉터리 결론이 나와요.
• 귀납의 기저를 빼먹기. 귀납 단계만 보이면, 아무 도미노도 넘어지지 않은 채로 "넘어진다면 다음도 넘어진다"만 말한 셈이에요.

연습 문제

1. 짝수와 홀수의 합은 홀수임을 직접 증명하세요.
2. 대우를 이용해 "$n^2$이 홀수이면 $n$도 홀수"임을 증명하세요.
3. 귀납법으로 $1 + 3 + 5 + \cdots + (2n-1) = n^2$을 증명하세요.
4. "모든 소수는 홀수다"를 반박하세요.
5. 리스트의 합을 구하는 반복문의 불변식을 말해 보세요.

정답

1. 짝수 $2m$과 홀수 $2n + 1$의 합은 $2(m + n) + 1$이므로 홀수예요.
2. 대우는 "$n$이 짝수이면 $n^2$도 짝수"예요. $n = 2k$이면 $n^2 = 4k^2 = 2(2k^2)$이라 짝수예요.
3. 기저: $n = 1$이면 $1 = 1^2$. 귀납: $1 + \cdots + (2k - 1) = k^2$이라 하면, 양변에 $2k + 1$을 더해 $k^2 + 2k + 1 = (k+1)^2$이 돼요.
4. 반례 2. 2는 소수이면서 짝수예요.
5. "매 반복을 시작할 때 합계 변수는 지금까지 본 원소들의 합이다."

다음 강의

수학 기초 트랙의 마지막 강의는 이산수학과 그래프 이론이에요. 지하철 노선, SNS의 친구 관계, 웹페이지의 링크처럼 "연결"을 다루는 수학이에요. 알고리즘과 네트워크, 추천 시스템으로 가는 다리가 돼요.