# 34주차 · 강의 — 예제 · 연습 · 해설

## 예제 — 점화식 증명을 함께 만들기

완성된 증명을 먼저 보이지 않는다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께, 예제 2.3은 설계부터 스스로 한다.

### 예제 2.1 — 추측에서 확정까지: 하노이 탑

**문제.** $a_1 = 1$, $a_{n+1} = 2a_n + 1$로 정의된 수열의 닫힌 꼴을 찾아 증명하시오. (원판 $n$장의 하노이 탑을 옮기는 데 필요한 최소 이동 횟수가 이 점화식을 만족한다.)

**설계 — 쓰기 전에 정하는 두 가지.** 증명을 쓰기 전에 출발점과 도착점을 정한다. 이번에는 도착점이 아직 문장으로 존재하지 않으므로, 사이클 ①~③으로 먼저 만든다.

|  | **말** | **수식 번역** |
|---|---|---|
| 가정 (출발점) | 점화식과 초기 조건 | $a_1 = 1$, $a_{k+1} = 2a_k + 1$ (근거 ①) |
| 목표 (도착점) | 닫힌 꼴 공식 | $a_n = \underline{\quad(?)\quad}$ — ①~③으로 만들어 채운다 |

**①단계 — 앞 항을 계산한다.** §1.2의 표에서 이미 다섯 항을 계산했다: $a_1 = 1$, $a_2 = 3$, $a_3 = 7$, $a_4 = 15$, $a_5 = 31$.

:::{container} quotebox
**확인 9.** 이 다섯 수를 2의 거듭제곱 $2, 4, 8, 16, 32$와 나란히 놓아 보자.

각 자리에서 두 수의 차는 얼마인가. 목표 칸에 들어갈 공식은 무엇인가?
:::

:::{admonition} 답
:class: quotebox dropdown

$2 - 1 = 1$, $4 - 1 = 3$, $8 - 1 = 7$, $16 - 1 = 15$, $32 - 1 = 31$ — 차가 전부

$1$이다. 따라서 추측은 $a_n = 2^n - 1$이고, 이것이 목표 칸에 들어간다.

③단계의 검산은 아직 쓰지 않은 항에서 한다: $a_6 = 2a_5 + 1 = 63 = 2^6 - 1$ ✓.

여기까지가 발견이고, 지금부터가 증명이다.
:::

**②단계 — 도구를 고르고 선언한다.** 점화식이 $a_{k+1}$을 $a_k$ 하나로만 나타내므로 보폭은 1이다. 보통 귀납법이면 충분하고 기초도 하나면 된다(§1.5).

:::{container} quotebox
**확인 10.** 첫 문장을 완성해 보자:

"$n$에 대한 $\underline{\qquad}$으로 증명한다. 보일 명제는 $P(n)$: $\underline{\qquad}$이다."
:::

:::{admonition} 답
:class: quotebox dropdown

"$n$에 대한 **수학적 귀납법**으로 증명한다. 보일 명제는 $P(n)$: $a_n = 2^n - 1$이다."

추측이 여기서 처음으로 $P(n)$ 자리에 앉는다 — §1.1에서 비어 있던 그 자리다.
:::

**③단계 — 기초를 확인한다.** 최소 사례에서 좌변과 우변을 **각각** 계산해 비교한다. 좌변은 초기 조건에서, 우변은 추측한 공식에서 온다.

:::{container} quotebox
**확인 11.** [기초] 문장을 완성해 보자:

"$n = 1$일 때 좌변은 $a_1 = \underline{\quad}$이고, 우변은 $2^1 - 1 = \underline{\quad}$이므로 같다."
:::

:::{admonition} 답
:class: quotebox dropdown

좌변 $a_1 = 1$(초기 조건), 우변 $2^1 - 1 = 1$. 두 값이 같으므로 $P(1)$이 참이다.

좌변을 우변에 맞춰 "$a_1 = 2^1 - 1$이니까 맞다"라고 한 줄로 적는 경우가 많은데,

그러면 두 값을 실제로 계산했다는 증거가 답안에 남지 않는다 — 등식을 옮겨 적은

것과 확인한 것을 구별할 수 없다. 양쪽을 따로 계산해 비교한다.
:::

**④단계 — 귀납 가정을 받고 도착점을 적어 둔다.** 가정과 도착점을 나란히 적어 두면 어느 방향으로 변형할지가 정해진다.

:::{container} quotebox
**확인 12.** [귀납] 문장을 완성해 보자:

"$a_k = \underline{\quad}$이라 가정하자(귀납 가정). 보일 것은 $a_{k+1} = \underline{\quad}$이다."
:::

:::{admonition} 답
:class: quotebox dropdown

가정 $a_k = 2^k - 1$, 도착점 $a_{k+1} = 2^{k+1} - 1$.

도착점은 추측 공식의 $n$ 자리에 $k+1$을 넣어 만든다 — 창작이 아니라 대입이다.
:::

**⑤단계 — 점화식으로 시작해 가정을 꽂는다.** 도착점 쪽 대상은 $a_{k+1}$인데, 손에 든 정보는 $a_k$에 대한 것이다. 둘을 잇는 등식은 점화식뿐이다(§1.3).

:::{container} quotebox
**확인 13.** 계산 줄을 완성해 보자:

"$a_{k+1} = \underline{\qquad}$ (점화식) $= 2(\underline{\qquad}) + 1$ (귀납 가정) $= \underline{\qquad}$."
:::

:::{admonition} 답
:class: quotebox dropdown

$a_{k+1} = 2a_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1$.

첫 등호가 점화식이고 둘째 등호가 귀납 가정의 투입이다. 가정을 실제로 쓴

지점에 "(귀납 가정)"이라고 표시하는 습관은 31주차 §1.5에서 세웠다.
:::

**⑥단계 — 원리를 인용하며 마감한다.**

:::{container} quotebox
**확인 14.** 마지막 문장을 완성해 보자:

"따라서 $P(k+1)$이 성립한다. $\underline{\qquad}$에 의해 모든 자연수 $n$에 대해 $a_n = 2^n - 1$이다. $\blacksquare$"
:::

:::{admonition} 답
:class: quotebox dropdown

"수학적 귀납법에 의해" — 원리의 이름을 적고 결론을 다시 진술한다.

이 문장이 있어야 "$k$에 대해 보였다"가 "모든 $n$에 대해 참"으로 승격된다.

추측이 정리가 되는 자리가 정확히 여기다.
:::

**완성본.** 방금 만든 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다.

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| 앞 다섯 항은 $1, 3, 7, 15, 31$이고, 이는 $2^1 - 1, \dots, 2^5 - 1$이다. 따라서 $a_n = 2^n - 1$로 추측한다. | 사이클 ①②. 검사할 $P(n)$을 만드는 단계이며, 아직 증명이 아니다. |
| $n$에 대한 수학적 귀납법으로 증명한다. 보일 명제는 $P(n)$: $a_n = 2^n - 1$이다. | 도구 선언. 점화식의 보폭이 1이므로 보통 귀납으로 충분하다(§1.5). |
| **[기초]** $n = 1$: 좌변 $a_1 = 1$(초기 조건), 우변 $2^1 - 1 = 1$. 같으므로 $P(1)$이 참이다. | 양변을 각각 계산해 비교한다. 초기 조건이 여기서 소비된다. |
| **[귀납]** $a_k = 2^k - 1$이라 가정하자(귀납 가정). 보일 것은 $a_{k+1} = 2^{k+1} - 1$이다. | 가정과 도착점을 나란히 적어 변형 방향을 고정한다. |
| $a_{k+1} = 2a_k + 1$ (점화식) $= 2(2^k - 1) + 1$ (귀납 가정) $= 2^{k+1} - 2 + 1 = 2^{k+1} - 1$. | 첫수는 점화식 대입 — 그래야 귀납 가정을 꽂을 자리가 생긴다(§1.3). |
| 따라서 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $a_n = 2^n - 1$이다. $\blacksquare$ | 원리를 인용하며 마감. 추측이 정리로 승격되는 문장이다. |

**이 여섯 줄이 "모든" $n$을 처리하는 이유.** 완성본의 $k$에 3을 넣어 읽어 보자: "$a_3 = 7 = 2^3 - 1$이라 가정하자. $a_4 = 2a_3 + 1 = 2(2^3 - 1) + 1 = 2^4 - 2 + 1 = 2^4 - 1$." $k = 7$을 넣어도, $k = 100$을 넣어도 같은 네 등호가 그대로 성립한다.

:::{container} quotebox
**확인 15.** 이 증명의 어느 줄도 $k$가 특정한 수라는 사실을 쓰지 않았다.

그렇다면 ①②에서 계산한 다섯 항의 역할은 무엇이었는가?
:::

:::{admonition} 답
:class: quotebox dropdown

후보를 만드는 재료였다. 증명의 본문(기초와 귀납)은 다섯 항 중 $a_1$ 하나만

쓰고, 나머지 넷은 한 줄도 인용되지 않는다.

그래서 다섯 항이 전부 맞았다는 사실은 증명의 근거가 아니다 — 후보를 고르게

해 준 관찰일 뿐이다. 사이클에서 ①②③과 ④의 지위가 다르다는 것이 이렇게

확인된다.
:::

### 예제 2.2 — 피보나치 합 공식

**명제.** 모든 자연수 $n$에 대해 $F_1 + F_2 + \cdots + F_n = F_{n+2} - 1$이다.

이번에는 설계만 함께 하고, 증명은 완성된 산문으로 본다. 합 기호로는 좌변을 $\sum_{i=1}^{n} F_i$로 적는다(31주차 §1.7의 표기이며, "아이가 1부터 엔까지 에프 아이의 합"으로 읽는다).

:::{container} quotebox
**확인 16.** 예제 2.1의 번역표에 해당하는 세 칸을 아래 세 줄에 정해 보자.

도구: 귀납 단계가 참조하는 과거는 몇 칸인가 $\to$ 보폭 $\underline{\quad}$, 기초 $\underline{\quad}$개.

가정(출발점): $\sum_{i=1}^{k} F_i = \underline{\qquad}$.

목표(도착점): $\sum_{i=1}^{k+1} F_i = \underline{\qquad}$.
:::

:::{admonition} 답
:class: quotebox dropdown

보폭 1, 기초 1개. 좌변이 누적합이므로 $k+1$항까지의 합은 $k$항까지의 합에서

한 항만 더하면 되고, 참조하는 과거는 $P(k)$ 하나다 — §1.5의 한 칸 모드다.

가정: $\sum_{i=1}^{k} F_i = F_{k+2} - 1$.

