# 34주차 — 점화식과 피보나치 수열

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: 점화식은 수열의 귀납적 정의다 — 정의가 기초와 전달로 되어 있으므로, 그 수열의 성질을 증명하는 엔진도 언제나 그 점화식이다.

**이 주의 위치**: 50주 과정의 34주차. 31~33주차에서 세운 귀납법을 "귀납적으로 정의된 대상"에 적용하고, 33주차 §1.4의 보폭 규칙을 실전에서 반복 훈련한다.

**원서 대응**: BoP(Book of Proof) 10장 후반 (Fibonacci 예제와 연습문제군). 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. 점화식과 초기 조건이 함께라야 수열이 결정된다는 것을 설명하고, 점화식이 **수열의 귀납적 정의**임을 귀납 원리의 조각과 하나씩 대응시킬 수 있다.
1. 닫힌 꼴이 주어지지 않은 수열에서 **추측 $\to$ 귀납 확정** 사이클(①~④)로 공식을 찾아 증명할 수 있다.
1. 피보나치 수열의 정의를 백지에 쓰고, 합 공식$\cdot$제곱합 공식$\cdot$카시니 항등식을 귀납법으로 증명할 수 있다.
1. 한 칸 모드와 두 칸 모드를 구분하고, "보폭 2이면 기초 2개"를 실제 증명에서 지킬 수 있다.

본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

## 준비 운동 (33주차 복습)

1. 강한 귀납법에서 "보폭 $d$이면 기초 $d$개"인 이유를 33주차 문제 17의 진단 사례로 설명하시오.
1. 최소 반례법의 구조를 한 문장으로 쓰시오.
1. $c_1 = 2$, $c_{n+1} = c_n + 3$일 때 $c_2, c_3, c_4$를 계산하시오.

### 자주 나오는 세 가지 답 — 1번 문항

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 도구 이름으로 답하기.** "강한 귀납법을 안 썼기 때문"이라고 적는다.

33주차 문제 17의 답안이 강한 귀납법을 선언하고도 무너졌다는 점에서 도구를 지목한 것은 절반은 옳다. 다만 그 답안은 실제로 "$1 \sim k$에서 성립 가정"이라고 적었고 — 곧 강한 가정을 받아 두었고 — 그런데도 결론이 거짓이었다. 무너진 곳은 가정의 크기가 아니라 **기초의 개수**다.

- **유형 2 — 결과만 선언.** "기초가 하나뿐이라 틀렸다"라고 적는다. 지목한 자리는

정확하다. 빠진 것은 왜 하나로는 부족한지다 — 점화식 $c_n = c_{n-2} + 2$가 $n \ge 3$에서만 뜻을 가지므로 전달 장치가 덮지 못하는 자리가 $c_2$ 하나 생기고, 그 자리가 비면 그것에 기대는 짝수 번째 항 전체가 무너진다(33주차 문제 17 풀이). 이번 주 §1.5가 이 셈을 규칙으로 굳힌다.

- **유형 3 — 백지.** "몇 칸 뒤를 참조하는가"를 세어 본 적이 없어 손이 나가지

않는다. 세는 방법은 기계적이다 — 귀납 단계에 등장하는 첨자 중 가장 먼 과거를 찾아 $k+1$에서 몇 칸 떨어졌는지 세면 그것이 보폭이고, 그 수만큼 기초가 필요하다 ($P(n)$이 항 하나에 대한 문장일 때의 규칙이며, 단서는 §1.5에 있다). 이번 주 내내 이 셈을 반복한다.

## 개념 — 귀납적으로 정의된 수열

### 1 귀납법을 곧바로 꺼내면 어디서 막히는가

이번 주의 소재는 "규칙으로 정의된 수열"이다. 31주차에서 세운 귀납 증명의 서식을 다음 문제에 그대로 들이대 보자.

:::{admonition} 시도 — 서식부터 꺼내 보기
:class: quotebox

문제: $a_1 = 1$, $a_{n+1} = 2a_n + 1$로 정의된 수열의 일반항을 구하시오.

"$n$에 대한 수학적 귀납법으로 증명한다.

**[기초]** $n = 1$일 때: $a_1 = 1$이고, 이것을 무엇과 비교해야 하는지 …

**[귀납]** $P(k)$가 성립한다고 가정하자 — 그런데 $P(k)$가 무슨 문장인지 …"
:::

