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

이 주의 길잡이

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

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

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

이번 주 목표

1. 점화식과 초기 조건이 함께라야 수열이 결정된다는 것을 설명하고, 점화식이 수열의 귀납적 정의임을 귀납 원리의 조각과 하나씩 대응시킬 수 있다.

2. 닫힌 꼴이 주어지지 않은 수열에서 추측 \(\to\) 귀납 확정 사이클(①~④)로 공식을 찾아 증명할 수 있다.

3. 피보나치 수열의 정의를 백지에 쓰고, 합 공식\(\cdot\)제곱합 공식\(\cdot\)카시니 항등식을 귀납법으로 증명할 수 있다.

4. 한 칸 모드와 두 칸 모드를 구분하고, “보폭 2이면 기초 2개”를 실제 증명에서 지킬 수 있다.

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

준비 운동 (33주차 복습)

1. 강한 귀납법에서 “보폭 \(d\)이면 기초 \(d\)개”인 이유를 33주차 문제 17의 진단 사례로 설명하시오.

2. 최소 반례법의 구조를 한 문장으로 쓰시오.

3. \(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주차에서 세운 귀납 증명의 서식을 다음 문제에 그대로 들이대 보자.

시도 — 서식부터 꺼내 보기

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

“\(n\)에 대한 수학적 귀납법으로 증명한다.

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

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

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

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

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

답

먼저 있어야 하는 것은 검사할 후보 문장 \(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}\)

확인 2. 빈칸 (1)~(4)를 채우고, 시작값 \(a_1 = 1\)이 주어지지 않았다면

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

답

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

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

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

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

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

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

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

수열 \(\{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\)에서 참이 된다	전체를 확보한다

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

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

답

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

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

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

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

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

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

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

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

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

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

\[ 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 \]

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

확인 4. 정의만으로 \(F_9\)와 \(F_{10}\)을 계산해 보자. 계산 과정의 등식을

그대로 적는다.

답

\(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\)의 값이 없고, 그 뒤의 모든 항이 결정되지 않는다.

확인 5. “\(F_2 = 1\)”을 지우는 순간 정확히 무엇이 무너지는가?

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

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

답

\(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}\)) 가정도 두 개가 필요하다.

확인 6. 어떤 답안의 [귀납] 부분에 “\(F_{k+1} = F_k + F_{k-1}\)이고,

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

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

답

두 개(\(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\)처럼 앞 항을 참조하지 않는 표현이다.

백지 암기 대상

추측 \(\to\) 귀납 확정 사이클

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

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

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

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

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

확인 7. ①~④ 중 어느 단계가 증명이고 어느 단계가 증명이 아닌가.

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

답

증명은 ④ 하나뿐이다. ①②③은 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 등), 증명을 끝낸 것은 그 뒤로 전부 근거 ④가 된다.

확인 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}\)이다.”

답

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

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

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

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

④를 거쳐야 근거가 된다.

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

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