목표: $\sum_{i=1}^{k+1} F_i = F_{k+3} - 1$ (공식의 $n$ 자리에 $k+1$을 대입).
:::

:::{container} quotebox
**확인 17.** 목표 쪽 좌변에서 마지막 항 $F_{k+1}$을 떼어 내면

$(F_{k+2} - 1) + F_{k+1}$이 나온다. 이것을 $F_{k+3} - 1$로 바꾸는 등식은 무엇인가?
:::

:::{admonition} 답
:class: quotebox dropdown

점화식 $F_{k+3} = F_{k+2} + F_{k+1}$이다(정의 34.2에 $n = k+3$을 대입, $k+3 \ge 3$이므로 적용 가능).

한 칸 모드에서도 점화식은 쓰이되, 가정 쪽이 아니라 **결론 쪽에서** 두 항을

하나로 합치는 데 쓰인다(§1.5).
:::

**증명.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변은 $F_1 = 1$이고 우변은 $F_3 - 1 = 2 - 1 = 1$이므로 같다. **[귀납]** $\sum_{i=1}^{k} F_i = F_{k+2} - 1$이라 가정하자. 보일 것은 $\sum_{i=1}^{k+1} F_i = F_{k+3} - 1$이다. 마지막 항을 분리하면

$$
\sum_{i=1}^{k+1} F_i = \left(\sum_{i=1}^{k} F_i\right) + F_{k+1} = (F_{k+2} - 1) + F_{k+1} \ \text{(귀납 가정)} = (F_{k+1} + F_{k+2}) - 1 = F_{k+3} - 1
$$

이고, 마지막 등호는 점화식 $F_{k+3} = F_{k+2} + F_{k+1}$이다. 따라서 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 명제가 성립한다. $\blacksquare$

(검산: $n = 4$일 때 좌변 $1 + 1 + 2 + 3 = 7$, 우변 $F_6 - 1 = 8 - 1 = 7$ ✓.)

이 증명에서 대수 변형은 괄호를 옮긴 것뿐이고, 실제로 일을 한 것은 점화식이다. 점화식 수열의 귀납이 대개 이런 모양이다 — 계산이 어려운 것이 아니라 **어느 등식을 언제 꺼내는가**가 전부다.

### 예제 2.3 — 두 칸 모드: $F_n < 2^n$

**명제.** 모든 자연수 $n$에 대해 $F_n < 2^n$이다.

이번에는 설계부터 스스로 해 보자.

:::{container} quotebox
**확인 18.** 도구와 기초 개수를 정해 보자. $F_{k+1}$을 점화식으로 풀면

어느 항들이 나오는가. 그 항들에 귀납 가정을 쓰려면 어떤 가정이 필요한가.

기초는 몇 개인가.
:::

:::{admonition} 답
:class: quotebox dropdown

$F_{k+1} = F_k + F_{k-1}$이므로 $k$와 $k-1$ 두 자리가 나온다. $P(k)$ 하나만

가정해서는 $F_{k-1}$에 쓸 것이 없으므로 **강한 귀납법**을 선언하고

"$1 \sim k$에서 성립"을 가정해야 한다.

보폭이 2이므로 기초는 **2개**($n = 1$, $n = 2$)다 — 점화식이 $k+1 \ge 3$에서만

적용되므로 $n = 1, 2$는 전달 장치가 만들어 낼 수 없다(§1.5).
:::

:::{container} quotebox
**확인 19.** 귀납 가정을 두 곳에 쓰면 $F_{k+1} < 2^k + 2^{k-1}$까지 온다.

도착점은 $2^{k+1}$이다. 이 둘을 잇는 부등식 한 줄을 만들어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$2^{k-1} < 2^k$이므로 $2^k + 2^{k-1} < 2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$이다.

이 한 줄이 **연결 부등식**이다(32주차에서 세운 이름). 귀납 가정이 데려다준

중간값 $2^k + 2^{k-1}$에서 도착점 $2^{k+1}$까지는 저절로 이어지지 않으므로,

그 사이를 잇는 부등식을 손으로 놓아야 증명이 닫힌다.
:::

**증명.** $n$에 대한 강한 귀납법으로 증명한다. **[기초]** $n = 1$일 때 $F_1 = 1 < 2 = 2^1$이고, $n = 2$일 때 $F_2 = 1 < 4 = 2^2$이다. (점화식이 두 칸 전까지 참조하므로 기초를 두 개 확인한다.) **[귀납]** $k \ge 2$인 $k$에 대해 $1 \sim k$의 모든 자리에서 명제가 성립한다고 가정하자. 보일 것은 $F_{k+1} < 2^{k+1}$이다. $k + 1 \ge 3$이므로 점화식이 적용되어

$$
F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} \ \text{(귀납 가정을 } k,\ k-1 \text{ 두 자리에)} < 2^k + 2^k = 2^{k+1}
$$

이다. 따라서 $P(k+1)$이 성립한다. 강한 귀납법에 의해 모든 자연수 $n$에 대해 $F_n < 2^n$이다. $\blacksquare$

**자가 점검.** 귀납 단계에서 $P(k)$와 $P(k-1)$ **둘**을 썼으므로 보폭이 2이고, 그래서 기초가 2개다. 기초가 $n = 1$ 하나뿐이었다면 $F_2 < 2^2$이 어디서도 확보되지 않는다 — 33주차 문제 17에서 본 붕괴가 그대로 재연된다. 이 증명은 표 없이 산문으로 적었다. 실전의 증명은 처음부터 끝까지 이런 산문이고, 이번 주의 목표는 이 산문을 백지에서 재현하는 것이다.

### 관찰 — 세 증명의 같은 뼈대

예제 2.1, 2.2, 2.3은 소재가 하노이$\cdot$합$\cdot$크기로 다르지만 뼈대가 같다. 각 단계에 어느 문장이 대응하는지 빈칸을 채워 보자.

:::{container} quotebox
**확인 20.** 예제 2.3의 산문에서 각 단계에 해당하는 문장(또는 식)을 찾아 보자.

① 도구 선언과 보폭 확인: $\underline{\qquad}$

② [기초]: $\underline{\qquad}$

③ [귀납] 가정과 도착점: $\underline{\qquad}$

④ 점화식 대입과 가정 투입: $\underline{\qquad}$

⑤ 마감: $\underline{\qquad}$
:::

:::{admonition} 답
:class: quotebox dropdown

① "$n$에 대한 강한 귀납법으로 증명한다."(보폭 2를 확인했으므로 강한 귀납.)

② "$F_1 = 1 < 2 = 2^1$이고 $F_2 = 1 < 4 = 2^2$이다." — 두 개.

③ "$1 \sim k$에서 성립한다고 가정하자. 보일 것은 $F_{k+1} < 2^{k+1}$이다."

④ "$F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} < 2^{k+1}$" — 첫 등호가 점화식,

첫 부등호가 귀납 가정 투입, 둘째 부등호가 연결 부등식.

⑤ "강한 귀납법에 의해 모든 자연수 $n$에 대해 $F_n < 2^n$이다."

예제 2.1과 2.2도 정확히 이 다섯 걸음이다 — 2.1은 ①에서 보통 귀납을 골랐고

②의 기초가 하나일 뿐이다.
:::

방금 확인한 뼈대에 이름을 붙인다.

:::{admonition} 백지 암기 대상
:class: keybox

**점화식 귀납의 5단계 틀**

① 점화식의 보폭을 세어 도구(보통 귀납 / 강한 귀납)와 기초 개수를 정하고 선언한다 $\to$ ② **[기초]** 보폭만큼의 최소 사례에서 양변을 각각 계산해 확인한다 $\to$ ③ **[귀납]** 가정을 받고 도착점 $P(k+1)$의 구체적 모양을 적어 둔다 $\to$ ④ **점화식을 대입해** 도착점 대상을 과거로 바꾼 뒤 귀납 가정을 투입하고(표시를 단다), 필요하면 연결 부등식으로 도착점까지 잇는다. 누적합 명제라면 마지막 항을 먼저 분리해 가정을 넣고, 점화식은 남은 두 항을 합치는 마지막 등호에서 쓴다(§1.5) $\to$ ⑤ 원리를 인용하며 마감한다.
:::

31주차의 5단계 틀과 다른 곳은 ①과 ④ 두 군데다. ①에 보폭 세기가 들어가고, ④에 점화식 대입이 들어간다 — 두 칸 모드에서는 그것이 첫수를 "대상 분리"에서 "점화식 대입"으로 바꾸고, 한 칸 모드에서는 첫수가 여전히 마지막 항 분리이되 그 뒤의 마지막 등호를 점화식이 맡는다.

## 빈칸 사다리 — 지지대를 하나씩 빼며

필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.

### 훈련 1 ●○○ — 수식 빈칸

**명제.** $a_1 = 3$, $a_{n+1} = a_n + 4$이면 모든 자연수 $n$에 대해 $a_n = 4n - 1$이다.

**증명.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $a_1 = 3$, 우변 $4 \cdot 1 - 1 = 3$이므로 같다. **[귀납]** $a_k = \underline{\quad(1)\quad}$이라 가정하자. 그러면 점화식에 의해

$$
a_{k+1} = a_k + 4 = \big(\underline{\quad(1)\quad}\big) + 4 \ \text{(귀납 가정)} = 4k + 3 = 4(k+1) - \underline{\quad(2)\quad}
$$

이므로 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $a_n = 4n - 1$이다. $\blacksquare$

### 훈련 2 ●●○ — 수식과 근거를 함께

이번에는 구조 낱말과 근거 문장도 빈칸이다.

**명제.** 모든 자연수 $n$에 대해 $F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$이다 (짝수 번째 항의 합).

**증명.** $n$에 대한 $\underline{\quad(1)\quad}$으로 증명한다. **[기초]** $n = 1$일 때 좌변 $F_2 = 1$, 우변 $F_3 - 1 = \underline{\quad(2)\quad}$이므로 같다. **[귀납]** $F_2 + F_4 + \cdots + F_{2k} = \underline{\quad(3)\quad}$이라 가정하자. 보일 것은 $F_2 + \cdots + F_{2k+2} = \underline{\quad(4)\quad}$이다. 마지막 항 $F_{2k+2}$를 분리하면

$$
F_2 + \cdots + F_{2k} + F_{2k+2} = \big(\underline{\quad(3)\quad}\big) + F_{2k+2} \ \text{(귀납 가정)} = \underline{\quad(5)\quad} - 1
$$

이고, 마지막 등호의 근거는 $\underline{\quad(6)\quad}$이다. 따라서 $P(k+1)$이 성립한다. 마감 문장은 $\underline{\quad(7)\quad}$이다. $\blacksquare$

