모던지 / 수학 / 이산수학 3강. 수학적 귀납법과 재귀

이산수학 3강. 수학적 귀납법과 재귀

무한을 일일이 확인할 수는 없습니다. 그러나 첫 도미노와 "넘어지면 다음 것도 넘어진다"는 규칙만 있으면, 무한 전체를 단 두 줄로 정복합니다.

풀고 시작

문제 1. 수학적 귀납법이 "지금까지 해가 떴으니 내일도 뜬다"는 식의 경험적 귀납과 결정적으로 다른 점은?

이름과 달리 수학적 귀납법은 연역입니다. 시작 사례가 참이고 각 단계의 전달이 참이면 모든 자연수에 대한 결론은 필연적으로 참이며, 반례 가능성이 남지 않죠. 경험적 귀납은 아무리 사례를 쌓아도 다음 사례를 보장하지 못한다는 점에서 논리적 지위가 전혀 다릅니다.

도미노의 논리

자연수 전체에 대한 명제, 예컨대 "1부터 n까지의 합은 n(n+1)/2이다"를 어떻게 증명할까요. 무한한 n을 하나씩 확인할 수는 없습니다. 수학적 귀납법(mathematical induction)은 이 무한을 단 두 단계로 압축합니다. 첫째, 기초 단계: n = 1일 때 명제가 참임을 보입니다. 둘째, 귀납 단계: n = k일 때 참이라고 가정하면 n = k+1일 때도 참임을 보입니다. 이 둘이 확보되면 명제는 모든 자연수에서 참입니다. 도미노 비유가 정확합니다. 첫 도미노를 넘어뜨렸고(기초), 어떤 도미노든 넘어지면 다음 도미노를 쓰러뜨린다면(귀납), 모든 도미노는 넘어지죠.

이름 때문에 생기는 오해 하나를 정리하겠습니다. 흄의 귀납 문제가 겨냥한 경험적 귀납은 "관찰된 사례들에서 관찰되지 않은 사례로" 건너뛰는 추론이고, 그 다리에는 논리적 보증이 없습니다. 반면 수학적 귀납법은 두 전제가 성립하면 결론이 필연적으로 따라 나오는 완전한 연역입니다. 자연수의 구조 자체(모든 수는 1에서 시작해 하나씩 더해 도달됩니다)가 이 추론을 보증하며, 페아노 공리계는 아예 귀납법을 자연수의 정의에 공리로 넣습니다.

하노이의 탑: 재귀로 풀기

1883년 프랑스 수학자 뤼카가 고안한 퍼즐이 있습니다. 기둥 세 개와 크기가 다른 원판 n개가 있고, 원판은 한 번에 하나씩만 옮기며 큰 원판을 작은 원판 위에 올릴 수 없습니다. 원판 전체를 다른 기둥으로 옮기는 것이 목표죠. 뤼카는 "64개의 황금 원판을 다 옮기면 세계가 끝난다"는 사원의 전설까지 곁들여 퍼즐을 팔았습니다.

n개를 옮기는 방법을 직접 설계하려면 막막하지만, 재귀(recursion)로 생각하면 세 줄이 됩니다. 위의 n−1개를 보조 기둥으로 옮기고, 가장 큰 원판을 목표 기둥으로 옮기고, n−1개를 그 위로 옮깁니다. n개 문제를 n−1개 문제 둘로 환원한 것이죠. 이동 횟수를 세면 점화식 T(n) = 2T(n−1) + 1이 나오고, 풀면 T(n) = 2ⁿ − 1입니다. 이 공식이 모든 n에서 옳다는 보증이 바로 귀납법입니다. 재귀가 풀이를 만들고 귀납법이 그 풀이를 증명하죠. 둘은 같은 구조의 앞면과 뒷면입니다. 참고로 원판 64개면 2⁶⁴ − 1, 약 1,845경 번의 이동이 필요합니다. 1초에 하나씩 옮겨도 5천억 년이 넘으니 전설은 안전합니다.

피보나치와 점화식