여기서 멈춘다. 31주차의 서식은 검사할 명제 $P(n)$이 **이미 손에 있는 상태**에서 시작한다. 지금 손에 있는 것은 규칙 하나뿐이고, $P(n)$ 자리에 적을 문장이 없다.

:::{container} quotebox
**확인 1.** 멈춘 자리에서 다음 줄이 나오려면 무엇이 먼저 있어야 하는가.

그것을 귀납법이 만들어 줄 수 있는가?
:::

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

먼저 있어야 하는 것은 **검사할 후보 문장** $P(n)$ — 첨자 $n$만으로 $a_n$을

계산하는 공식이다. 귀납법은 이 후보가 참인지 **검사**하는 도구이지 후보를

**만드는** 도구가 아니다. 후보를 만드는 일은 별도의 단계이고, 그 단계는

1주차에서 "증명이 아니다"라고 못 박은 예시 관찰이다.

이번 주는 그 예시 관찰을 버리지 않고 제자리에 앉힌다 — 예시가 후보를 만들고

귀납이 후보를 확정한다(§1.6).
:::

### 2 규칙으로 항을 만들어 보기

막히기 전에 할 수 있는 일부터 한다. 규칙 $a_{n+1} = 2a_n + 1$과 시작값 $a_1 = 1$로 표를 채워 보자.

| **$n$** | **$a_n$의 계산** | **$a_n$** |
|---|---|---|
| $1$ | 시작값으로 주어짐 | $1$ |
| $2$ | $2a_1 + 1 = 2 \times 1 + 1$ | $3$ |
| $3$ | $2a_2 + 1 = 2 \times 3 + 1$ | $\underline{\quad(1)\quad}$ |
| $4$ | $2a_3 + 1 = 2 \times \underline{\quad(2)\quad} + 1$ | $\underline{\quad(3)\quad}$ |
| $5$ | $2a_4 + 1$ | $\underline{\quad(4)\quad}$ |

:::{container} quotebox
**확인 2.** 빈칸 (1)~(4)를 채우고, 시작값 $a_1 = 1$이 주어지지 않았다면

이 표의 어느 칸부터 채울 수 없는지 적어 보자.
:::

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

(1) $7$  (2) $7$  (3) $15$  (4) $31$.

시작값이 없으면 **첫 칸부터** 채울 수 없다. 규칙이 알려 주는 것은 "앞 항에서

다음 항으로"뿐이므로, 앞 항이 하나도 없으면 규칙은 한 번도 발동하지 못한다.

거꾸로 시작값만 있고 규칙이 없어도 둘째 칸부터 채울 수 없다.

규칙과 시작값이 **함께**라야 수열의 모든 항이 하나로 결정된다.
:::

이 관찰에 정식 이름을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 한 일에 이름을 붙였을 뿐이다.

### 정의 34.1 — 점화식과 초기 조건 (recurrence relation, initial condition) [백지 암기 대상]

:::{container} quotebox
수열 $\{a_n\}$의 각 항을 **앞의 항(들)으로** 나타내는 등식을 **점화식**이라 하고,

그 등식이 유효한 $n$의 범위를 함께 밝힌다.

그 범위 밖이라서 규칙으로 만들 수 없는 앞쪽 항(들)의 값을 손으로 주는 것을

**초기 조건**이라 한다.

점화식(적용 범위 포함)과 초기 조건이 함께 주어져야 수열의 모든 항이 하나로 결정된다.
:::

기호 $\{a_n\}$은 "에이 엔의 수열"로 읽고, 첫째 항부터 차례로 늘어놓은 수 전체를 한 덩어리로 부르는 표기다. $a_n$ 하나는 수이고, $\{a_n\}$은 그 수들의 나열이다.

### 3 정의가 귀납이면 증명도 귀납

점화식 정의의 조각과 31주차 귀납 원리의 조각을 나란히 놓아 보자.

| **점화식 정의의 조각** | **귀납 원리의 조각** | **두 조각이 공통으로 하는 일** |
|---|---|---|
| 초기 조건 $a_1 = 1$ | **[기초]** $P(1)$이 참 | 출발점을 손으로 확보한다 |
| 점화식 $a_{n+1} = 2a_n + 1$ | **[귀납]** $P(k)$가 참이면 $P(k+1)$도 참 | 한 칸을 전달한다 |
| 두 조각으로 모든 항이 결정된다 | 두 조각으로 모든 $n$에서 참이 된다 | 전체를 확보한다 |