### 훈련 3 ●●● — 뼈대만 남기고

이번에는 5단계 틀의 각 칸을 통째로 채운다.

**명제.** 모든 자연수 $n$에 대해 $F_n \le 2^{n-1}$이다.

**증명의 뼈대.**

- ① 도구 선언과 기초 개수: $\underline{\quad(1)\quad}$
- ② [기초]: $\underline{\quad(2)\quad}$
- ③ [귀납] 가정과 도착점: $\underline{\quad(3)\quad}$
- ④ 점화식 대입, 가정 투입, 연결 부등식: $\underline{\quad(4)\quad}$
- ⑤ 마감: $\underline{\quad(5)\quad}$

(예제 2.3보다 상계가 한 단계 낮아졌으므로 연결 부등식도 더 빡빡하다. $2^{k-1} + 2^{k-2}$를 공통인수로 묶어 $2^k$와 비교해 보면 된다. 이 훈련이 문제 15와 18의 예행연습이다.)

## 연습문제 (20문항)

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 증명 문제는 반드시 보폭부터 세고 시작한다(§1.5).

:::{admonition} 이번 주의 채점 기준
:class: quotebox

답이 아니라 **근거**가 점수다. "$a_n = 2^n - 1$이다(맞음)"는 0점이고,

"앞 항으로 추측한 뒤 기초와 귀납 단계를 각각 확인했고, 귀납 단계에서 점화식을

쓴 지점이 표시되어 있다"가 만점이다. 특히 이번 주에는 두 가지를 따로 본다 —

① 기초의 개수가 보폭과 맞는가 ② 귀납 단계에서 점화식을 쓴 지점과 귀납 가정을

쓴 지점이 각각 표시되어 있는가.

난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.
:::

### 기본 ●○○

**1.** 피보나치 수열을 $F_{10}$까지 나열하시오. 그리고 $F_{11}, F_{12}$를 점화식으로 구하시오.

:::{admonition} 힌트
:class: quotebox dropdown

앞의 두 항을 더해 다음 항을 만든다. 마지막 두 항은 나열을 외워 적지 말고

$F_{11} = F_{10} + F_9$처럼 점화식의 꼴을 그대로 적은 뒤 계산한다.
:::

**2.** [백지] 추측 $\to$ 귀납 확정 사이클(①~④)을 쓰시오.

:::{admonition} 힌트
:class: quotebox dropdown

네 단계 중 셋은 발견이고 하나는 증명이다. 그 하나가 몇 번인지, 그리고 그

단계의 첫수가 무엇인지까지 적으면 완전한 답이다(§1.6).
:::

**3.** $b_1 = 5$, $b_{n+1} = b_n - 2$의 앞 다섯 항을 계산하고 닫힌 꼴을 추측하시오 (증명은 문제 7).

:::{admonition} 힌트
:class: quotebox dropdown

항마다 일정한 수가 빠지므로 등차 꼴 $b_n = (\text{첫 항}) + (n-1) \times (\text{공차})$를

먼저 세워 정리해 본다. 추측을 세운 뒤 아직 쓰지 않은 항에서 검산한다.
:::

**4.** 빈칸 훈련($a_n = 4n - 1$)을 백지에서 완성하시오.

:::{admonition} 힌트
:class: quotebox dropdown

빈칸을 외워 채우는 것이 아니라 다섯 단계 틀을 처음부터 다시 밟는다.

막히는 자리는 대개 마지막 변형 — $4k + 3$을 $4(k+1) - 1$로 다시 묶는 곳이다.
:::

**5.** 예제 2.1(하노이)을 백지에 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

①②의 추측 단계와 ④의 증명 단계를 종이 위에서 눈에 보이게 나눠 적는다.

증명 본문이 다섯 항 중 실제로 쓰는 것은 $a_1$ 하나뿐이다(확인 15).
:::

**6.** 예제 2.2(피보나치 합)를 백지에 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

귀납 단계의 첫 동작은 마지막 항 분리다. 그 뒤 귀납 가정을 넣고, 남은 두 항

$F_{k+1}$과 $F_{k+2}$를 점화식으로 합친다.
:::

### 표준 ●●○

**7.** 문제 3의 추측($b_n = 7 - 2n$)을 귀납법으로 확정하시오.

:::{admonition} 힌트
:class: quotebox dropdown

훈련 1과 같은 구조이고 공차의 부호만 다르다. 기초에서 좌변 $b_1$과 우변

$7 - 2 \cdot 1$을 각각 계산해 비교하는 것부터 시작한다.
:::

**8.** $c_1 = 2$, $c_{n+1} = 2c_n$의 닫힌 꼴을 추측하고 귀납으로 증명하시오.

**9.** 모든 자연수 $n$에 대해 $F_1^2 + F_2^2 + \cdots + F_n^2 = F_n F_{n+1}$임을 증명하시오. (귀납 단계에서 공통인수 $F_{k+1}$ 묶기 $\to$ 점화식)

:::{admonition} 힌트
:class: quotebox dropdown

마지막 항 $F_{k+1}^2$을 더하면 $F_k F_{k+1} + F_{k+1}^2$이 된다. 두 항에

공통으로 들어 있는 것을 밖으로 빼면 괄호 안이 $F_k + F_{k+1}$이 되고,

그 자리에서 점화식이 한 번에 작동한다.
:::

**10.** 예제 2.3($F_n < 2^n$)을 백지에 재현하시오 — 기초 2개의 이유를 한 줄 덧붙일 것.

:::{admonition} 힌트
:class: quotebox dropdown

덧붙일 한 줄의 뼈대: "귀납 단계가 $F_k$와 $F_{k-1}$ 두 자리를 쓰므로 보폭이 2이고,

점화식은 $k+1 \ge 3$에서만 적용되므로 $n = 1, 2$는 …".
:::

:::{admonition} 점화식을 두 번 펼치기 — 문제 11에서 처음 쓰는 기술
:class: quotebox

지금까지는 점화식을 한 번만 대입해 $F_{k+1} = F_k + F_{k-1}$로 만들었다.

그런데 귀납 가정이 $F_{3k}$에 대한 것이고 도착점이 $F_{3k+3}$이면, 한 번

대입해서는 $F_{3k+2} + F_{3k+1}$이 나올 뿐 가정을 꽂을 자리($F_{3k}$)가

보이지 않는다. 이럴 때는 나온 항 중 하나에 점화식을 **한 번 더** 적용한다:

$F_{3k+2} = F_{3k+1} + F_{3k}$. 그러면 $F_{3k}$가 드러난다.

점화식은 몇 번이든 다시 쓸 수 있는 등식이라는 것(근거 ①)이 이 기술의 전부다.

(문제 11의 지시문에 나오는 IH는 귀납 가정(inductive hypothesis)의 약자이며,

32주차 §1.2의 표기와 같다.)
:::

**11.** 모든 자연수 $n$에 대해 $F_{3n}$은 짝수임을 증명하시오. (힌트: $F_{3(k+1)} = F_{3k+3} = F_{3k+2} + F_{3k+1} = 2F_{3k+1} + F_{3k}$ — 점화식을 두 번 펼쳐 IH 항을 노출)

:::{admonition} 힌트
:class: quotebox dropdown

점화식을 한 번 대입해 나온 항 중 첨자가 큰 쪽에 다시 한 번 대입한다. 그러면

$F_{3k}$가 드러나고, 거기에 귀납 가정을 꽂는다. 마무리는 1주차의 짝수 정의다 —

$F_{3k} = 2m$으로 적고 전체를 $2 \times (\text{정수})$ 꼴로 묶는다.
:::

:::{admonition} 이 문제가 빌려 쓰는 사실 — 공약수와 차 (문제 12)
:class: quotebox

문제 12의 귀납 단계는 다음 성질을 쓴다: $d$가 두 정수를 모두 나누면 그 차도

나눈다 — 곧 $d \mid x$이고 $d \mid y$이면 $d \mid (x - y)$이다. 이것은 2주차

문제 7에서 증명한 명제이므로 근거 ④로 그대로 인용할 수 있다.

22주차 문제 11("$n$과 $n+1$의 공통 약수는 $\pm 1$뿐")이 같은 성질로 증명되었고,

문제 12는 그 논법을 피보나치의 이웃 두 항에 옮겨 놓은 것이다.
:::

**12.** 연속한 두 피보나치 수는 서로소임을 — 즉 $F_n$과 $F_{n+1}$의 공통 약수는 $\pm 1$뿐임을 — 귀납법으로 증명하시오. (귀납 단계 힌트: $d \mid F_{k+1}$이고 $d \mid F_{k+2}$이면 $d \mid (F_{k+2} - F_{k+1}) = F_k$ — 22주차 문제 11과 같은 논법)

:::{admonition} 힌트
:class: quotebox dropdown

공약수 $d$를 하나 잡고 시작한다. 두 배수의 차도 배수라는 2주차 문제 7을 쓰면

$d$가 더 작은 첨자의 항 $F_k$도 나누고, 그 순간 $d$는 $F_k$와 $F_{k+1}$의

공약수가 되어 귀납 가정이 발동한다. 첨자에 $F_k$가 보여도 소비하는 가정은

$P(k)$ 하나이므로 기초도 하나다(§1.5).
:::

**13.** $a_1 = 1$, $a_{n+1} = \dfrac{a_n}{1 + a_n}$의 앞 네 항을 계산해 닫힌 꼴을 추측하고 귀납으로 증명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

분수 계산이 부담스러우면 각 항을 통분해 한 번에 정리한다. 네 항이 나오면

분자가 전부 같다는 것이 먼저 보이고, 그 다음 분모의 규칙이 보인다.
:::

**14.** (카시니 항등식) 모든 $n \ge 2$에 대해 $F_{n+1} F_{n-1} - F_n^2 = (-1)^n$임을 증명하시오. (기초 $n = 2$; 귀납 단계에서 $F_{k+2} = F_{k+1} + F_k$를 대입해 $-\big(F_{k+1}F_{k-1} - F_k^2\big)$ 꼴로 재배열)

:::{admonition} 힌트
:class: quotebox dropdown

도착점은 $(-1)^{k+1}$이고 귀납 가정은 $(-1)^k$이므로, 목표는 계산 결과를

**가정의 부호를 뒤집은 꼴**로 만드는 것이다. 곧 $-\big(F_{k+1}F_{k-1} - F_k^2\big)$을

만들면 끝난다. 전개 도중 $F_{k+1} - F_k$가 보이면 그것을 $F_{k-1}$로 되감는다.
:::

### 도전 ●●●

:::{admonition} 연결 부등식 — 도전 문제가 공통으로 요구하는 한 줄
:class: quotebox

