수학적 귀납법 (mathematical induction)

너, 끝이 보이지 않게 늘어선 도미노를 떠올려 보자. 한 줄이 지평선 너머까지 이어져 있어서 세어 볼 수도 없다. 누가 너한테 묻는다. 이 도미노가 전부 다 쓰러지겠냐고. 무식하게 답하려면 첫 번째가 쓰러지나 보고, 두 번째도 보고, 세 번째도 보고… 영원히 끝나지 않는다. 무한히 많으니까. 그런데 너는 단 두 가지만 확인하고도 자신 있게 말할 수 있다. 첫째, 맨 앞 도미노를 내가 손으로 민다. 둘째, 어느 자리에 있든 한 놈이 쓰러지면 반드시 바로 뒤엣놈을 건드리도록 간격이 맞춰져 있다. 이 둘만 참이면 끝이다. 첫 놈이 쓰러지니 둘째가 쓰러지고, 둘째가 쓰러지니 셋째가… 너는 천 번째도 백만 번째도 직접 안 봤지만 전부 쓰러진다는 걸 안다. 무한을 통째로 잡은 거다.

이게 바로 오늘 이야기의 핵심인데, 수학에서는 이 도미노 묘기를 수학적 귀납법이라 부른다. 이름은 좀 얄궂다. 귀납이라 해놓고 실은 한 치의 빈틈도 없는 연역이거든. 흔히 말하는 귀납, 그러니까 까마귀 백 마리가 검으니 모든 까마귀가 검을 거라는 식의 '많이 봤으니 아마 그럴 것'과는 전혀 다르다. 여기엔 '아마'가 없다. 두 단추만 채우면 무한 전체가 100퍼센트 확정된다.

씨앗은 멀리 거슬러 올라간다. 유클리드도 이미 '소수는 무한히 많다'를 증명하며 비슷한 사다리 오르기를 썼고, 16세기 이탈리아의 프란체스코 마우롤리코는 처음 n개의 홀수를 더하면 n의 제곱이 된다는 걸 이 방식으로 보였다. 1 더하기 3은 4, 거기에 5를 더하면 9, 7을 더하면 16. 1, 4, 9, 16… 전부 제곱수다. 그런데 이걸 처음으로 또렷한 '방법'으로 세운 사람은 17세기 프랑스의 블레즈 파스칼이다. 그는 자기 이름이 붙은 그 숫자 삼각형의 성질을 증명하면서, 한 줄이 참이면 다음 줄도 참이라는 톱니바퀴를 명시적으로 돌렸다. 다만 정작 '귀납(induction)'이라는 이름은 이들이 붙인 게 아니다. 그 말을 이 절차에 가져다 쓴 건 17세기 영국의 존 월리스였고, 오늘 우리가 쓰는 '수학적 귀납법'이라는 명칭을 못 박은 사람은 그보다 한참 뒤인 19세기의 오거스터스 드 모르간이다. 그러니까 이건 누가 허공에서 발명한 게 아니라, 수학자들이 무한을 마주칠 때마다 더듬더듬 쓰던 손버릇을 여러 사람이 대를 이어 또렷한 절차로 다듬고 명명해 준 쪽에 가깝다.

진짜로 단단해진 건 훨씬 나중이다. 19세기 말 이탈리아의 주세페 페아노가 자연수가 도대체 무엇인가를 다섯 개의 공리로 깎아낼 때, 마지막 다섯 번째 공리 자리에 바로 이 귀납법을 박아 넣었다. 즉 '0에서 참이고, n에서 참이면 n+1에서도 참인 성질은 모든 자연수에서 참이다'를 자연수의 정의 자체에 못 박은 거다. 도미노 묘기가 한낱 요령에서, 자연수라는 세계가 서 있는 주춧돌로 승격된 순간이다.

이 도구를 가장 멀리까지 끌고 간 무대는 뜻밖에도 컴퓨터다. 컴퓨터 안의 거의 모든 게 '반복'과 '자기 자신을 부르는 구조'로 돌아가는데, 그게 멈추는지 옳게 끝나는지를 사람이 일일이 다 돌려 볼 수가 없다. 그래서 프로그램이 맞다는 걸 '증명'할 때 바로 이 귀납법을 쓴다. 한 바퀴 돌 때 성립하던 조건이 다음 바퀴에도 그대로 유지됨을 보이면, 몇 번을 돌든 안전하다는 게 따라 나온다. 더 흥미로운 건, 이걸 기계가 검산하게 만들려고 사람들이 사고의 윗틀까지 갈아 끼웠다는 점이다. 증명을 더 이상 줄글 설득이 아니라, 기초 단계와 n에서 n+1로 가는 단계라는 정해진 모양의 절차로 바꿔 적자, 코크나 리안 같은 증명 보조기가 그 사다리를 칸칸이 검사해 줄 수 있게 됐다.

그러니 너가 '경우가 끝도 없이 많아서 도저히 다 확인 못 하겠다' 싶은 벽을 만나거든, 전부 세려 들지 마라. 딱 두 가지만 붙잡아라. 맨 처음 한 칸이 참인가. 그리고 아무 칸이나 참이라고 가정하면 바로 다음 칸도 반드시 참이 되는가. 이 두 단추만 채워지면, 나머지 무한은 네가 손대지 않아도 줄줄이 알아서 쓰러진다.