00. 무한을 무너뜨리는 도미노, 귀납법
1. 학습 목표 (Learning Objectives)
- 인간의 유한한 머리로 ‘무한(Infinity)’의 모든 케이스를 단 두 번의 논리적 스텝(Step 1, Step 2) 작동만으로 전부 증명해 내는 마법, 수학적 귀납법(Mathematical Induction) 의 본질을 파악합니다.
- 끝없이 나열된 ‘도미노의 연쇄 폭발 현상’ 을 통해 점화식이라는 논리의 도화선이 어떻게 작동하는지 시각적으로 이해합니다.
2. 1억 개의 명제를 증명하는 방법
“모든 자연수에 대하여 이러이러한 공식이 무조건 100% 성립한다!”라는 수학 명제가 여러분에게 주어졌습니다.
어떻게 증명하시겠습니까? 가장 순수한 무식한 방법은 $n=1$ 일 때 식에 대입해 보고, 맞으면 “오 통과!” $n=2, n=3, n=4$ 일 때도 대입해 보고 만족하면 “오케이 다 맞네~”라고 하는 것입니다.
하지만 누군가 시비를 겁니다.
“야, 네가 $n=1$만부터 $9,999$만까지 대입해서 100% 맞다고 쳐도, $n$이 $1$억이 됐을 때 그 공식이 맞을지 네가 계산 안 해봤잖아? 어떻게 1억이 넘어가는 무한의 우주에서도 이 공식이 안 깨진다고 장담해?”
인간은 무한번 계산을 죽을 때까지 할 수 없습니다. 이때 인간을 구원하기 위해 프랑스의 천재 블레즈 파스칼(Blaise Pascal) 이 체계화하고, 이탈리아의 수학자 주세페 페아노(Giuseppe Peano) 가 공리계로 꽝꽝 못 박은 절대 논리가 바로 ‘수학적 귀납법’입니다.
3. 영원히 쓰러지는 도미노 폭발 엔진
위 그림처럼 우주 끝까지 나열된 수만 개의 도미노 블록을 내가 직접 일일이 다 손가락으로 툭툭 쳐서 쓰러뜨리려면 수십 년이 걸릴 겁니다. 하지만 나는 단 두 개의 철칙 만 증명하면, 소파에 누워 팝콘을 먹으면서도 “저기 저 10억 번째 도미노도 알아서 반드시 쓰러질 것이다!”라고 100% 장담할 수 있습니다.
- [규칙 1. 시작의 방아쇠] : 내가 맨 앞에 있는 제1번 도미노($n=1$)를 확실하게 손으로 밀어서 쓰러뜨렸다!
- [규칙 2. 간격의 폭발] : 앞번호 도미노 하나($n=k$)가 쓰러지기만 하면, 얘는 무조건 바로 뒷번호 도미노($n=k+1$)를 연쇄 타격해서 쓰러뜨릴 수 있는 완벽한 간격(논리) 으로 떨어져 있다!
“1번이 쓰러지네? 그럼 2번에 의해 2번도 쓰러지겠군! 2번이 쓰러졌어? 그럼 2번에 의해 3번도 쓰러지네? 3번이… 무한 반복!”
수학적 귀납법은 바로 인류가 ‘무한대’의 증명을 유한한 ‘연쇄 물리 역학’ 하나로 대여(Hacking)한 수학 역사상 가장 아름다운 치트키입니다.
4. 학습 정리 (Summary)
- 무한 증명의 한계: 자연수 집합처럼 끝이 없는 데이터를 대상으로 100% 참임을 증명하려면, 숫자를 영원히 대입할 수 없기에 새로운 논리 엔진이 필요합니다.
- 수학적 귀납법의 본질(도미노 효과): 첫 단추($n=1$)가 확실히 채워졌다는 사실과, 현재 항($k$)이 다음 항($k+1$)으로 발동될 수밖에 없는 연결 고리의 공식만 수학적으로 증명해 주면 세상 모든 숫자에 대해 스스로 무한 연쇄 증명 폭발이 일어나는 강력한 검증 메커니즘입니다.