부등식 명제의 귀납에서 귀납 가정이 데려다주는 곳은 도착점이 아니라 그 근처다.

예제 2.3에서 가정은 $F_{k+1} < 2^k + 2^{k-1}$까지만 데려다주었고, 거기서

도착점 $2^{k+1}$까지는 손으로 부등식 한 줄을 놓아야 했다. 그 한 줄이 **연결

부등식**이며, 생략하면 증명이 닫히지 않는다(32주차 문제 17에서 해부했다).

아래 문제 15와 18이 요구하는 것이 전부 이 한 줄이고, 두 문제의 차이는 그 줄이

부등호로 닫히는가($\frac52 \ge \frac94$) 등호로 닫히는가($\varphi + 1 = \varphi^2$ —

$\varphi$는 그리스 문자 "파이"로 읽으며 황금비를 나타내는 기호로, 문제 18에서 정의한다)뿐이다.
:::

**15.** 모든 자연수 $n$에 대해 $F_n \ge \left(\dfrac{3}{2}\right)^{n-2}$임을 강한 귀납법으로 증명하시오. (기초 2개; 연결 부등식: $\left(\frac32\right)^{k-2} + \left(\frac32\right)^{k-3} \ge \left(\frac32\right)^{k-1}$ — 공통인수로 묶어 $\frac32 + 1 \ge \frac94$ 확인. 지수 꼴이 문제 18과 한 칸 다른 것은 이 명제의 지수가 $n-1$이 아니라 $n-2$이기 때문이다)

:::{admonition} 힌트
:class: quotebox dropdown

기초에서 지수가 음수가 되는 것을 겁내지 않는다 — $n = 1$이면

$\left(\frac32\right)^{-1} = \frac23$이고, $1 \ge \frac23$은 참이다.

귀납 단계에서는 두 항의 공통인수로 지수가 작은 쪽을 묶어 낸다.
:::

**16.** 모든 자연수 $n$에 대해 $F_1 + F_3 + F_5 + \cdots + F_{2n-1} = F_{2n}$(홀수 번째 항의 합)임을 증명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

훈련 2(짝수 번째 합)와 같은 구조이며 우변에 $-1$이 없다. 마지막 항을

분리해 귀납 가정을 넣으면 $F_{2k} + F_{2k+1}$이 남고, 점화식 한 번으로 닫힌다.
:::

**17.** (진단) 다음 답안의 결함을 지적하시오.

:::{container} quotebox
"명제: 모든 $n$에서 $F_n < 2^n$. 증명: [기초] $F_1 = 1 < 2$ ✓. [귀납] $F_k < 2^k$이라 가정하자. $F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} < 2^{k+1}$. $\blacksquare$"

(예제 2.3과 어디가 다른가? 이 답안이 무너지는 지점을 정확히 — $F_{k-1}$에 무엇을 쓸 권리가 있는가, 그리고 $k+1 = 2$일 때 점화식은?)
:::

:::{admonition} 힌트
:class: quotebox dropdown

결함을 찾는 순서는 두 단계다. ① 귀납 단계의 각 부등호 옆에 "이 줄의 근거는

어느 가정인가"를 적어 본다 — 가정한 적 없는 것을 쓴 줄이 드러난다.

② 귀납 단계가 작동하는 $k$의 범위를 적고, 그 범위가 덮지 못하는 $n$을 센다.
:::

**18.** 황금비 $\varphi = \frac{1 + \sqrt5}{2}$는 $\varphi^2 = \varphi + 1$을 만족한다. 이를 직접 확인하시오. 그리고 모든 자연수 $n$에 대해 $F_n \le \varphi^{n-1}$임을 강한 귀납법으로 증명하시오. (연결: $\varphi^{k-1} + \varphi^{k-2} = \varphi^{k-2}(\varphi + 1) = \varphi^{k-2} \cdot \varphi^2 = \varphi^k$ — 등호로 떨어진다)

:::{admonition} 힌트
:class: quotebox dropdown

기호 $\varphi$는 그리스 문자 "파이"로 읽는다. 첫 확인은 양변을 각각 계산해

비교하는 것이다 — 좌변은 $\left(\frac{1+\sqrt5}{2}\right)^2$을 전개하고,

우변은 $\frac{1+\sqrt5}{2} + 1$을 통분한다. 두 결과가 같은 분수로 나오면 된다.

증명 부분은 문제 15와 뼈대가 같고 연결 부등식만 등호가 된다.
:::

**19.** 수열을 $d_1 = 1$, $d_{n+1} = d_n + (2n + 1)$로 정의하자. (a) 앞 다섯 항을 계산해 닫힌 꼴을 추측하시오. (b) 귀납으로 확정하시오. (c) 이 결과가 31주차의 어느 공식과 같은 내용인지 지적하시오.

:::{admonition} 힌트
:class: quotebox dropdown

(a)에서 더해지는 수 $2n+1$이 $n = 1, 2, 3, \dots$에 따라 $3, 5, 7, \dots$로

바뀐다는 것을 먼저 적어 둔다. 다섯 항이 나오면 패턴은 곧바로 보인다.

(c)는 "무엇을 무엇에 차례로 더한 결과인가"를 말로 옮기면 답이 나온다.
:::

**20.** (서술) (a) "점화식 수열의 성질 증명에서 귀납법이 자연스러운 이유"를 정의의 구조와 연결해 두 문장 이내로 쓰시오. (b) $F_{n+1}/F_n$을 $n = 2, \dots, 8$에서 소수점 셋째 자리까지 계산하고, 어떤 값에 다가가는 듯한지 관찰을 기록하시오 (황금비 $\varphi \approx 1.618$ — 증명은 45주차로 미룬다).

:::{admonition} 힌트
:class: quotebox dropdown

(a)는 §1.3의 대응표를 문장으로 풀어 쓰면 된다 — 정의의 두 조각과 증명의

두 조각이 각각 무엇에 대응하는지 지목한다.

(b)는 나눗셈을 일곱 번 하는 작업이다. 값을 세로로 나열해 두면 크고 작음이

번갈아 나타나는 것이 눈에 들어온다.
:::

## 백지 재현 — 복습 프로토콜

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.

**1차 시도 (4일차) — 틀 카드 허용.** 점화식 귀납의 5단계 틀(§2 관찰)과 추측 $\to$ 귀납 확정 사이클(§1.6)만 펴 놓고, 예제 2.1과 2.3을 처음부터 끝까지 적는다. 정의 34.2와 본문의 다른 부분은 보지 않는다.

**2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다:

- [ ] 정의 34.1(점화식과 초기 조건)의 뜻을 쓰고, 둘 중 하나가 없으면 무엇이 결정되지 않는지 설명했다.
- [ ] 정의 34.2(피보나치 수열)을 초기 조건 두 개와 적용 범위 $(n \ge 3)$까지 조각 그대로 썼다.
- [ ] 추측 $\to$ 귀납 확정 사이클 ①~④를 쓰고, 어느 단계가 증명인지 지목했다.
- [ ] 예제 2.1(하노이)$\cdot$2.2(합 공식)$\cdot$2.3($F_n < 2^n$)을 백지에 처음부터 끝까지 재현했다.
- [ ] 재현한 증명마다 보폭을 세어 기초 개수를 맞췄고, 점화식을 쓴 지점과 귀납 가정을 쓴 지점에 각각 표시를 달았다.
- [ ] 카시니 항등식을 $n = 2$와 $n = 3$에서 검산했다.

**막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다.

| **막힌 지점** | **처방** |
|---|---|
| 닫힌 꼴을 무엇으로 추측할지 모르겠다 | §1.6 사이클 ①② — 2의 거듭제곱, 등차, 등비, 제곱수와 나란히 놓고 차를 본다 |
| 기초를 몇 개 둘지 모르겠다 | §1.5 모드 표 — **귀납 단계가 실제로 소비하는 가정의 개수**를 센다. $P(n)$이 항 하나에 대한 문장이면 그것이 곧 '가장 먼 과거'까지의 칸수이고, $P(n)$이 여러 항을 묶은 문장이면(문제 12$\cdot$14) 첨자에 $F_{k-1}$이 보여도 기초는 하나다 |
| 보통 귀납과 강한 귀납 중 무엇을 쓸지 모르겠다 | §1.5 — 소비하는 가정이 하나면 보통, 둘이면 강한 귀납($P(n)$이 두 항을 묶은 문장인 경우는 §1.5의 단서를 본다) |
| 귀납 단계의 첫 줄이 나오지 않는다 | §1.3 확인 3 — 첫수는 점화식 대입이고, 누적합 명제라면 마지막 항 분리가 먼저다 |
| 가정을 넣었는데 도착점까지 가지 않는다 | §2 예제 2.3 확인 19 — 연결 부등식 한 줄을 손으로 놓는다 |
| 가정을 꽂을 자리가 보이지 않는다 | 문제 11 앞 상자 — 점화식을 한 번 더 펼쳐 가정의 항을 드러낸다 |
| 추측이 맞는데 증명을 왜 하는지 모르겠다 | §1.6 확인 7과 1주차 문제 18 — 39개가 맞고 40번째에서 무너진 사례 |

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

## 해설

각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

### 빈칸 사다리 — 훈련 1

(1) $4k - 1$  (2) $1$

※ (2)가 이 훈련의 핵심이다. $4k + 3$까지 계산해 놓고 멈추면 도착점 꼴 $4(k+1) - 1$과 생김새가 달라 증명이 닫히지 않은 것처럼 보인다. $4k + 3$에서 $4(k+1) = 4k + 4$를 만들려면 $1$을 빼야 하므로 $4k + 3 = 4(k+1) - 1$이다. 목표 꼴이 정확히 나올 때까지 변형을 밀어붙이는 것도 기술이다(1주차 문제 7).

### 빈칸 사다리 — 훈련 2

(1) 수학적 귀납법  (2) $2 - 1 = 1$  (3) $F_{2k+1} - 1$  (4) $F_{2k+3} - 1$ (5) $F_{2k+3}$  (6) 점화식 $F_{2k+3} = F_{2k+2} + F_{2k+1}$ (근거 ①) (7) 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$이다.

※ (5)(6)이 한 덩어리다. 귀납 가정을 넣으면 $(F_{2k+1} - 1) + F_{2k+2}$가 되고, $-1$을 밖으로 밀어 두면 $F_{2k+1} + F_{2k+2}$가 남는다 — 이 둘은 이웃한 두 항이므로 점화식으로 $F_{2k+3}$이 된다. 한 칸 모드에서 점화식이 결론 쪽에서 작동하는 전형적인 모양이다(§1.5).