:::{container} quotebox
**확인 3.** 위 대응을 근거로, 점화식 수열의 성질을 증명할 때 귀납 단계의

첫수(첫 변형)로 무엇을 써야 하는지 한 구절로 적어 보자.
:::

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

**점화식 대입**이다. 귀납 단계에서 손에 든 것은 $P(k)$(과거에 대한 정보)이고

만들어야 할 것은 $P(k+1)$(미래에 대한 문장)인데, $a_{k+1}$을 과거의 항으로

바꿔 주는 등식은 점화식 하나뿐이다. 그 등식을 쓰기 전에는 귀납 가정을 꽂아

넣을 자리 자체가 생기지 않는다.

점화식은 이번 주 모든 증명의 엔진이지만, 그것이 발동하는 자리는 모드에 따라

다르다 — 두 칸 모드(및 닫힌 꼴 점화식)에서는 [귀납]의 첫 등호가 점화식 대입이고,

한 칸 모드 중 **누적합 명제**(예제 2.2, 문제 9$\cdot$16, 훈련 2)에서는 첫 등호가

마지막 항 분리이고 점화식은 마지막 등호에서 두 항을 합친다. 같은 한 칸 모드라도

문제 12$\cdot$14처럼 누적합이 아닌 명제는 첫 등호가 점화식 대입이다(§1.5).
:::

### 정의 34.2 — 피보나치 수열 (Fibonacci sequence) [백지 암기 대상]

:::{container} quotebox
$$
F_1 = 1, \quad F_2 = 1, \qquad F_n = F_{n-1} + F_{n-2} \quad (n \ge 3)
$$
:::

기호 $F_n$은 "에프 엔"으로 읽고 $n$번째 피보나치 수를 뜻한다. 정의대로 항을 만들면

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

가 된다. 앞의 두 항을 더해 다음 항을 만드는 규칙이므로, 초기 조건도 두 개다.

:::{container} quotebox
**확인 4.** 정의만으로 $F_9$와 $F_{10}$을 계산해 보자. 계산 과정의 등식을

그대로 적는다.
:::

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

$F_9 = F_8 + F_7 = 21 + 13 = 34$, $F_{10} = F_9 + F_8 = 34 + 21 = 55$.

위 나열과 일치한다. 표를 외워서 답하는 것과 정의로 계산해 답하는 것은

다르다 — 이번 주의 증명은 전부 후자의 방식으로 진행된다.
:::

### 4 정의 해부 — 조각마다 하는 일

정의 34.2는 세 조각으로 되어 있고, 조각마다 증명에서 맡는 역할이 다르다.

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| "$F_1 = 1$, $F_2 = 1$" | 초기 조건 두 개 | 귀납 증명의 **기초 개수**를 두 개로 못 박는다 |
| "$F_n = F_{n-1} + F_{n-2}$" | 전달 규칙 | 귀납 단계의 첫수 — 도착점 $F_{k+1}$을 과거 두 항으로 바꾼다 |
| "$(n \ge 3)$" | 규칙의 적용 범위 | $F_2$는 규칙으로 만들 수 없다 — 기초가 두 개여야 하는 이유 |

**조각 삭제 실험.** 첫 조각에서 "$F_2 = 1$"을 지워 보자. 그러면 $F_3 = F_2 + F_1$을 계산하려는 순간 $F_2$의 값이 없고, 그 뒤의 모든 항이 결정되지 않는다.

:::{container} quotebox
**확인 5.** "$F_2 = 1$"을 지우는 순간 정확히 무엇이 무너지는가?

($F_3$만의 문제인지, 셋째 조각 "$(n \ge 3)$"을 "$(n \ge 2)$"로 고치면

해결되는지 함께 생각해 보자.)
:::

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

$F_3$ 하나가 아니라 **셋째 항 이후 전부**가 결정되지 않는다. 각 항이 앞 항에

기대고 있으므로 한 칸이 비면 그 뒤가 전부 빈다 — 수열이 정의되지 않은 것이다.

"$(n \ge 2)$"로 고쳐도 해결되지 않는다. 그러면 $F_2 = F_1 + F_0$이 되는데

$F_0$이 정의되어 있지 않으므로 같은 자리에서 다시 막힌다.

규칙이 두 칸 전을 참조하는 한, 손으로 주어야 하는 시작값은 두 개다.
:::

### 5 한 칸 모드와 두 칸 모드

