도미노를 1억 개 세워 놓고 "전부 넘어진다"를 확인하려면 1억 개를 다 봐야 할까요? 아니에요. 두 가지만 확인하면 돼요. ① 첫 번째 도미노를 넘어뜨린다. ② 어떤 도미노든 넘어지면 바로 다음 것도 넘어지도록 세워져 있다. 이 두 문장이면 1억 번째도, 1조 번째도 넘어져요. 무한히 많은 경우를 유한한 두 단계로 증명하는 이 방법이 수학적 귀납법이고, "다음 항은 이전 항으로부터"라고 수열을 정의하는 것이 귀납적 정의예요. 둘은 같은 생각의 앞면과 뒷면이에요.
파스칼은 『산술삼각형론』(1654년 집필, 1665년 출간)에서 삼각형의 성질을 증명하며 "첫 줄에서 성립하고, 어떤 줄에서 성립하면 다음 줄에서도 성립한다"는 논법을 명시적으로 썼어요. 오늘날 교과서의 수학적 귀납법 서술은 이 형식이에요. 300년 뒤 컴퓨터 과학은 같은 생각으로 "프로그램이 모든 입력에 대해 옳다"를 증명해요.
🔁 귀납적 정의 — 다음 항은 이전 항으로부터
수열을 "$n$번째 항은 이것"(일반항)이 아니라 "첫 항은 이것, 다음 항은 이전 항으로 이렇게"로 정하는 방법이에요. 첫 항과 규칙을 고르고 항이 만들어지는 것을 보세요.
$a_1$1
✅ 귀납적 정의 (점화식)
첫째항 $a_1$ (때로는 $a_2$까지)과, 이웃한 항 사이의 관계식 $a_{n+1}=f(a_n)$을 주면 수열이 정해진다. 관계식을 점화식이라고 한다.
점화식
무슨 수열인가
$a_{n+1}-a_n=d$ (또는 $2a_{n+1}=a_n+a_{n+2}$)
등차수열 — 이웃한 항의 차가 일정 (가운데 항이 평균)
$a_{n+1}\div a_n=r$ (또는 $a_{n+1}^2=a_na_{n+2}$)
등비수열 — 이웃한 항의 비가 일정 (가운데 항의 제곱이 양옆의 곱)
$a_{n+1}=a_n+f(n)$
차가 $n$에 따라 변하는 수열 (계차)
$a_{n+2}=a_{n+1}+a_n$
앞 두 항의 합 (피보나치)
$a_1=2$, $a_{n+1}=3a_n-2$ 로 정의된 수열의 $a_4$는?
1규칙을 그대로 따라간다: $a_2=3\cdot2-2=4$.
2$a_3=3\cdot4-2=10$, $a_4=3\cdot10-2=28$.
$a_4=28$
⚠️ 이 교육과정의 범위
점화식에서 항을 차례로 만드는 것과 어떤 수열인지 알아보는 것까지가 범위예요. $a_{n+1}=3a_n-2$ 같은 점화식의 일반항을 구하는 특수 기법은 다루지 않아요. 물으면 "따라가며 계산"이 답이에요.
➗ 분수로 된 점화식도 따라가면 된다
분모에 $a_n$ 이 있어도 하는 일은 같다. 규칙을 그대로 따라가며 한 항씩 만든다. 예 — $a_1=2$, $a_{n+1}=\dfrac{a_n}{a_n+2}$ ① $a_2=\dfrac{2}{2+2}=\dfrac24=\dfrac12$ ② $a_3=\dfrac{1/2}{1/2+2}=\dfrac{1/2}{5/2}=\dfrac15$ — 번분수는 분자·분모에 같은 수를 곱해 정리한다(여기서는 2를 곱해 $\frac{1}{5}$). ③ $a_4=\dfrac{1/5}{1/5+2}=\dfrac{1/5}{11/5}=\dfrac1{11}$ 실점 지점 두 곳 — 분모가 $a_n+2$ 인지 $a_n$ 인지 먼저 정확히 읽는 것, 그리고 분모를 통분하지 않고 그냥 더해 버리는 것이다. 한 항씩 값을 적어 두면 둘 다 막힌다.
🧩 수학적 귀납법 — 도미노 두 문장
"모든 자연수 $n$에 대해 $P(n)$이 성립한다"를 증명하고 싶어요. 도미노를 보세요. ① 첫 개를 넘어뜨리기(재생 버튼) → ② 넘어지면 다음도 넘어진다는 것이 확인되면 끝까지 넘어져요.
두 문장이 참이면 $n$이 아무리 커도 넘어진다
✅ 수학적 귀납법
자연수 $n$에 대한 명제 $P(n)$이 (ⅰ) $n=1$일 때 성립하고, (ⅱ) $n=k$일 때 성립한다고 가정하면 $n=k+1$일 때도 성립한다 는 것을 보이면, $P(n)$은 모든 자연수 $n$에 대해 성립한다.
🔑 읽는 법
(ⅰ)은 첫 도미노, (ⅱ)는 "간격이 충분히 좁다"는 확인이에요. (ⅱ)에서 $P(k)$를 가정하는 것이 핵심이에요. "$k$번째가 넘어졌다면"이라는 가정 아래 $k+1$번째를 넘어뜨리는 거니까요. 이 가정을 쓰지 않은 증명은 귀납법이 아니에요.
첫 증명 — 등차수열의 합
모든 자연수 $n$에 대하여 $1+2+\cdots+n=\dfrac{n(n+1)}2$ 임을 증명하시오.
(ⅰ) $n=1$: 좌변 $=1$, 우변 $=\dfrac{1\cdot2}2=1$. 성립.
(ⅱ) $n=k$일 때 성립한다고 가정: $1+2+\cdots+k=\dfrac{k(k+1)}2$.
$n=k+1$: 양변에 $k+1$을 더하면 좌변은 $1+\cdots+k+(k+1)$, 우변은 $\dfrac{k(k+1)}2+(k+1)=\dfrac{(k+1)(k+2)}2$. 이것은 공식에 $n=k+1$을 넣은 꼴. 성립.
(ⅰ), (ⅱ)에 의해 모든 자연수 $n$에 대해 성립 ∎
⚠️ 흔한 실수
(ⅱ)에서 $n=k+1$일 때의 식을 먼저 써 놓고 그것을 이용하는 것 — 증명할 것을 가정하는 순환 논법이에요. 가정할 수 있는 것은 $P(k)$뿐이고, 목표 $P(k+1)$은 $P(k)$에서 만들어내야 해요.
🎯 목표 식을 먼저 적어 둔다
(ⅱ) 단계에서 헤매지 않는 가장 쉬운 방법은, 손을 대기 전에 도착점을 종이에 적어 두는 것이다. ① 공식의 $n$ 자리에 $k+1$ 을 넣어 목표 식을 쓴다 ② 가정한 $P(k)$ 를 쓴다 ③ ②에서 출발해 ①로 간다 예 — $1^3+2^3+\cdots+n^3=\left\{\dfrac{n(n+1)}2\right\}^2$ 에서 목표는 $\left\{\dfrac{(k+1)(k+2)}2\right\}^2$ 이다($n$ 에 $k+1$ 을 넣고 $(k+1)+1=k+2$ 로 정리한 것). 가정한 우변에 $(k+1)^3$ 을 더하면 $\dfrac{k^2(k+1)^2}4+(k+1)^3=\dfrac{(k+1)^2(k+2)^2}4$ 로 목표와 같아진다. 목표를 안 적으면 어디까지 정리해야 하는지를 모른 채 식을 굴리게 된다. 등식·배수·부등식 세 유형 모두 같다.
🧮 증명 연습 — 세 가지 유형
등식·배수·부등식. 세 유형 모두 뼈대는 같아요: (ⅰ) $n=1$ 확인 → (ⅱ) $P(k)$ 가정 → $P(k+1)$을 만든다. 다른 것은 "만드는 방법"뿐이에요.
(ⅱ) $k\ge5$에서 $2^k\gt k^2$ 가정. $2^{k+1}=2\cdot2^k\gt2k^2$. 그런데 $k\ge5$이면 $2k^2-(k+1)^2=k^2-2k-1=(k-1)^2-2\gt0$ 이므로 $2k^2\gt(k+1)^2$. 따라서 $2^{k+1}\gt(k+1)^2$. 성립.
$n\ge5$인 모든 자연수에 대해 성립 ∎
🔑 세 유형의 공통 기술
$P(k+1)$의 식 안에서 $P(k)$의 식을 찾아내는 것. 등식은 "더하기", 배수는 "빼내기", 부등식은 "가정으로 바꿔치기 후 크기 비교". 그 뒤에 남는 것만 정리하면 끝.
🔢 지수가 든 배수 증명 — 빼내는 방법은 같다
밑이 든 식도 뼈대는 ②와 같다. $P(k+1)$ 안에서 $P(k)$ 를 찾아내고 남는 것을 본다. 예 — $5^n-1$ 은 $4$ 의 배수이다. (ⅰ) $n=1$: $5-1=4$. 4의 배수. ✓ (ⅱ) $5^k-1=4m$ ($m$은 자연수) 가정. $5^{k+1}-1=5\cdot5^k-1=\underbrace{5(5^k-1)}_{\text{가정한 부분}}+4=5\cdot4m+4=4(5m+1)$ 4의 배수. 성립. ∎ 🔑 가르는 요령 — $5\cdot5^k-1$ 에서 $5^k-1$ 을 만들려면 $5$ 를 묶고 남는 만큼을 뒤에 더한다: $5\cdot5^k-1=5(5^k-1)+5-1$. 다항식에서 $3(k^2+k+1)$ 을 뒤에 남겼던 것과 같은 손놀림이다. 가정을 $5^k=4m+1$ 로 바꿔 대입해도 같은 답이 나온다. 어느 쪽이든 가정을 반드시 쓴다는 것이 핵심이다.
🌐 세상 속으로
📌 어른이 되어도 기억할 것
무한을 유한한 두 단계로. "처음이 성립한다 + 이어진다"면 끝까지 성립한다. 도미노 하나면 기억된다.
재귀: "다음은 이전으로부터"는 컴퓨터가 문제를 푸는 기본 방식이고, 귀납법은 그 프로그램이 옳다는 증명이다.
귀납법에서 가정을 쓰지 않았다면 증명이 아니다. 논리적 글쓰기의 기본 — 무엇을 가정했고 무엇을 보였는가.
💡 인사이트 — 대수의 끝, 그다음
여기까지가 대수 전부예요. 지수·로그(폭발과 그 반대말), 삼각함수(원과 파동), 수열(규칙과 합). 다음 과목 미적분Ⅰ은 "가까워진다"에서 시작해 변화율(미분)과 넓이(적분)를 다뤄요. 이 단원의 "다음 항 = 이전 항 + 변화"가 그대로 "다음 순간 = 지금 + 변화율 × 시간"이 돼요.
🏠 귀납과 재귀가 보이는 곳
🧩
도미노
첫 개 + 간격
🪜
계단
한 칸 오를 수 있으면 끝까지
🌀
피보나치
해바라기 씨·나선의 배열
📁
폴더 속 폴더
재귀 구조
💰
잔액 갱신
다음 달 = 이번 달 × 1.0X + 입금
🧬
세대
다음 세대는 이전 세대로부터
🏭 산업과 직업
💻
소프트웨어 검증 반복문·재귀 함수가 "모든 입력에 대해 옳다"는 것을 귀납법으로 증명한다. 항공·의료 소프트웨어의 안전성 검증이 이 논리. 🎓 컴퓨터공학 · 소프트웨어공학
🔐
암호·보안 암호 알고리즘의 성질을 모든 크기에 대해 증명할 때 귀납법이 기본 도구. 🎓 정보보안 · 수학
📈
시뮬레이션 날씨·주가·감염 모델은 점화식(다음 상태 = 이전 상태로부터)을 컴퓨터로 수백만 번 돌리는 것. 🎓 응용수학 · 데이터사이언스