※ (7)을 빼면 증명이 닫히지 않는다. "$k$에 대해 보였다"를 "모든 $n$에 대해 참"으로 승격시키는 것이 원리를 인용하는 이 마지막 문장이기 때문이다(확인 14, §2 5단계 틀 ⑤).

### 빈칸 사다리 — 훈련 3

(1) $n$에 대한 강한 귀납법으로 증명한다. 점화식이 두 칸 전까지 참조하므로 기초는 2개다. (2) $n = 1$: $F_1 = 1 \le 2^0 = 1$ ✓. $n = 2$: $F_2 = 1 \le 2^1 = 2$ ✓. (3) $k \ge 2$에 대해 $1 \sim k$의 모든 자리에서 성립한다고 가정하자. 보일 것은 $F_{k+1} \le 2^k$이다. (4) $k+1 \ge 3$이므로 점화식이 적용되어 $F_{k+1} = F_k + F_{k-1} \le 2^{k-1} + 2^{k-2}$ (귀납 가정을 두 자리에)이고, 공통인수로 묶으면 $2^{k-1} + 2^{k-2} = 2^{k-2}(2 + 1) = 3 \cdot 2^{k-2} \le 4 \cdot 2^{k-2} = 2^k$이다. (5) 강한 귀납법에 의해 모든 자연수 $n$에 대해 $F_n \le 2^{n-1}$이다. $\blacksquare$

※ 예제 2.3의 $F_n < 2^n$보다 상계가 절반이므로 여유가 줄었고, 그래서 연결 부등식에서 $3 \le 4$라는 판정이 필요해졌다. 기초의 첫 자리에서 등호가 나오는 것도 확인해 둔다 — $F_1 = 2^0$이라 등호이고 $F_2 < 2^1$이라 진부등식이므로, 부등호를 $\le$로 두어야 $n = 1$에서도 명제가 참이다.

### 문제 1

**접근.** 나열은 정의대로 앞의 두 항을 더해 만든다. 마지막 두 항은 외운 목록에서 꺼내지 말고 점화식의 꼴을 그대로 적은 뒤 계산한다 — 이번 주 내내 쓸 습관이 "정의로 계산한다"이기 때문이다(확인 4).

**풀이.** $F_1 = 1$, $F_2 = 1$에서 시작해 차례로

$$
1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55
$$

가 $F_1$부터 $F_{10}$까지다. 이어서 점화식에 $n = 11$과 $n = 12$를 대입하면

$$
F_{11} = F_{10} + F_9 = 55 + 34 = 89, \qquad F_{12} = F_{11} + F_{10} = 89 + 55 = 144
$$

이다.

**검산.** $F_{12} = 144 = 12^2$이지만 이는 우연이고 규칙이 아니다 — $F_{13} = 233$은 제곱수가 아니다. 눈에 띄는 패턴을 만나면 다음 항에서 곧바로 검산하는 것이 사이클 ③단계의 습관이다.

### 문제 2

**접근.** §1.6의 상자를 그대로 재현하되, 네 단계를 나열하는 데서 그치지 않고 어느 단계가 증명이고 어느 단계가 아닌지까지 적는다. 그 구분이 이번 주의 핵심이므로 구분이 빠진 답은 절반만 쓴 것이다.

**풀이.** ① 앞 항을 여러 개 계산한다($a_1$부터 $a_5$ 정도). ② 패턴을 추측한다(등차인가, 등비인가, $2^n \pm 1$인가, 제곱수인가). ③ 추측을 아직 쓰지 않은 항에서 검산한다 — 어긋나면 ①로 돌아간다. ④ 귀납법으로 확정한다. [귀납]의 첫수는 점화식 대입이다(누적합 명제라면 마지막 항 분리가 먼저이고 그 뒤에 점화식이 온다).

이 중 증명은 ④ 하나뿐이고 ①②③은 발견이다. ①②③만으로 끝내면 1주차 문제 18의 $f(n) = n^2 + n + 41$처럼 39개가 맞고 40번째에서 무너지는 사태를 막을 수 없다.

**복기.** 사이클의 가치는 예시 관찰을 버리지 않고 제자리에 앉힌 데 있다. 예시는 후보를 만들고 귀납은 후보를 확정한다 — 두 언어의 분업이다.

### 문제 3

**접근.** 항마다 일정한 수 $2$가 빠지므로 등차수열이다. 등차의 닫힌 꼴은 "첫 항 + (지난 칸 수) $\times$ 공차"이고, 지난 칸 수는 $n - 1$이다.

**풀이.** 점화식대로 계산하면

$$
b_1 = 5,\quad b_2 = 3,\quad b_3 = 1,\quad b_4 = -1,\quad b_5 = -3
$$

이다. 등차 꼴로 세우면 $b_n = 5 + (n-1) \times (-2) = 5 - 2n + 2 = 7 - 2n$이므로 추측은 $b_n = 7 - 2n$이다.

**검산.** 아직 계산에 쓰지 않은 항에서 확인한다: $b_6 = b_5 - 2 = -5$이고 공식으로는 $7 - 12 = -5$ ✓. 추측이 살아남았으므로 문제 7에서 ④단계로 넘어간다.

### 문제 4

**접근.** 빈칸의 답을 외워 채우는 것이 아니라 5단계 틀을 처음부터 밟는다. 점화식 $a_{n+1} = a_n + 4$는 앞 항 하나만 참조하므로 보폭 1, 기초 1개다.

**풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변은 $a_1 = 3$(초기 조건), 우변은 $4 \cdot 1 - 1 = 3$이므로 같다. 따라서 $P(1)$이 참이다. **[귀납]** $a_k = 4k - 1$이라 가정하자(귀납 가정). 보일 것은 $a_{k+1} = 4(k+1) - 1$이다. 점화식에 의해

$$
a_{k+1} = a_k + 4 = (4k - 1) + 4 \ \text{(귀납 가정)} = 4k + 3 = 4(k+1) - 1
$$

이므로 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $a_n = 4n - 1$이다. $\blacksquare$

**복기.** 마지막 등호가 이 문제의 전부다. $4k + 3$은 도착점과 값은 같지만 꼴이 다르므로, 도착점의 꼴 $4(k+1) - 1$로 다시 묶어야 증명이 닫힌다. (검산: $n = 3$이면 $a_3 = 11$이고 $4 \cdot 3 - 1 = 11$ ✓.)

### 문제 5

**접근.** 추측 단계와 증명 단계를 종이 위에서 눈에 보이게 나눠 적는다. 증명 본문이 실제로 쓰는 것은 초기 조건 $a_1$과 점화식뿐이고, 나머지 네 항은 후보를 고르게 해 준 재료다(확인 15).

**풀이.** **[추측]** $a_1 = 1$, $a_2 = 3$, $a_3 = 7$, $a_4 = 15$, $a_5 = 31$이고, 이는 $2^1 - 1, 2^2 - 1, 2^3 - 1, 2^4 - 1, 2^5 - 1$이다. 따라서 $a_n = 2^n - 1$로 추측한다. (검산: $a_6 = 2 \cdot 31 + 1 = 63 = 2^6 - 1$ ✓.)

**[증명]** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $a_1 = 1$, 우변 $2^1 - 1 = 1$이므로 같다. **[귀납]** $a_k = 2^k - 1$이라 가정하자(귀납 가정). 보일 것은 $a_{k+1} = 2^{k+1} - 1$이다. 점화식에 의해

$$
a_{k+1} = 2a_k + 1 = 2(2^k - 1) + 1 \ \text{(귀납 가정)} = 2^{k+1} - 2 + 1 = 2^{k+1} - 1
$$

이므로 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $a_n = 2^n - 1$이다. $\blacksquare$

**복기.** 하노이 탑의 해석을 붙이면 점화식의 뜻이 보인다 — 원판 $n+1$장을 옮기려면 위 $n$장을 옮기고($a_n$회), 가장 큰 원판을 한 번 옮기고($1$회), 다시 $n$장을 옮겨야($a_n$회) 하므로 $a_{n+1} = 2a_n + 1$이다. 원판 64장이면 $2^{64} - 1$회다.

### 문제 6

**접근.** 한 칸 모드이므로 보폭 1, 기초 1개다. 귀납 단계의 첫 동작은 마지막 항 분리이고, 그 뒤 귀납 가정을 넣은 다음 남은 두 항을 점화식으로 합친다.

**풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변은 $F_1 = 1$이고 우변은 $F_3 - 1 = 2 - 1 = 1$이므로 같다. **[귀납]** $\sum_{i=1}^{k} F_i = F_{k+2} - 1$이라 가정하자(귀납 가정). 보일 것은 $\sum_{i=1}^{k+1} F_i = F_{k+3} - 1$이다. 마지막 항을 분리하면

$$
\sum_{i=1}^{k+1} F_i = \left(\sum_{i=1}^{k} F_i\right) + F_{k+1} = (F_{k+2} - 1) + F_{k+1} \ \text{(귀납 가정)} = (F_{k+1} + F_{k+2}) - 1 = F_{k+3} - 1
$$

이고 마지막 등호는 점화식이다. 따라서 $P(k+1)$이 성립하고, 수학적 귀납법에 의해 모든 자연수 $n$에 대해 명제가 성립한다. $\blacksquare$

**검산.** $n = 5$: 좌변 $1+1+2+3+5 = 12$, 우변 $F_7 - 1 = 13 - 1 = 12$ ✓.

**복기.** 이 증명에서 대수 변형은 괄호를 옮긴 것뿐이고 일을 한 것은 점화식이다. "어느 등식을 언제 꺼내는가"가 점화식 귀납의 실력이다.

### 문제 7

**접근.** 훈련 1과 같은 구조이고 공차의 부호만 다르다. 기초에서 좌변 $b_1$과 우변 $7 - 2 \cdot 1$을 각각 계산해 비교하는 것부터 시작한다.

**풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변은 $b_1 = 5$(초기 조건), 우변은 $7 - 2 \cdot 1 = 5$이므로 같다. **[귀납]** $b_k = 7 - 2k$라 가정하자(귀납 가정). 보일 것은 $b_{k+1} = 7 - 2(k+1)$이다. 점화식에 의해

$$
b_{k+1} = b_k - 2 = (7 - 2k) - 2 \ \text{(귀납 가정)} = 5 - 2k = 7 - 2 - 2k = 7 - 2(k+1)
$$

이므로 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $b_n = 7 - 2n$이다. $\blacksquare$

**복기.** 문제 3에서 만든 추측이 여기서 정리로 승격되었다. 문제 3의 검산 ($b_6 = -5$)은 증명의 근거가 아니라 후보를 살려 둔 관찰이었다는 점을 다시 확인한다. (검산: $n = 4$이면 $b_4 = -1$이고 $7 - 8 = -1$ ✓.)