같은 피보나치 수열이라도 증명할 명제에 따라 필요한 과거의 개수가 다르다. 33주차 §1.4의 보폭 규칙이 여기서 실전 형태를 갖는다.

| **모드** | **귀납 단계가 쓰는 것** | **필요한 기초** | **이번 주의 무대** |
|---|---|---|---|
| 한 칸 모드 | $P(k)$ 하나 (누적량 $\sum F_i$ 등, 또는 $P(n)$ 자체가 이웃한 여러 항을 묶은 문장) | 1개 | 예제 2.2, 문제 9$\cdot$11$\cdot$12$\cdot$14$\cdot$16, 훈련 2 (문제 14는 무대가 $n \ge 2$이므로 기초가 $n = 2$ 하나다) |
| 두 칸 모드 | $P(k)$와 $P(k-1)$ 둘 ($F_n$ 하나의 크기를 재는 부등식) | 2개 | 예제 2.3, 문제 15$\cdot$18, 훈련 3 |

**보폭 세기가 적용되는 범위.** 위의 보폭 세기는 $P(n)$이 $F_n$ 하나에 대한 문장일 때의 규칙이다. 문제 12$\cdot$14처럼 $P(n)$ 자체가 이웃한 여러 항을 한 문장으로 묶은 것이면($P(n)$: "$F_n$과 $F_{n+1}$의 공약수는 $\pm 1$뿐" 또는 "$F_{n+1}F_{n-1} - F_n^2 = (-1)^n$") $P(k)$ 하나로 다음 묶음이 만들어지므로 기초도 하나면 된다. 첨자에 $F_{k-1}$이 보인다는 것만으로 보폭을 2로 세지 않는다 — 세는 대상은 **소비하는 가정의 개수**다.

한 칸 모드에서도 점화식은 쓴다. 다만 그때 점화식은 **결론 쪽에서** 두 항을 하나로 합치는 데 쓰이고($F_{k+1} + F_{k+2} = F_{k+3}$), 귀납 가정은 여전히 $P(k)$ 하나만 소비된다. 두 칸 모드에서는 점화식이 **가정 쪽에서** 두 과거를 불러오므로 ($F_{k+1} = F_k + F_{k-1}$) 가정도 두 개가 필요하다.

:::{container} quotebox
**확인 6.** 어떤 답안의 [귀납] 부분에 "$F_{k+1} = F_k + F_{k-1}$이고,

귀납 가정에 의해 $F_k < 2^k$, $F_{k-1} < 2^{k-1}$이다"라고 적혀 있다.

이 답안은 몇 개의 기초를 확인했어야 하는가. 그 이유는?
:::

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

**두 개**($n = 1$과 $n = 2$)다. 귀납 단계가 $k$와 $k-1$ 두 자리를 참조하므로

보폭이 2이고, 33주차 §1.4의 규칙에 의해 기초도 2개다.

셈이 이렇게도 확인된다: 이 논증은 $F_{k+1}$에 점화식을 쓰므로 $k+1 \ge 3$에서만

작동한다. 곧 $n = 1$과 $n = 2$는 전달 장치가 절대 만들어 내지 못하는 자리다.

기초가 $n = 1$ 하나뿐이면 $F_2$가 확보되지 않은 채 그 위에 모든 것이 쌓인다

(문제 17에서 이 답안을 정면으로 해부한다).
:::

### 6 닫힌 꼴이 주어지지 않을 때 — 추측 → 귀납 확정 사이클

§1.1에서 막혔던 문제로 돌아간다. 손에 규칙만 있고 검사할 공식이 없을 때의 동선은 다음과 같다. **닫힌 꼴**(closed form)이란 첨자 $n$만으로 $a_n$을 계산하는 공식을 말한다 — $a_n = 2^n - 1$처럼 앞 항을 참조하지 않는 표현이다.

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

**추측 $\to$ 귀납 확정 사이클**

① 앞 항을 여러 개 계산한다($a_1$부터 $a_5$ 정도).

② 패턴을 **추측**한다(등차인가, 등비인가, $2^n \pm 1$인가, 제곱수인가).

③ 추측을 아직 쓰지 않은 항에서 검산한다 — 어긋나면 ①로 돌아간다.

④ **귀납법으로 확정**한다. [귀납]의 첫수는 점화식 대입이다(누적합 명제라면

마지막 항 분리가 먼저이고 그 뒤에 점화식이 온다 — §1.5).
:::

:::{container} quotebox
**확인 7.** ①~④ 중 어느 단계가 증명이고 어느 단계가 증명이 아닌가.