수열을 "n번째 항을 이전 항들로 정의하는 규칙", 즉 점화식(recurrence relation)으로 표현하는 것도 재귀적 사고입니다. 가장 유명한 예가 피보나치 수열이죠. 1202년 피사의 레오나르도(훗날 피보나치라 불립니다)는 『산반서』에서 토끼 번식 문제를 냈고, 그 답이 1, 1, 2, 3, 5, 8, 13, …으로 이어지는 수열, 즉 F(n) = F(n−1) + F(n−2)였습니다. 이 단순한 규칙에서 놀라운 성질들이 자랍니다. 이웃한 두 항의 비율은 황금비 φ ≈ 1.618로 수렴하고, 해바라기 씨앗과 솔방울의 나선 개수에 피보나치 수가 나타납니다. 점화식은 미래를 한 번에 주지 않고 직전 상태로부터 매번 계산하게 한다는 점에서, 이산적 세계의 미분방정식이라 할 만합니다.

재귀적 사고와 컴퓨터과학

재귀가 컴퓨터과학의 핵심인 이유는 명확합니다. 큰 문제를 같은 모양의 작은 문제로 줄이는 것이 프로그래밍의 근본 전략이기 때문이죠. 정렬 알고리즘의 대표인 병합 정렬과 퀵 정렬은 배열을 쪼개 같은 방식으로 정렬하는 분할 정복이고, 파일 시스템의 폴더 탐색은 폴더 안의 폴더를 같은 절차로 도는 재귀이며, 프로그래밍 언어의 문법 자체가 재귀적으로 정의됩니다(식 안에 식이 들어가죠). 함수가 자기 자신을 호출해도 무한히 돌지 않는 이유는 귀납법과 같은 구조 덕분입니다. 기저 사례(base case)가 도미노의 첫 장이고, 자기 호출이 귀납 단계입니다. 기저 사례를 빠뜨린 재귀가 무한 루프로 죽는 것은, 첫 도미노를 넘어뜨리지 않은 귀납 증명이 아무것도 증명하지 못하는 것과 같습니다. 다음 강에서는 존재를 세지 않고 증명하는 또 다른 무기, 비둘기집 원리를 만납니다.

인출 문제

문제 1. 수학적 귀납법의 두 단계는 무엇일까요?

n = 1에서 명제가 참임을 보이는 기초 단계와, n = k에서 참이면 n = k+1에서도 참임을 보이는 귀납 단계가 전부입니다. 이 둘이 성립하면 자연수의 구조에 의해 모든 n에서 참이 보장되죠. 사례 수집이나 반례 부재 확인은 경험적 방법이지 귀납법이 아닙니다.

문제 2. 하노이의 탑에서 원판 n개의 최소 이동 횟수가 만족하는 점화식은?

n−1개를 보조 기둥으로 옮기고(T(n−1)), 가장 큰 원판을 한 번 옮기고(+1), n−1개를 다시 그 위로 옮깁니다(T(n−1)). 그래서 2T(n−1) + 1이고, 풀면 2의 n제곱 빼기 1입니다. 세 번째 보기는 피보나치의 점화식이죠.

문제 3. 피보나치 수열의 유래와 성질로 옳은 것은?

피사의 레오나르도가 산반서에서 낸 토끼 문제의 답이 이 수열이며, 각 항은 앞의 두 항의 합입니다. 황금비는 수열의 결과로 나타나는 극한이지 수열의 기원이 아니죠. 뤼카는 하노이의 탑의 고안자로, 별개의 인물 맥락입니다.

문제 4. 재귀 함수가 무한히 돌지 않기 위해 반드시 필요한 것은?

재귀는 문제를 점점 작게 만들다가 기저 사례에서 멈춰야 합니다. 기저 사례가 없거나 도달 불가능하면 호출이 끝나지 않죠. 이것은 귀납 증명에서 기초 단계가 빠지면 아무것도 증명되지 않는 것과 정확히 대응하는 구조입니다.

생각해볼 질문 (정답 없음)

"수학적 귀납법"이라는 이름은 오해를 부르는 잘못된 작명일까요, 아니면 유한한 확인으로 무한을 다룬다는 점에서 경험적 귀납과 닮은 데가 있을까요.

이전: 2강 그래프 이론 · 다음: 4강 비둘기집 원리와 램지 이론

이 문서를 언급함

← 이산수학 2강. 그래프 이론: 점과 선의 세계 ← 이산수학 4강. 비둘기집 원리와 램지 이론 ← 수학

모던지 · 궁금하면 모던지 GitHub · 2026-09-10