### 문제 8

**접근.** 항마다 일정한 수 $2$가 곱해지므로 등비수열이다. 앞 항을 계산해 보면 $2, 4, 8, 16$이므로 2의 거듭제곱이 후보이고, 첨자와 지수가 맞는지 확인한다.

**풀이.** **[추측]** $c_1 = 2$, $c_2 = 2 \cdot 2 = 4$, $c_3 = 2 \cdot 4 = 8$, $c_4 = 2 \cdot 8 = 16$이므로 $c_n = 2^n$으로 추측한다. (검산: $c_5 = 32 = 2^5$ ✓.)

**[증명]** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $c_1 = 2$, 우변 $2^1 = 2$이므로 같다. **[귀납]** $c_k = 2^k$이라 가정하자(귀납 가정). 보일 것은 $c_{k+1} = 2^{k+1}$이다. 점화식에 의해

$$
c_{k+1} = 2c_k = 2 \cdot 2^k \ \text{(귀납 가정)} = 2^{k+1}
$$

이므로 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $c_n = 2^n$이다. $\blacksquare$

**복기.** 등차(훈련 1, 문제 7)와 등비(이 문제)의 증명은 첫수만 다르다 — 훈련 1과 문제 7에서는 점화식이 $+d$를 붙였고 여기서는 $\times r$를 붙인다. 고2 수열의 일반항 공식이 전부 이 방식으로 증명된다.

### 문제 9

**접근.** 한 칸 모드다. 마지막 항 $F_{k+1}^2$을 더하면 $F_k F_{k+1} + F_{k+1}^2$이 되는데, 두 항 모두 $F_{k+1}$을 갖고 있다. 밖으로 빼면 괄호 안이 $F_k + F_{k+1}$이 되고 그 자리에서 점화식이 작동한다.

**풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변은 $F_1^2 = 1$이고 우변은 $F_1 F_2 = 1 \cdot 1 = 1$이므로 같다. **[귀납]** $\sum_{i=1}^{k} F_i^2 = F_k F_{k+1}$이라 가정하자(귀납 가정). 보일 것은 $\sum_{i=1}^{k+1} F_i^2 = F_{k+1} F_{k+2}$이다. 마지막 항을 분리하면

$$
\sum_{i=1}^{k+1} F_i^2 = \left(\sum_{i=1}^{k} F_i^2\right) + F_{k+1}^2 = F_k F_{k+1} + F_{k+1}^2 \ \text{(귀납 가정)} = F_{k+1}\big(F_k + F_{k+1}\big) = F_{k+1} F_{k+2}
$$

이고 마지막 등호는 점화식 $F_{k+2} = F_{k+1} + F_k$이다. 따라서 $P(k+1)$이 성립하고, 수학적 귀납법에 의해 모든 자연수 $n$에 대해 명제가 성립한다. $\blacksquare$

**검산.** $n = 5$: 좌변 $1 + 1 + 4 + 9 + 25 = 40$, 우변 $F_5 F_6 = 5 \times 8 = 40$ ✓.

**복기.** 공통인수 묶기가 점화식을 부르는 자리를 만들었다. 합 공식(예제 2.2)에서는 덧셈이, 제곱합에서는 인수분해가 그 자리를 만든다 — 어느 쪽이든 목표는 같다: **이웃한 두 피보나치 수를 나란히 세워 점화식이 발동하게 하는 것.** (기하학적 해석: 한 변이 $F_1, F_2, \dots, F_n$인 정사각형들을 차례로 붙이면 $F_n \times F_{n+1}$ 직사각형이 빈틈없이 채워진다. 넓이를 두 방식으로 센 것이 이 항등식이다.)

### 문제 10

**접근.** 두 칸 모드다. 백지에서 재현할 때 무너지기 쉬운 자리는 기초 개수와 "$k \ge 2$"라는 범위 선언 두 곳이므로 그 둘을 먼저 적어 두고 시작한다.

**풀이.** $n$에 대한 강한 귀납법으로 증명한다. **[기초]** $n = 1$일 때 $F_1 = 1 < 2 = 2^1$이고, $n = 2$일 때 $F_2 = 1 < 4 = 2^2$이다. **[귀납]** $k \ge 2$인 $k$에 대해 $1 \sim k$의 모든 자리에서 성립한다고 가정하자. 보일 것은 $F_{k+1} < 2^{k+1}$이다. $k+1 \ge 3$이므로 점화식이 적용되어

$$
F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} \ \text{(귀납 가정을 두 자리에)} < 2^k + 2^k = 2^{k+1}
$$

이다. 따라서 $P(k+1)$이 성립하고, 강한 귀납법에 의해 모든 자연수 $n$에 대해 $F_n < 2^n$이다. $\blacksquare$

**덧붙이는 한 줄 (문제가 요구한 것).** 귀납 단계가 $F_k$와 $F_{k-1}$ 두 자리를 쓰므로 보폭이 2이고, 점화식은 $k+1 \ge 3$에서만 적용되므로 $n = 1$과 $n = 2$는 전달 장치가 만들어 낼 수 없다. 따라서 그 두 자리를 손으로 확인해야 한다.

**복기.** 두 칸 모드의 답안을 검사하는 두 질문은 고정되어 있다 — 가정 선언이 "$1 \sim k$"인가, 기초가 두 개인가. 문제 17이 이 두 질문을 그대로 채점 도구로 쓴다.

### 문제 11

**접근.** 도착점은 $F_{3k+3}$인데 귀납 가정은 $F_{3k}$에 대한 것이다. 점화식을 한 번만 대입하면 $F_{3k+2} + F_{3k+1}$이 나올 뿐 가정을 꽂을 자리가 없으므로, 나온 항 중 $F_{3k+2}$에 점화식을 **한 번 더** 적용해 $F_{3k}$를 드러낸다 (문제 11 앞 상자).

**풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 $F_3 = 2$이고 $2 = 2 \times 1$이므로 짝수이다. **[귀납]** $F_{3k}$가 짝수라고 가정하자(귀납 가정). 보일 것은 $F_{3(k+1)} = F_{3k+3}$이 짝수라는 것이다. 점화식을 두 번 펼치면

$$
F_{3k+3} = F_{3k+2} + F_{3k+1} = \big(F_{3k+1} + F_{3k}\big) + F_{3k+1} = 2F_{3k+1} + F_{3k}
$$

이다. 귀납 가정에 의해 $F_{3k} = 2m$인 정수 $m$이 존재하므로

$$
F_{3k+3} = 2F_{3k+1} + 2m = 2\big(F_{3k+1} + m\big)
$$

이고, $F_{3k+1} + m$은 정수이므로(근거 ②) $F_{3k+3}$은 짝수의 정의를 만족한다. 따라서 $P(k+1)$이 성립하고, 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $F_{3n}$은 짝수이다. $\blacksquare$

**검산.** $F_3 = 2$, $F_6 = 8$, $F_9 = 34$, $F_{12} = 144$ — 전부 짝수 ✓.

**복기.** 이 증명은 두 도구를 겹쳐 썼다. 점화식 두 번 펼치기가 가정의 자리를 만들었고, 1주차의 짝수 정의($2 \times$ 정수)가 결론의 꼴을 만들었다. 피보나치의 홀짝은 홀, 홀, 짝의 3주기로 반복되며, 나머지 절반 ($F_{3n+1}$과 $F_{3n+2}$가 홀수)도 같은 기법으로 증명된다.

### 문제 12

**접근.** 첨자에 $F_k$가 보여도 소비하는 가정은 $P(k)$ 하나이므로 기초도 하나다 — $P(n)$ 자체가 이웃한 두 항을 묶은 문장이기 때문이다(§1.5). 귀납으로 옮겨 간다. $F_{k+1}$과 $F_{k+2}$의 공약수 $d$를 잡으면, 점화식의 차 $F_{k+2} - F_{k+1} = F_k$ 때문에 $d$가 $F_k$도 나눈다. 그러면 $d$는 $F_k$와 $F_{k+1}$의 공약수가 되어 귀납 가정이 발동한다 — 새 이웃을 옛 이웃으로 되감는 구조다.

**풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 $F_1 = 1$, $F_2 = 1$이고, 1의 약수는 $\pm 1$뿐이므로 두 수의 공약수도 $\pm 1$뿐이다. **[귀납]** $F_k$와 $F_{k+1}$의 공약수가 $\pm 1$뿐이라고 가정하자(귀납 가정). 보일 것은 $F_{k+1}$과 $F_{k+2}$의 공약수가 $\pm 1$뿐이라는 것이다. $d$를 $F_{k+1}$과 $F_{k+2}$의 임의의 공약수라 하자. 곧 $d \mid F_{k+1}$이고 $d \mid F_{k+2}$이다. 2주차 문제 7(근거 ④)에 의해

$$
d \mid \big(F_{k+2} - F_{k+1}\big)
$$

인데, 점화식 $F_{k+2} = F_{k+1} + F_k$에서 $F_{k+2} - F_{k+1} = F_k$이므로 $d \mid F_k$이다. 따라서 $d$는 $F_k$와 $F_{k+1}$의 공약수이고, 귀납 가정에 의해 $d = \pm 1$이다. $d$가 임의의 공약수였으므로 $F_{k+1}$과 $F_{k+2}$의 공약수는 $\pm 1$뿐이다. 따라서 $P(k+1)$이 성립하고, 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $F_n$과 $F_{n+1}$의 공약수는 $\pm 1$뿐이다. $\blacksquare$

**검산.** $F_7 = 13$과 $F_8 = 21$: 13의 약수는 $\pm 1, \pm 13$, 21의 약수는 $\pm 1, \pm 3, \pm 7, \pm 21$이므로 공통인 것은 $\pm 1$뿐이다 ✓.

**복기.** 22주차 문제 11("$n$과 $n+1$의 공통 약수는 $\pm 1$뿐")과 몸통이 같다 — 둘 다 "두 배수의 차를 취해 더 작은 수로 되감는다". 이 되감기를 반복하는 절차가 유클리드 호제법이고, 그 절차가 가장 느리게 끝나는 입력이 바로 이웃한 두 피보나치 수다.

### 문제 13

**접근.** 분수 점화식이므로 앞 항을 계산할 때 통분이 필요하다. 네 항을 구하면 분자가 전부 1이라는 것이 먼저 보이고, 그 다음 분모가 첨자와 같다는 것이 보인다.

**풀이.** **[추측]** $a_1 = 1$이고