증명이 아닌 단계를 이 사이클에서 빼면 무슨 일이 생기는지도 적어 보자.
:::

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

증명은 ④ 하나뿐이다. ①②③은 1주차에서 "예시 확인은 증명이 아니다"라고 못

박은 그 예시 관찰이다 — 몇 개가 맞아도 나머지 전부를 보장하지 못한다

(1주차 문제 18에서 39개가 맞고 40번째에서 무너지는 사례를 보았다).

그러나 ①②③을 빼면 ④에 넣을 문장이 없다. §1.1의 막힘이 바로 그 상태였다.

예시는 후보를 **만들고** 귀납은 후보를 **확정한다** — 두 단계는 경쟁하는 것이

아니라 분업한다. 발견의 언어와 증명의 언어를 구분하는 것이 이번 주의 소득이다.
:::

### 7 근거 목록 갱신 — 칸은 그대로 네 개

증명에서 쓸 수 있는 것은 여전히 네 칸이다. 이번 주에 늘어나는 것은 칸이 아니라 ① 칸의 정의 하나와 ④ 칸의 내용물이다.

| **근거** | **내용** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | 1~33주차의 정의 전부 + **정의 34.1(점화식과 초기 조건)$\cdot$정의 34.2(피보나치 수열)**, 그리고 문제마다 주어지는 점화식 자체 | "$F_{k+1} = F_k + F_{k-1}$ (정의 34.2)"을 별도 설명 없이 쓴다 |
| ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | "$2F_{3k+1} + F_{3k}$는 정수이므로"를 별도 설명 없이 쓴다 |
| ③ 등식$\cdot$부등식의 성질 | 대입 / 전개 / 묶기 / 양변 연산 / 부등식 연결 | $a_k = 2^k - 1$을 $2a_k + 1$에 대입한다 |
| ④ 이미 증명한 명제 | 1~33주차 전부 + 이번 주에 승격되는 항등식들 | 2주차 문제 7("두 배수의 차도 배수")을 문제 12의 귀납 단계에서 쓴다 |

**점화식은 근거 ①에 들어간다.** 문제에서 "$a_{n+1} = 2a_n + 1$로 정의된 수열"이라고 주어지면 그 등식은 정의이고, 증명 어디서든 근거 없이 인용할 수 있다. 반대로 "앞 다섯 항이 $2^n - 1$이더라"는 관찰은 네 칸 어디에도 없다 — ④에 등록되려면 귀납 증명이 먼저 붙어야 한다.

이번 주에 근거 ④로 승격되는 주요 항등식은 다음과 같다: 피보나치 합 공식($\sum F_i = F_{n+2} - 1$, 예제 2.2), 제곱합 공식($\sum F_i^2 = F_n F_{n+1}$, 문제 9), 짝수 번째 합 공식($F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$, 훈련 2), 홀수 번째 합 공식(문제 16), 연속한 두 피보나치 수의 서로소성(문제 12), 카시니 항등식(문제 14). 이번 주에 증명되는 명제는 이보다 많고(훈련 3, 예제 2.3, 문제 11$\cdot$15$\cdot$18 등), 증명을 끝낸 것은 그 뒤로 전부 근거 ④가 된다.

:::{container} quotebox
**확인 8.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

허용된다면 몇 번 근거인가.

(가) "정의에 의해 $F_{k+2} = F_{k+1} + F_k$이다."

(나) "$a_1$부터 $a_5$까지 전부 $2^n - 1$이므로 모든 $n$에서 $a_n = 2^n - 1$이다."

(다) "문제 9에 의해 $F_1^2 + \cdots + F_k^2 = F_k F_{k+1}$이다."
:::

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

(가) 허용 — 근거 ①. 정의 34.2의 점화식에 $n = k+2$를 넣은 줄이므로 별도

설명이 필요 없다($k + 2 \ge 3$인지만 확인한다).

(나) 불허. 다섯 개의 확인은 그 다섯 개에 대해서만 참이다 — 근거 목록의 어느

칸에도 "여러 개 확인했다"는 항목이 없다. 이 문장은 사이클의 ②에 해당하며,

④를 거쳐야 근거가 된다.

(다) 허용 — 근거 ④. 단, 문제 9를 실제로 증명한 뒤에만 그렇다. 아직 풀지 않은

문제를 인용하면 증명되지 않은 것을 근거로 삼은 것이 된다.
:::