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

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\).

확인 9. 이 다섯 수를 2의 거듭제곱 \(2, 4, 8, 16, 32\)와 나란히 놓아 보자.

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

답

\(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).

확인 10. 첫 문장을 완성해 보자:

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

답

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

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

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

확인 11. [기초] 문장을 완성해 보자:

“\(n = 1\)일 때 좌변은 \(a_1 = \underline{\quad}\)이고, 우변은 \(2^1 - 1 = \underline{\quad}\)이므로 같다.”

답

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

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

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

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

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

확인 12. [귀납] 문장을 완성해 보자:

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

답

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

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

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

확인 13. 계산 줄을 완성해 보자:

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

답

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

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

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

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

확인 14. 마지막 문장을 완성해 보자:

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

답

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

이 문장이 있어야 “\(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\)을 넣어도 같은 네 등호가 그대로 성립한다.

확인 15. 이 증명의 어느 줄도 \(k\)가 특정한 수라는 사실을 쓰지 않았다.

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

답

후보를 만드는 재료였다. 증명의 본문(기초와 귀납)은 다섯 항 중 \(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부터 엔까지 에프 아이의 합”으로 읽는다).

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

답

보폭 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\)을 대입).

확인 17. 목표 쪽 좌변에서 마지막 항 \(F_{k+1}\)을 떼어 내면

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

답

점화식 \(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\)이다.

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

확인 18. 도구와 기초 개수를 정해 보자. \(F_{k+1}\)을 점화식으로 풀면

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

기초는 몇 개인가.

답

\(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).

확인 19. 귀납 가정을 두 곳에 쓰면 \(F_{k+1} < 2^k + 2^{k-1}\)까지 온다.

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

답

\(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\)크기로 다르지만 뼈대가 같다. 각 단계에 어느 문장이 대응하는지 빈칸을 채워 보자.

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

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

② [기초]: \(\underline{\qquad}\)

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

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

⑤ 마감: \(\underline{\qquad}\)

답

① “\(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은 ①에서 보통 귀납을 골랐고

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

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

백지 암기 대상

점화식 귀납의 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).

이번 주의 채점 기준

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

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

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

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

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

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

기본 ●○○#

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

힌트

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

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

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

힌트

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

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

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

힌트

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

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

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

힌트

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

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

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

힌트

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

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

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

힌트

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

\(F_{k+1}\)과 \(F_{k+2}\)를 점화식으로 합친다.

표준 ●●○#

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

힌트

훈련 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\) 점화식)

힌트

마지막 항 \(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개의 이유를 한 줄 덧붙일 것.

힌트

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

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

점화식을 두 번 펼치기 — 문제 11에서 처음 쓰는 기술

지금까지는 점화식을 한 번만 대입해 \(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 항을 노출)

힌트

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

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

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

이 문제가 빌려 쓰는 사실 — 공약수와 차 (문제 12)

문제 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과 같은 논법)

힌트

공약수 \(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}\)의 앞 네 항을 계산해 닫힌 꼴을 추측하고 귀납으로 증명하시오.

힌트

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

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

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)\) 꼴로 재배열)

힌트

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

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

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

도전 ●●●#

연결 부등식 — 도전 문제가 공통으로 요구하는 한 줄

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

예제 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\)이기 때문이다)

힌트

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

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

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

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

힌트

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

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

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

“명제: 모든 \(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\)일 때 점화식은?)

힌트

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

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

② 귀납 단계가 작동하는 \(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\) — 등호로 떨어진다)

힌트

기호 \(\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주차의 어느 공식과 같은 내용인지 지적하시오.

힌트

(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주차로 미룬다).

힌트

(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부를 수료한다.