$$
a_2 = \frac{1}{1 + 1} = \frac12, \qquad a_3 = \frac{1/2}{1 + 1/2} = \frac{1/2}{3/2} = \frac13, \qquad a_4 = \frac{1/3}{1 + 1/3} = \frac{1/3}{4/3} = \frac14
$$

이므로 $a_n = \dfrac1n$으로 추측한다. (검산: $a_5 = \frac{1/4}{5/4} = \frac15$ ✓.)

**[증명]** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $a_1 = 1$, 우변 $\frac11 = 1$이므로 같다. **[귀납]** $a_k = \frac1k$이라 가정하자(귀납 가정). 보일 것은 $a_{k+1} = \frac{1}{k+1}$이다. 점화식에 의해

$$
a_{k+1} = \frac{a_k}{1 + a_k} = \frac{1/k}{1 + 1/k} \ \text{(귀납 가정)} = \frac{1/k}{(k+1)/k} = \frac1k \cdot \frac{k}{k+1} = \frac{1}{k+1}
$$

이므로 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $a_n = \frac1n$이다. $\blacksquare$

**복기.** 분모 $1 + \frac1k$를 $\frac{k+1}{k}$로 통분하는 것이 유일하게 손이 필요한 변형이고, 그 뒤는 분수의 나눗셈이 곱셈으로 바뀌면서 $k$가 약분된다. 점화식이 분수여도 5단계 틀은 한 줄도 바뀌지 않는다.

### 문제 14

**접근.** 첨자에 $F_{k-1}$이 보여도 소비하는 가정은 $P(k)$ 하나이므로 기초도 하나다 — $P(n)$ 자체가 이웃한 세 항을 한 등식으로 묶은 문장이기 때문이다(§1.5). 도착점은 $(-1)^{k+1}$이고 귀납 가정은 $(-1)^k$이므로, 계산 결과를 **가정의 부호를 뒤집은 꼴** $-\big(F_{k+1}F_{k-1} - F_k^2\big)$로 만드는 것이 목표다. 전개 도중 $F_{k+1} - F_k$가 나오면 점화식으로 $F_{k-1}$로 되감는다.

**풀이.** $n$에 대한 수학적 귀납법으로 증명한다(무대가 $n \ge 2$이므로 기초는 $n = 2$다). **[기초]** $n = 2$일 때 $F_3 F_1 - F_2^2 = 2 \cdot 1 - 1^2 = 1$이고 $(-1)^2 = 1$이므로 같다. **[귀납]** $k \ge 2$에 대해 $F_{k+1}F_{k-1} - F_k^2 = (-1)^k$이라 가정하자(귀납 가정). 보일 것은 $F_{k+2}F_k - F_{k+1}^2 = (-1)^{k+1}$이다. 점화식 $F_{k+2} = F_{k+1} + F_k$를 대입해 전개하면

$$
F_{k+2}F_k - F_{k+1}^2 = (F_{k+1} + F_k)F_k - F_{k+1}^2 = F_{k+1}F_k + F_k^2 - F_{k+1}^2
$$

이고, $F_{k+1}$이 들어 있는 두 항($F_{k+1}F_k$와 $-F_{k+1}^2$)을 뒤로 모아 $F_{k+1}$을 묶어 내면

$$
F_{k+1}F_k + F_k^2 - F_{k+1}^2 = F_k^2 + \big(F_{k+1}F_k - F_{k+1}^2\big) = F_k^2 - F_{k+1}\big(F_{k+1} - F_k\big)
$$

이다. 여기서 $k \ge 2$이므로 점화식 $F_{k+1} = F_k + F_{k-1}$이 적용되어 $F_{k+1} - F_k = F_{k-1}$이다. 따라서

$$
F_{k+2}F_k - F_{k+1}^2 = F_k^2 - F_{k+1}F_{k-1} = -\big(F_{k+1}F_{k-1} - F_k^2\big) = -(-1)^k \ \text{(귀납 가정)} = (-1)^{k+1}
$$

이므로 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 $n \ge 2$에 대해 $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$이다. $\blacksquare$

**검산.** $n = 3$: $F_4 F_2 - F_3^2 = 3 \cdot 1 - 4 = -1 = (-1)^3$ ✓. $n = 4$: $F_5 F_3 - F_4^2 = 5 \cdot 2 - 9 = 1 = (-1)^4$ ✓.

**복기.** 부호가 번갈아 바뀌는 항등식의 귀납은 "가정을 그대로 쓰는" 것이 아니라 "가정에 $-1$을 곱한 꼴을 만드는" 것이 목표가 된다. 도착점을 미리 적어 두는 습관(5단계 틀 ③)이 이 방향 설정을 해 준다. 이 항등식은 넓이 역설의 정체이기도 하다 — 한 변이 $F_{n+1}$인 정사각형을 잘라 $F_{n+2} \times F_n$ 직사각형으로 재조립하면 (정사각형 넓이) $-$ (직사각형 넓이)가 정확히 $(-1)^n$이다. $n = 5$이면 정사각형이 $8 \times 8 = 64$, 직사각형이 $5 \times 13 = 65$이므로 $64 - 65 = -1 = (-1)^5$이다. 같은 항등식을 첨자 하나씩 밀어 적으면 $F_{n+1}^2 - F_n F_{n+2} = (-1)^n$이 된다 — 새 항등식이 아니라 카시니를 다시 쓴 것이므로 따로 증명할 필요가 없다.

### 문제 15

**접근.** 두 칸 모드이므로 강한 귀납법과 기초 2개다. 손으로 놓아야 하는 것은 연결 부등식 한 줄이고, 두 항의 공통인수로 지수가 작은 쪽을 묶어 내면 계수 비교로 끝난다.

**풀이.** $n$에 대한 강한 귀납법으로 증명한다. **[기초]** $n = 1$일 때 $F_1 = 1$이고 $\left(\frac32\right)^{-1} = \frac23$이므로 $1 \ge \frac23$이다. $n = 2$일 때 $F_2 = 1$이고 $\left(\frac32\right)^{0} = 1$이므로 $1 \ge 1$이다. **[귀납]** $k \ge 2$인 $k$에 대해 $1 \sim k$의 모든 자리에서 성립한다고 가정하자. 보일 것은 $F_{k+1} \ge \left(\frac32\right)^{k-1}$이다. $k+1 \ge 3$이므로 점화식이 적용되어

$$
F_{k+1} = F_k + F_{k-1} \ge \left(\tfrac32\right)^{k-2} + \left(\tfrac32\right)^{k-3} \ \text{(귀납 가정을 두 자리에)}
$$

이다. 연결 부등식으로 도착점까지 잇는다. 공통인수 $\left(\frac32\right)^{k-3}$으로 묶으면

$$
\left(\tfrac32\right)^{k-2} + \left(\tfrac32\right)^{k-3} = \left(\tfrac32\right)^{k-3}\left(\tfrac32 + 1\right) = \left(\tfrac32\right)^{k-3} \cdot \tfrac52 \ \ge \ \left(\tfrac32\right)^{k-3} \cdot \tfrac94 = \left(\tfrac32\right)^{k-3}\left(\tfrac32\right)^{2} = \left(\tfrac32\right)^{k-1}
$$

이다($\frac52 = \frac{10}{4} \ge \frac94$이고 $\left(\frac32\right)^{k-3} > 0$이므로 부등호의 방향이 유지된다). 두 부등식을 이으면 $F_{k+1} \ge \left(\frac32\right)^{(k+1)-2}$이므로 $P(k+1)$이 성립한다. 강한 귀납법에 의해 모든 자연수 $n$에 대해 $F_n \ge \left(\frac32\right)^{n-2}$이다. $\blacksquare$

**검산.** $n = 6$: $F_6 = 8$이고 $\left(\frac32\right)^4 = \frac{81}{16} = 5.0625$이므로 $8 \ge 5.0625$ ✓.

**복기.** 이 문제와 예제 2.3을 합치면 "피보나치는 공비 $\frac32$보다 빠르고 공비 $2$보다 느리게 커진다"는 위아래 두 방향의 하계$\cdot$상계가 된다. 진짜 공비가 그 사이의 $\varphi$라는 사실의 절반이 문제 18이고, 나머지 절반(극한)이 45주차다.

### 문제 16

**접근.** 훈련 2(짝수 번째 합)와 같은 구조이며 우변에 $-1$이 없다. 마지막 항 $F_{2k+1}$을 분리해 귀납 가정을 넣으면 $F_{2k} + F_{2k+1}$이 남고, 이 둘은 이웃한 두 항이므로 점화식 한 번으로 닫힌다.

**풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변은 $F_1 = 1$이고 우변은 $F_2 = 1$이므로 같다. **[귀납]** $F_1 + F_3 + \cdots + F_{2k-1} = F_{2k}$라 가정하자(귀납 가정). 보일 것은 $F_1 + F_3 + \cdots + F_{2k+1} = F_{2k+2}$이다. 마지막 항 $F_{2k+1}$을 분리하면

$$
F_1 + F_3 + \cdots + F_{2k-1} + F_{2k+1} = F_{2k} + F_{2k+1} \ \text{(귀납 가정)} = F_{2k+2} = F_{2(k+1)}
$$

이고 둘째 등호는 점화식이다. 따라서 $P(k+1)$이 성립하고, 수학적 귀납법에 의해 모든 자연수 $n$에 대해 명제가 성립한다. $\blacksquare$

**검산.** $n = 3$: 좌변 $F_1 + F_3 + F_5 = 1 + 2 + 5 = 8$, 우변 $F_6 = 8$ ✓.

**복기.** 이 문제와 훈련 2를 더하면 예제 2.2가 나온다 — 홀수 번째 합 $F_{2n}$과 짝수 번째 합 $F_{2n+1} - 1$을 더하면 $F_1$부터 $F_{2n}$까지의 합 $F_{2n+2} - 1$이 되고, 이는 예제 2.2에 $n$ 자리로 $2n$을 넣은 것과 같다. 증명된 항등식들끼리 맞물리는지 확인하는 것도 검산의 한 방법이다.

### 문제 17

**접근.** 두 칸 모드 답안을 검사하는 고정된 두 질문을 그대로 쓴다(문제 10 복기). ① 귀납 단계의 각 부등호가 어느 가정에 기대는지 옆에 적는다 — 가정한 적 없는 것을 쓴 줄이 드러난다. ② 귀납 단계가 작동하는 $k$의 범위를 적고, 그 범위와 기초가 함께 덮지 못하는 $n$을 센다.

**풀이.** 결함은 두 가지다.

**① 가정 범위 초과.** 답안은 "[귀납] $F_k < 2^k$이라 가정하자"라고만 적었다 — 곧 보통 귀납의 가정 $P(k)$ 하나다. 그런데 몸통에서 $F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1}$이라 쓰면서 $F_{k-1} < 2^{k-1}$, 곧 $P(k-1)$을 사용했다. 가정한 적 없는 것을 근거로 삼았으므로 이 줄은 근거 목록의 어느 칸에도 해당하지 않는다. 고치려면 "$1 \sim k$에서 성립한다고 가정하자"로 강한 귀납법을 선언해야 한다(33주차 §1.4).

**② 기초 부족.** 점화식 $F_{k+1} = F_k + F_{k-1}$은 $k+1 \ge 3$에서만 적용되므로, 이 귀납 단계가 만들어 낼 수 있는 것은 $P(3), P(4), \dots$뿐이다. 기초는 $n = 1$ 하나이므로 $P(2)$가 기초에서도 귀납에서도 확보되지 않는다. 보폭이 2이면 기초도 2개여야 한다는 규칙(§1.5)을 어긴 것이다.

수정본이 예제 2.3이다 — 강한 귀납법을 선언하고 기초를 $n = 1$과 $n = 2$ 두 개 확인하면 두 결함이 동시에 사라진다.

**복기.** 이 답안의 계산은 한 줄도 틀리지 않았다. 결함은 계산이 아니라 **선언**에 있다 — 무엇을 가정했다고 적었는가, 기초를 몇 개 확인했는가. 33주차 문제 17이 같은 결함을 다른 수열에서 다뤘고, 35주차 오류 박물관의 2관이 이 유형이다.

### 문제 18

**접근.** 두 부분으로 나뉜다. 앞부분은 $\varphi^2$과 $\varphi + 1$을 각각 계산해 비교하는 확인이고, 뒷부분은 문제 15와 뼈대가 같은 강한 귀납이다. 다른 곳은 연결 부등식뿐이며, 여기서는 부등호가 아니라 **등호**로 떨어진다.

**풀이.**

**(앞부분) $\varphi^2 = \varphi + 1$의 확인.** 좌변을 전개하면

$$
\varphi^2 = \left(\frac{1+\sqrt5}{2}\right)^2 = \frac{(1+\sqrt5)^2}{4} = \frac{1 + 2\sqrt5 + 5}{4} = \frac{6 + 2\sqrt5}{4} = \frac{3+\sqrt5}{2}
$$

이고, 우변을 통분하면 $\varphi + 1 = \frac{1+\sqrt5}{2} + \frac22 = \frac{3+\sqrt5}{2}$이다. 두 값이 같으므로 $\varphi^2 = \varphi + 1$이다. (달리 말하면 $\varphi$는 $x^2 = x + 1$의 근이다.)

**(뒷부분) $F_n \le \varphi^{n-1}$의 증명.** $n$에 대한 강한 귀납법으로 증명한다. **[기초]** $n = 1$일 때 $F_1 = 1$이고 $\varphi^0 = 1$이므로 $1 \le 1$이다. $n = 2$일 때 $F_2 = 1$이고 $\varphi^1 = \frac{1+\sqrt5}{2} \approx 1.618$이므로 $1 \le \varphi$이다. **[귀납]** $k \ge 2$인 $k$에 대해 $1 \sim k$의 모든 자리에서 성립한다고 가정하자. 보일 것은 $F_{k+1} \le \varphi^{k}$이다. $k+1 \ge 3$이므로 점화식이 적용되어

$$
F_{k+1} = F_k + F_{k-1} \le \varphi^{k-1} + \varphi^{k-2} \ \text{(귀납 가정을 두 자리에)}
$$

이다. 공통인수 $\varphi^{k-2}$로 묶고 앞부분의 확인을 쓰면

$$
\varphi^{k-1} + \varphi^{k-2} = \varphi^{k-2}(\varphi + 1) = \varphi^{k-2} \cdot \varphi^2 = \varphi^{k}
$$

이므로 $F_{k+1} \le \varphi^{k} = \varphi^{(k+1)-1}$이다. 따라서 $P(k+1)$이 성립하고, 강한 귀납법에 의해 모든 자연수 $n$에 대해 $F_n \le \varphi^{n-1}$이다. $\blacksquare$

**검산.** $n = 6$: $F_6 = 8$이고 $\varphi^5 \approx 11.09$이므로 $8 \le 11.09$ ✓.

**복기.** 문제 15에서는 연결 부등식이 $\frac52 \ge \frac94$라는 여유로 닫혔고, 여기서는 $\varphi + 1 = \varphi^2$이라는 등호로 닫혔다. 여유가 0이라는 것은 상계 $\varphi^{n-1}$이 더 줄일 수 없는 한계에 닿아 있다는 뜻이다. $\varphi$가 $x^2 = x+1$의 근이라는 사실 하나가 이 결과를 만들었고, 그 방정식은 점화식에서 이렇게 나온다 — $F_n = F_{n-1} + F_{n-2}$의 양변을 $F_{n-1}$로 나누면 $\frac{F_n}{F_{n-1}} = 1 + \frac{F_{n-2}}{F_{n-1}}$이 되고, 이웃한 두 항의 비율이 한 값 $x$로 안정된다고 보면 $x = 1 + \frac1x$, 곧 $x^2 = x + 1$이 된다. (비율이 실제로 한 값에 안정된다는 것은 여기서 증명하지 않고 가정한 것이며, 그 가정을 정당화하는 극한의 언어가 45주차의 몫이다.) 비율이 $\varphi$에 다가가는 이유(문제 20(b), 45주차)의 절반이 여기에 있다.

### 문제 19

**접근.** 더해지는 수 $2n+1$이 $n = 1, 2, 3, \dots$에 따라 $3, 5, 7, \dots$로 바뀐다. 곧 이 수열은 1에서 시작해 홀수를 차례로 더한 값이므로, 앞 다섯 항을 계산하면 패턴이 곧바로 보인다.

**풀이.**

**(a)** 점화식대로 계산하면

$$
d_1 = 1, \quad d_2 = 1 + 3 = 4, \quad d_3 = 4 + 5 = 9, \quad d_4 = 9 + 7 = 16, \quad d_5 = 16 + 9 = 25
$$

이고 이는 $1^2, 2^2, 3^2, 4^2, 5^2$이므로 $d_n = n^2$으로 추측한다. (검산: $d_6 = 25 + 11 = 36 = 6^2$ ✓.)

**(b)** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $d_1 = 1$, 우변 $1^2 = 1$이므로 같다. **[귀납]** $d_k = k^2$이라 가정하자(귀납 가정). 보일 것은 $d_{k+1} = (k+1)^2$이다. 점화식에 의해

$$
d_{k+1} = d_k + (2k+1) = k^2 + 2k + 1 \ \text{(귀납 가정)} = (k+1)^2
$$

이므로 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $d_n = n^2$이다. $\blacksquare$

**(c)** 31주차 훈련 1의 공식 $1 + 3 + 5 + \cdots + (2n-1) = n^2$과 같은 내용이다. 그쪽은 홀수 $n$개의 합을 한 줄의 등식으로 적었고, 이쪽은 같은 덧셈을 "직전 값에 다음 홀수를 더한다"는 점화식으로 적었다. 누적합과 점화식은 같은 대상의 두 표기다.

**복기.** 마지막 변형 $k^2 + 2k + 1 = (k+1)^2$이 완전제곱 인수분해이고, 이 문제의 전부다. (c)가 알려 주는 일반 원리는 이것이다 — 누적합 $\sum_{i=1}^n f(i)$는 언제나 점화식 $S_{n+1} = S_n + f(n+1)$로 다시 쓸 수 있고, 그 역도 성립한다.

### 문제 20

**접근.** (a)는 §1.3의 대응표를 문장으로 푸는 서술이다. 정의의 두 조각(초기 조건과 점화식)이 증명의 두 조각(기초와 귀납 단계)에 각각 대응한다는 것을 지목하면 된다. (b)는 나눗셈 일곱 번이고, 값을 세로로 나열하면 크고 작음이 번갈아 나타나는 것이 보인다.

**풀이.** (예시 답안)

**(a)** 점화식 수열은 "초기 조건 + 이전 항에서 다음 항을 만드는 규칙"으로 정의되는데, 이는 귀납 증명의 "기초 + 귀납 단계"와 조각 하나하나가 대응하는 같은 구조다. 정의가 귀납적으로 되어 있으므로 그 정의를 그대로 따라가며 성질을 옮기는 도구도 귀납법이고, 귀납 단계의 첫수가 언제나 점화식 대입인 것이 그 대응의 직접적인 결과다.

**(b)** 소수점 셋째 자리까지 계산하면

$$
\frac{F_3}{F_2} = 2.000,\quad \frac{F_4}{F_3} = 1.500,\quad \frac{F_5}{F_4} \approx 1.667,\quad \frac{F_6}{F_5} = 1.600,
$$

$$
\frac{F_7}{F_6} = 1.625,\quad \frac{F_8}{F_7} \approx 1.615,\quad \frac{F_9}{F_8} \approx 1.619
$$

이다. 값이 큰 쪽과 작은 쪽을 번갈아 오가면서 그 진폭이 계속 줄어들고, $1.618\dots \approx \varphi$를 사이에 두고 좁혀지는 모양이다.

**복기.** 진동하며 좁혀지는 이 모양은 카시니 항등식(문제 14)의 직접적인 결과다. $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$의 양변을 $F_n F_{n-1}$로 나누면

$$
\frac{F_{n+1}}{F_n} - \frac{F_n}{F_{n-1}} = \frac{(-1)^n}{F_n F_{n-1}}
$$

이 되는데, 오른쪽의 부호가 매 항 뒤집히므로 비율이 위아래로 번갈아 움직이고, 분모 $F_n F_{n-1}$이 커지므로 진폭이 줄어든다. "다가간다"를 느낌이 아니라 정확한 문장으로 말하는 언어($\varepsilon$-N 정의)가 45주차의 주제이며, 45주차 문제 19가 이 관찰을 그 언어로 다시 쓰는 자리다.

---

**다음 주 예고:** 31~34주차의 귀납법 파트를 마무리한다. 먼저 **귀납 오류 박물관** 5관에서 기초 누락$\cdot$기초 부족$\cdot$전달의 첫 고리 붕괴$\cdot$연결 부등식 생략$\cdot$귀납 가정 미사용을 한자리에 모아 탐지 질문을 만든다. 이번 주 문제 17이 2관의 사례로 다시 등장한다. 그다음 "모든 말은 같은 색"이라는 가짜 증명이 정확히 어느 $k$에서 무너지는지 해부하고, 20문항 백지 시험으로 7부를 수료한다.