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

예제 — 세 형태를 함께 만들기

완성된 답안을 먼저 보이지 않는다. 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 약한 귀납: 홀수의 합

Result. 모든 자연수 \(n\) 에 대해 \(\displaystyle\sum_{i=1}^n (2i-1) = n^2\) 이다.

설계 — 쓰기 전에 정하는 두 가지. 귀납 답안도 다른 증명과 같다. 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 먼저 수식으로 옮긴다. 귀납에서 특별한 점은 이 번역을 귀납 단계 안에서 한다는 것뿐이다.

	말	수식 번역
형태 판정	\(P(n+1)\) 이 요구하는 이전 항	\(\underline{\quad(1)\quad}\)
기저	\(n = 1\) 에서 성립	좌변 \(= 1\), 우변 \(= 1^2\)
가정 (출발점)	\(P(n)\)	\(\sum_{i=1}^n (2i-1) = n^2\)
목표 (도착점)	\(P(n+1)\)	\(\sum_{i=1}^{n+1}(2i-1) = \underline{\quad(2)\quad}\)

확인 12. 표의 (1)과 (2)를 채워 보자. (1)은 §1.6의 세 물음 중 첫째 물음에 답하는 칸이고, (2)는 \(P(n)\) 의 식에서 \(n\) 을 \(n+1\) 로 바꾸어 얻는 칸이다.

답

(1) \(P(n)\) 하나. 합의 마지막 항 하나만 떼면 \(\sum_{i=1}^n\) 이 그대로 드러나므로

직전 항으로 충분하다 — 약한 귀납이다.

(2) \((n+1)^2\). \(P(n)\) 의 우변 \(n^2\) 에서 \(n\) 자리에 \(n+1\) 을 넣은 것이다. 도착점을

먼저 적어 두지 않으면 계산을 어디서 멈춰야 할지 알 수 없다.

1단계 — 기저를 확인한다. 사다리의 첫 칸을 실제로 놓는다. 좌변과 우변을 각각 따로 계산해 값이 같음을 보인다.

확인 13. 기저 문장을 완성해 보자. “\(n = 1\) 일 때 좌변은 \(\sum_{i=1}^1 (2i-1) = \underline{\quad}\) 이고 우변은 \(1^2 = \underline{\quad}\) 이다.”

답

좌변 \(= 2 \cdot 1 - 1 = 1\), 우변 \(= 1\). 두 값이 같으므로 \(P(1)\) 이 참이다.

기저에서 좌변과 우변을 한꺼번에 “당연히 같다”로 처리하지 않는다 — 각각 계산해

값을 적는 것까지가 걸음 ①이다.

2단계 — 가정을 선언한다. 귀납 단계는 조건문 \(P(n) \Rightarrow P(n+1)\) 하나를 증명하는 일이고, 그 조건문의 출발점을 무대에 올리는 문장이다(S14주차).

3단계 — 쪼갠다. 도착점의 좌변 \(\sum_{i=1}^{n+1}(2i-1)\) 안에서 가정의 좌변 \(\sum_{i=1}^n (2i-1)\) 이 보이도록 재그룹한다. 이 줄이 귀납의 관절이다.

확인 14. 쪼개기 줄을 완성해 보자. “\(\displaystyle\sum_{i=1}^{n+1}(2i-1) = \left(\sum_{i=1}^{n}(2i-1)\right) + \underline{\qquad}\)” — 떼어 낸 마지막 항은 무엇인가.

답

마지막 항은 \(2(n+1) - 1 = 2n+1\) 이다. 합의 일반항 \(2i-1\) 에서 \(i\) 자리에 \(n+1\) 을

넣어 얻는다. 마지막 항을 \(2n-1\) 로 적는 경우가 많은데, 그것은 \(i = n\) 일 때의 항이다 —

떼어 내야 할 것은 새로 늘어난 항이다.

4단계 — 가정을 소비하고 도착점의 꼴로 정리한다. 쪼개기로 드러난 자리에 가정을 대입한 뒤, 도착점 \((n+1)^2\) 이 나올 때까지 밀어붙인다.

확인 15. 이어지는 두 줄을 완성해 보자. “\(= \underline{\quad} + (2n+1)\) [가정 소비] \(= \underline{\qquad}\).”

답

\(= n^2 + (2n+1) = n^2 + 2n + 1 = (n+1)^2\).

첫 등호가 가정 소비처다 — \(\sum_{i=1}^n (2i-1)\) 을 \(n^2\) 으로 바꾼 그 순간에만

가정 \(P(n)\) 이 쓰였다. 둘째 등호는 완전제곱 정리이고 근거 ③이다.

5단계 — 결론을 선언한다. 두 걸음이 갖춰졌음을 밝히고 명제를 선언한다.

확인 16. 마지막 문장을 완성해 보자. “기저 단계와 \(\underline{\qquad}\) 가 모두 성립하므로, 귀납의 원리에 의해 \(\underline{\qquad}\). \(\blacksquare\)”

답

“기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 **모든 자연수

\(n\) 에 대해 \(\sum_{i=1}^n (2i-1) = n^2\) 이다.** \(\blacksquare\)”

결론 문장에서 원 명제를 다시 적는다. “따라서 성립한다”로 끝내면 무엇이 증명되었는지가

답안에 남지 않는다.

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

증명의 한 줄	왜 이 줄을 쓰는가?
\(P(n)\) 을 “\(\sum_{i=1}^n (2i-1) = n^2\)” 이라 하자.	무엇을 \(n\) 에 대해 세울지 문장으로 고정한다. 이 선언이 없으면 아래의 “가정”이 무엇을 가리키는지 정해지지 않는다.
(기저) \(n = 1\) 일 때 좌변은 \(2 \cdot 1 - 1 = 1\), 우변은 \(1^2 = 1\) 로 같다. 따라서 \(P(1)\) 이 참이다.	걸음 ①. 사다리의 첫 칸이다. 이것이 없으면 확인 2의 삭제 실험처럼 전달만 남는다.
(귀납 단계) \(n\) 을 자연수라 하고 \(P(n)\) 을 가정하자.	걸음 ②. 조건문 \(P(n) \Rightarrow P(n+1)\) 의 출발점을 무대에 올린다(S14주차).
\(\displaystyle\sum_{i=1}^{n+1}(2i-1) = \left(\sum_{i=1}^{n}(2i-1)\right) + (2n+1)\)	걸음 ③ 쪼개기. 새로 늘어난 항 \(2(n+1)-1\) 을 떼어 내 가정의 좌변을 드러낸다. 관절은 이 한 줄이다.
\(= n^2 + (2n+1) = n^2 + 2n + 1 = (n+1)^2\)	걸음 ④ 가정 소비. 첫 등호에서만 가정이 쓰였다. 나머지는 전개와 완전제곱(근거 ③)이다.
곧 \(P(n+1)\) 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 \(n\) 에 대해 \(\sum_{i=1}^n (2i-1) = n^2\) 이다. \(\blacksquare\)	걸음 ⑤. 도착점에 닿았음을 밝히고 원 명제를 다시 선언한다.

검산. \(n = 4\) 에서 좌변은 \(1 + 3 + 5 + 7 = 16\) 이고 우변은 \(4^2 = 16\) 이다. 검산은 증명이 아니지만 쪼개기를 잘못 적었을 때 곧바로 걸린다.

예제 2.2 — 강한 귀납: 소인수분해의 존재

Result. 2 이상의 모든 정수는 소수이거나 소수들의 곱이다.

준비 운동 4번이 바로 이 명제였고, §1.1의 시도 1이 여기서 막혔다. 이번에는 설계만 함께 하고 본문은 완성본으로 본다.

확인 17. 설계표를 채워 보자. (1) \(P(n+1)\) 이 요구하는 이전 항은 무엇이고 따라서 형태는 무엇인가. (2) 기저는 몇 개가 필요한가. (3) 목표(도착점)는 무엇인가.

답

(1) \(n+1\) 이 합성수일 때 \(n+1 = ab\) 로 쪼개지므로 필요한 것은 \(P(a)\) 와 \(P(b)\) 이고,

\(a\) 와 \(b\) 가 \(2\) 와 \(n\) 사이 어디인지 미리 알 수 없다. §1.6의 둘째 물음에 걸리므로

강한 귀납이다.

(2) 하나면 된다. 되돌아보는 보폭이 정해져 있지 않고 \(2\) 부터 \(n\) 까지 전부를

가정하므로, 그 구간의 시작점 \(P(2)\) 만 손으로 채우면 된다. 보폭이 고정된

확인 5의 동전 무대와 여기가 다른 점이다.

(3) \(n+1\) 이 소수이거나 소수들의 곱임을 보이는 것. 이 결론은 두 갈래이므로 답안도

두 경우로 나뉜다.

증명의 한 줄	왜 이 줄을 쓰는가?
\(P(n)\) 을 “\(n\) 은 소수이거나 소수들의 곱이다” 라 하고, \(n \ge 2\) 에서 \(P(n)\) 을 강한 귀납으로 보인다.	형태를 답안 첫 줄에 밝힌다. 읽는 쪽이 아래의 가정 폭을 어디까지로 읽을지가 여기서 정해진다.
(기저) \(n = 2\) 는 소수이므로 \(P(2)\) 가 참이다.	걸음 ①. 구간의 시작점 하나면 충분하다(확인 17).
(귀납 단계) \(n \ge 2\) 라 하고, \(2 \le i \le n\) 인 모든 정수 \(i\) 에 대해 \(P(i)\) 가 참이라고 가정하자.	걸음 ②. 출발점이 \(P(n)\) 하나가 아니라 구간 전체다 — 이 폭이 §1.1의 막힘을 푸는 유일한 차이다.
\(n+1\) 이 소수인 경우: \(P(n+1)\) 이 그대로 참이다.	결론의 첫 갈래가 이미 성립하는 경우다. 경우 나누기의 한쪽을 여기서 닫는다.
\(n+1\) 이 합성수인 경우: 합성수의 정의에 의해 \(n+1 = ab\) 이면서 \(1 < a < n+1\), \(1 < b < n+1\) 인 정수 \(a, b\) 가 존재한다. 정수이므로 \(2 \le a \le n\) 이고 \(2 \le b \le n\) 이다.	걸음 ③ 쪼개기. 근거 ①(합성수의 정의)이다. 부등식을 \(2 \le a \le n\) 으로 정리하는 이 줄이 \(a\) 를 가정의 사정권 안으로 넣는다.
\(a\) 와 \(b\) 는 모두 \(2\) 이상 \(n\) 이하이므로, 가정에 의해 각각 소수이거나 소수들의 곱이다.	걸음 ④ 가정 소비. 여기서 소비한 것은 \(P(a)\) 와 \(P(b)\) 이고, 약한 귀납의 가정에는 이 둘이 들어 있지 않다.
두 표현을 곱으로 이어 붙이면 \(n+1 = ab\) 도 소수들의 곱이다. 곧 \(P(n+1)\) 이 참이다.	도착점 도달. 이어 붙이기에는 유일성이 필요하지 않다(확인 11의 (나)).
기저 단계와 귀납 단계가 모두 성립하므로, 강한 귀납법에 의해 2 이상의 모든 정수는 소수이거나 소수들의 곱이다. \(\blacksquare\)	걸음 ⑤. 인용한 원리의 이름을 “강한 귀납법”으로 정확히 적는다.

복기. 이 증명이 약한 귀납으로 안 되는 이유는 계산이 어려워서가 아니라 가정의 폭이 모자라서다. 합성수의 두 인수는 \(\sqrt{n+1}\) 근처까지 작아질 수 있어 \(P(n)\) 하나로는 덮이지 않는다(S14주차 문제 13). 여기서 얻은 것은 산술의 기본정리의 존재 파트이고, 유일성 파트는 C15주차에서 청산한다.

예제 2.3 — 최소 반례법: 같은 명제, 다른 서식

Result. 모든 자연수 \(n\) 에 대해 \(\displaystyle\sum_{i=1}^n i = \frac{n(n+1)}2\) 이다.

이번에는 설계부터 스스로 해 보자. 이 명제는 §1.6의 첫째 물음에서 이미 약한 귀납으로 판정되는 것이고(1권 31주차 예제 2.1), 여기서는 일부러 최소 반례법으로 적는다. 같은 명제를 두 서식으로 적어 보면 두 서식의 대응이 눈에 들어온다.

확인 18. 정의 8.3의 다섯 걸음을 이 명제에 맞춰 각각 한 줄로 적어 보자. ① 무엇을 가정하는가 ② 무엇을 최소로 잡는가 ③ 무엇을 확인해 \(m\) 의 아래끝을 올리는가 ④ 최소성에서 무엇을 얻어 무엇과 충돌시키는가 ⑤ 무엇을 선언하는가.

답

① 이 공식이 성립하지 않는 자연수가 존재한다고 가정한다.

② 그런 자연수들의 집합에서 최소원소 \(m\) 을 잡는다 [최소원리].

③ \(n = 1\) 에서 공식이 성립함을 확인해 \(m \neq 1\), 곧 \(m \ge 2\) 를 얻는다.

④ 최소성에서 \(\sum_{i=1}^{m-1} i = \frac{(m-1)m}2\) 을 얻고, 여기에 \(m\) 을 더해

\(\sum_{i=1}^{m} i = \frac{m(m+1)}2\) 을 유도한다. 이것은 “\(m\) 은 반례다”와 충돌한다.

⑤ 반례가 없으므로 모든 자연수에서 공식이 성립한다.

증명. 이 공식이 성립하지 않는 자연수가 존재한다고 가정하자. 그런 자연수 전체의 집합을 \(R\) 이라 하면 \(R\) 는 공집합이 아닌 자연수 집합이므로, 최소원리에 의해 \(R\) 에는 최소원소가 존재한다. 그것을 \(m\) 이라 하자.

\(n = 1\) 일 때 좌변은 \(1\) 이고 우변은 \(\frac{1 \cdot 2}2 = 1\) 로 같으므로 \(1 \notin R\) 이고, 따라서 \(m \ge 2\) 이다. 곧 \(m - 1\) 은 자연수다. \(m\) 이 \(R\) 의 최소원소이고 \(m-1 < m\) 이므로 \(m - 1 \notin R\), 곧

\[ \sum_{i=1}^{m-1} i = \frac{(m-1)m}{2} \]

이다. 양변에 \(m\) 을 더하면

\[ \sum_{i=1}^{m} i = \frac{(m-1)m}{2} + m = \frac{m^2 - m + 2m}{2} = \frac{m(m+1)}{2} \]

이므로 \(m \notin R\) 이다. 이것은 \(m \in R\) 라는 사실과 충돌하므로 모순이다. 따라서 \(R\) 는 공집합이고, 모든 자연수 \(n\) 에 대해 \(\sum_{i=1}^n i = \frac{n(n+1)}2\) 이다. \(\blacksquare\)

이번 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 원서와 실전의 증명은 처음부터 끝까지 이런 산문이다. 이번 주의 목표는 이 산문을 백지에서 재현하는 것이다.

검산. \(n = 5\) 에서 좌변은 \(1+2+3+4+5 = 15\) 이고 우변은 \(\frac{5 \cdot 6}2 = 15\) 이다.

관찰 — 세 예제의 같은 뼈대

예제 2.1, 2.2, 2.3은 형태가 다르지만 하는 일이 같다. 대응표의 빈칸을 채워 보자.

항목	예제 2.1 (약한)	예제 2.2 (강한)	예제 2.3 (최소 반례)
첫 칸을 놓은 줄	기저 \(n = 1\)	기저 \(n = 2\)	\(\underline{\quad(1)\quad}\)
가정으로 받은 것	\(P(n)\) 하나	\(\underline{\quad(2)\quad}\)	\(m\) 보다 작은 곳은 전부 참
한 칸을 만든 계산	마지막 항 분리 후 대입	인수 분해 후 두 가정 대입	\(\underline{\quad(3)\quad}\)
마무리	원 명제 선언	원 명제 선언	모순 지목 후 원 명제 선언

확인 19. 표의 (1)(2)(3)을 채우고, 세 예제가 공통으로 만든 것을 한 낱말로 적어 보자.

답

(1) “\(n = 1\) 에서 성립하므로 \(1 \notin R\)” — 기저를 확인해 최소 반례의 아래끝을

올린 줄이다. 위치만 옮겼을 뿐 계산은 예제 2.1의 기저와 같다.

(2) \(2\) 부터 \(n\) 까지 전부, 곧 \(P(2), \ldots, P(n)\).

(3) \(\sum_{i=1}^{m-1} i\) 에 \(m\) 을 더해 \(\sum_{i=1}^{m} i\) 를 얻은 계산 — 예제 2.1의

쪼개기를 \(n \to n+1\) 대신 \(m-1 \to m\) 으로 적은 것이다.

공통으로 만든 것: 한 칸. 세 예제 모두 “바로 아래에서 참이면 여기서도 참”이라는

한 칸을 만들고, 그 칸을 어느 방향으로 쓰는지만 다르다.

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

백지 암기 대상

귀납 답안의 공통 뼈대

어느 형태를 쓰든 답안에는 세 가지가 반드시 있다.

① 첫 칸 — 기저 확인(최소 반례법에서는 기저 배제로 나타난다).

② 한 칸 — 아래에서 여기로 오는 계산. 이 계산의 재료가 되는 이전 항이 몇 개냐가 형태를 정한다.

③ 원리 인용과 선언 — 어느 원리로 무한을 덮었는지 이름을 밝히고 원 명제를 다시 적는다.

세 가지 중 하나라도 없으면 형태와 무관하게 미완성이다.

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

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

훈련 1 ●○○ — 수식 빈칸

Result. 모든 자연수 \(n\) 에 대해 \(\displaystyle\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}6\) 이다.

증명. \(P(n)\) 을 위 등식이라 하고 약한 귀납으로 보인다.

(기저) \(n = 1\) 일 때 좌변은 \(1^2 = 1\), 우변은 \(\frac{1 \cdot 2 \cdot 3}6 = \underline{\quad(1)\quad}\) 이므로 \(P(1)\) 이 참이다.

(귀납 단계) \(P(n)\) 을 가정하자. 마지막 항을 떼어 내면

\[ \sum_{i=1}^{n+1} i^2 = \left(\sum_{i=1}^{n} i^2\right) + \underline{\quad(2)\quad} = \frac{n(n+1)(2n+1)}6 + (n+1)^2 \]

이고, 공통 인수 \((n+1)\) 로 묶으면

\[ = (n+1) \cdot \frac{n(2n+1) + 6(n+1)}6 = (n+1) \cdot \frac{2n^2 + 7n + 6}6 \]

이다. 여기서 \(2n^2 + 7n + 6 = (n+2)\big(\underline{\quad(3)\quad}\big)\) 이므로

\[ \sum_{i=1}^{n+1} i^2 = \frac{(n+1)(n+2)(2n+3)}6 = \frac{(n+1)\big((n+1)+1\big)\big(2(n+1)+1\big)}6 \]

이고, 이것이 곧 \(P(n+1)\) 이다. 기저 단계와 귀납 단계가 성립하므로 귀납의 원리에 의해 모든 자연수에서 등식이 성립한다. \(\blacksquare\)

이 증명의 가정 소비처는 첫 등호 뒤에서 \(\sum_{i=1}^n i^2\) 을 \(\underline{\quad(4)\quad}\) 로 바꾼 순간이다. 검산: \(n = 3\) 에서 좌변은 \(1 + 4 + 9 = 14\) 이고 우변은 \(\frac{3 \cdot 4 \cdot 7}6 = \underline{\quad(5)\quad}\) 이다.

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

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

Result. 모든 자연수 \(n\) 에 대해 \(4 \mid (5^n - 1)\) 이다.

증명. 이 명제가 거짓인 자연수가 존재한다고 가정하고, 그런 자연수 전체의 집합을 \(R\) 라 하자. \(R\) 는 공집합이 아닌 자연수 집합이므로 \(\underline{\quad(1)\quad}\) 에 의해 최소원소 \(m\) 이 존재한다.

\(n = 1\) 일 때 \(5^1 - 1 = 4\) 이고 \(4 \mid 4\) 이므로 \(1 \notin R\) 이다. 따라서 \(\underline{\quad(2)\quad}\) 이고, \(m - 1\) 은 자연수다 [걸음 \(\underline{\quad(3)\quad}\)].

\(m\) 의 최소성에 의해 \(m - 1 \notin R\) 이므로 \(4 \mid (5^{m-1} - 1)\) 이고, 나누어떨어짐의 정의에 의해 \(5^{m-1} - 1 = 4k\) 인 정수 \(k\) 가 존재한다. 그러면

\[ 5^m - 1 = 5 \cdot 5^{m-1} - 1 = 5\big(\underline{\quad(4)\quad}\big) - 1 = 20k + 4 = \underline{\quad(5)\quad} \]

이고, \(5k + 1\) 은 정수이므로 [근거 \(\underline{\quad(6)\quad}\)] \(4 \mid (5^m - 1)\) 이다. 곧 \(m \notin R\) 이며, 이것은 \(m \in R\) 와 충돌하므로 모순이다.

따라서 \(R = \varnothing\) 이고, \(\underline{\quad(7)\quad}\). \(\blacksquare\)

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

이번에는 형태를 고르는 것부터 시작한다. §1.6의 세 물음과 확인 5의 보폭 계산이 그대로 필요하다.

Result. \(24\) 이상의 모든 정수 \(n\) 은 \(n = 5a + 7b\) 인 음이 아닌 정수 \(a, b\) 로 나타낼 수 있다.

\(23\) 까지는 이렇게 되지 않는 정수가 있다 — 예컨대 \(23\) 은 \(5a + 7b\) 꼴이 아니다 (\(b = 0, 1, 2, 3\) 을 각각 넣어 보면 \(23, 16, 9, 2\) 중 어느 것도 \(5\) 의 배수가 아니다).

증명의 뼈대. 각 칸을 통째로 채운다.

• ① 형태 판정과 그 이유: \(\underline{\quad(1)\quad}\)

• ② 기저: 몇 개를 두어야 하는지와 각각의 표현: \(\underline{\quad(2)\quad}\)

• ③ 귀납 단계: \(\underline{\quad(3)\quad}\)

• ④ 마무리: \(\underline{\quad(4)\quad}\)

(문제 12가 같은 뼈대를 3원\(\cdot\)5원 무대에서 다룬다 — 보폭이 달라지면 기저 개수가 어떻게 달라지는지 두 문제를 나란히 놓고 확인한다.)

연습문제 (20문항)

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 형태마다 채점 항목이 정해져 있다.

약한 귀납: 기저의 좌\(\cdot\)우변 계산 + 쪼개기 줄 + 가정 소비처를 짚을 수 있는가 + 원리 인용.

강한 귀납: 가정의 폭을 “\(n_0 \le i \le n\) 인 모든 \(i\)” 로 정확히 적었는가 + 기저 개수가 보폭과 맞는가 + 쓴 항이 가정 안에 있는지 확인했는가.

최소 반례법: 다섯 걸음 전부 + 최소원리 인용 + 충돌한 두 문장의 지목 + 기저 배제.

어느 형태든 “가정에 의해”라고 적힌 줄을 손가락으로 짚을 수 없으면 미완성이다.

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

기본 ●○○

1. [백지] 약한 귀납의 원리, 강한 귀납법, 최소 반례법의 다섯 걸음, 그리고 §1.6의 세 형태 대응표를 쓰시오.

힌트

서식은 걸음의 목록만 외우면 절반이다. 걸음마다 “이것을 빼면 무엇이 무너지는가”를

함께 적어 두면, 일부를 잊었을 때 나머지에서 복구할 수 있다. §1.2와 §1.4의 두 해부

표가 그 복구의 재료다.

2. 다음 각 명제에 어느 형태(약한 귀납 / 강한 귀납 / 최소 반례법)가 자연스러운지 판정하고, 판정의 이유를 한 줄씩 쓰시오 (증명은 하지 말 것). (a) \(\displaystyle\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}2\right)^2\) (b) 모든 정수 \(n \ge 2\) 는 소수들의 곱이다 (c) 피보나치 수열에서 \(F_n < 2^n\) (d) \(4a + 5b\) (\(a, b\) 는 음이 아닌 정수) 꼴로 표현되지 않는 최대 정수는 \(11\) 이다

힌트

판정의 절차는 §1.6의 세 물음이다. 각 명제에서 \(P(n+1)\) 을 쪼개는 첫 줄만 적어 보고,

그 줄이 요구하는 이전 항이 몇 개이며 그중 직전이 아닌 것이 있는지 세면 된다.

(d)는 다른 셋과 성격이 다르다 — “최대”라는 낱말이 요구하는 것이 두 가지임에 유의한다.

3. 예제 2.1(홀수의 합)을 백지에 재현하시오. 쪼개기 줄과 가정 소비처를 각각 표시하시오.

힌트

다섯 걸음 중 쪼개기는 확인 14가 만든 줄이고, 가정 소비처는 확인 15의 첫 등호다.

쪼개기에서 떼어 내는 항은 새로 늘어난 항 \(2(n+1)-1\) 이지 \(2n-1\) 이 아니다.

마지막 줄에서 원 명제를 다시 적었는지까지가 채점 대상이다.

4. 빈칸 사다리의 훈련 1~3을 백지에서 완성하시오.

힌트

훈련 1은 (4)가 유일한 가정 소비처이므로 그 한 줄을 먼저 정하고 나머지를 맞춘다.

훈련 2는 (4)가 최소성 소비처이고, 그 앞의 (2) 기저 배제가 없으면 그 줄이 뜻을 잃는다.

훈련 3은 §1.6의 세 물음으로 형태를 고른 뒤 확인 5의 보폭 계산으로 기저 개수를 정한다.

5. 예제 2.3(최소 반례법)을 백지에 재현하고, 예제 2.1과 나란히 놓아 다섯 걸음이 약한 귀납의 어느 걸음에 대응하는지 표로 대조하시오.

힌트

대조표의 행은 확인 8에서 이미 두 개를 만들었다. 나머지 걸음(①②⑤)이 약한 귀납의

어디에 해당하는지 — 또는 대응하는 것이 없는지 — 를 채우면 표가 완성된다.

6. 모든 자연수 \(n\) 에 대해 \(3 \mid (n^3 - n)\) 임을 약한 귀납으로 증명하시오.

힌트

쪼개기 줄은 S14주차 예제 2.2가 다룬 그 계산이다. \((n+1)^3 - (n+1)\) 을 전개한 뒤

\(n^3 - n\) 덩어리가 그대로 보이도록 재그룹하면 남는 것이 \(3n^2 + 3n\) 이다. 나머지 항이

\(3\) 의 배수임을 별도로 보이는 것이 가정 소비 다음의 일이다.

표준 ●●○

7. 모든 자연수 \(n\) 에 대해 \(\displaystyle\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}2\right)^2\) 임을 약한 귀납으로 증명하시오 (S14주차 문제 8).

힌트

가정을 대입하면 \(\left(\frac{n(n+1)}2\right)^2 + (n+1)^3\) 이 된다. 공통 인수

\((n+1)^2\) 으로 묶으면 남는 것이 \(\frac{n^2}4 + (n+1)\) 이고, 통분하면 완전제곱이 나온다.

8. 모든 정수 \(n \ge 4\) 에 대해 \(2^n \ge n^2\) 임을 귀납으로 증명하시오.

힌트

기저는 \(n = 4\) 다 (\(16 \ge 16\)). 귀납 단계에서 가정을 소비하면 \(2^{n+1} \ge 2n^2\)

까지만 간다. 도착점은 \((n+1)^2\) 이므로 \(2n^2 \ge (n+1)^2\) 을 따로 보여 이어

붙여야 한다 — 1권 32주차에서 연결 부등식이라 부른 그 조각이다. 정리하면

\(n^2 - 2n - 1 \ge 0\), 곧 \((n-1)^2 \ge 2\) 를 보이는 문제가 된다.

9. \(F_1 = F_2 = 1\), \(F_{n+2} = F_{n+1} + F_n\) 으로 정의된 피보나치 수열에 대해, 모든 자연수 \(n\) 에서 \(F_n \le 2^{n-1}\) 임을 증명하시오. 기저가 두 개 필요한 이유도 쓰시오 (S14주차 문제 15의 상계를 조인 판이다).

힌트

점화식이 두 항을 참조하므로 보폭이 \(2\) 이고, 따라서 기저도 두 개다(확인 5의 계산).

귀납 단계에서 \(2^n + 2^{n-1}\) 을 \(2^{n-1}\) 로 묶으면 \(3 \cdot 2^{n-1}\) 이 되고,

도착점 \(2^{n+1} = 4 \cdot 2^{n-1}\) 과 계수만 비교하면 끝난다.

10. 다음 제시된 증명을 C5주차의 증명 평가 다섯 걸음으로 채점하시오. 판정은 옳음\(\cdot\)틀림\(\cdot\)불완전 가운데 하나로 적고, 결함이 있는 줄을 지목한 뒤 병명(S11주차의 어휘)과 수리를 덧붙이시오.

Result. 모든 자연수 \(n\) 에 대해 \(\displaystyle\sum_{i=1}^n i = \frac{n(n+1)}2\) 이다.

증명. 귀납 단계에서 \(\sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}2\) 임을 보이자. 등차수열의 합 공식에 의해 이는 참이다. \(\blacksquare\)

힌트

검사할 질문은 둘이다. 다섯 걸음 중 몇 개가 답안에 실제로 있는가. 그리고 인용된

“등차수열의 합 공식”은 근거 목록의 몇 번이며, 이 과정에서 증명된 적이 있는가.

확인 3이 같은 답안을 다루었다.

11. 모든 자연수 \(n\) 에 대해 \(\displaystyle\sum_{i=1}^n (2i-1) = n^2\) 임을 최소 반례법으로 증명하시오.

힌트

예제 2.3의 다섯 걸음을 그대로 옮기고 재료만 바꾼다. 걸음 ④에서 더할 항은

\(2m - 1\) 이다 — 확인 14에서 본 대로, 떼어 낼 항은 새로 늘어난 항이다.

기저 배제(걸음 ③)를 빼면 확인 7의 붕괴가 재연된다.

12. \(8\) 이상의 모든 정수는 3원 동전과 5원 동전으로 지불할 수 있음을 강한 귀납으로 증명하시오. 기저를 몇 개 잡아야 하는지 결정한 근거도 쓰시오.

힌트

기저 개수는 §1.3의 삭제 실험(확인 5)이 이미 계산했다. 귀납 단계에서 쓸 항은

\(P(n-2)\) 이므로, 그 항이 가정의 사정권 안에 있으려면 \(n - 2 \ge 8\), 곧

\(n + 1 \ge 11\) 이어야 한다. 그 아래 세 값을 손으로 채운다.

13. 모든 자연수 \(n\) 에 대해 \(6 \mid (n^3 + 5n)\) 임을 증명하시오.

힌트

쪼개기 줄에서 \((n+1)^3 + 5(n+1)\) 을 전개해 \(n^3 + 5n\) 덩어리를 드러내면 남는 것이

\(3n^2 + 3n + 6\) 이다. \(3n^2 + 3n = 3n(n+1)\) 이고, \(n(n+1)\) 이 짝수라는 사실(§1.7의

목록, 1권 1주차 문제 16)을 쓰면 이 항이 \(6\) 의 배수임이 나온다.

14. \(x^2 = 3y^2\) 인 양의 정수 \(x, y\) 는 존재하지 않음을 무한강하로 증명하시오.

힌트

C7주차 문제 17의 \(\sqrt2\) 판을 \(\sqrt3\) 으로 옮긴 것이다. 최소로 잡을 양은 \(x\) 다.

\(3 \mid x^2\) 에서 \(3 \mid x\) 로 가는 줄에 유클리드 보조정리(\(p = 3\))를 인용한다.

\(x = 3x'\) 을 대입하고 정리하면 \(y^2 = 3x'^2\) 이 되어 같은 논증이 \(y\) 에서 한 번 더 돈다.

도전 ●●●

15. 모든 정수 \(n \ge 2\) 는 소수인 약수를 가짐을 강한 귀납으로 증명하시오.

힌트

예제 2.2와 형태도 무대도 같지만 결론이 더 약하다 — 분해 전체가 아니라 소인수

하나만 있으면 된다. 그래서 합성수 \(n+1 = ab\) 에서 \(a\) 에만 가정을 쓰면 되고,

마지막에 \(p \mid a\) 와 \(a \mid (n+1)\) 을 이어 붙이는 데 나누어떨어짐의 추이성

(1권 2주차)이 필요하다. 이 명제는 S11주차 문제 15(소수의 무한성)가 부품으로 쓰는

사실이고, 1권 33주차 문제 6이 같은 것을 따름정리로 유도한다.

16. 어느 세 점도 한 직선 위에 있지 않은 \(n\) 개의 점에 대해, 그들을 서로 잇는 선분의 개수가 \(\binom n2\) 임을 귀납으로 증명하시오.

힌트

기저는 \(n = 2\) 다. 귀납 단계에서 \(n+1\) 번째 점을 추가하면 기존 \(n\) 개 각각과 새

선분이 하나씩 생기므로 늘어나는 개수가 \(n\) 이다. 남는 일은 \(\binom n2 + n = \binom{n+1}2\)

을 §1.7의 이항계수 값으로 계산해 확인하는 것뿐이다. (C16주차 조합론의 예고편이다.)

17. \(x > -1\) 인 모든 실수 \(x\) 와 모든 자연수 \(n\) 에 대해 \((1+x)^n \ge 1 + nx\) 임을 증명하시오 (베르누이 부등식). 조건 \(x > -1\) 이 귀납 단계의 어느 줄에서 소비되는지 명시하시오.

힌트

가정의 양변에 \(1+x\) 를 곱하는 것이 쪼개기다. 부등식의 양변에 곱할 때는 곱하는

수의 부호를 먼저 밝혀야 부등호 방향이 보존된다 — 조건 \(x > -1\) 이 소비되는

자리가 정확히 거기다. 곱한 뒤 남는 \(nx^2\) 을 버리는 것이 마지막 걸음이다.

18. 다음 제시된 증명의 결함을 찾고, 무엇이 무너졌는지 지적하시오.

Result. 모든 자연수 \(n\) 에 대해 \(n < 100\) 이다.

증명. 강한 귀납으로 보인다. 기저는 \(n = 1\) 이고 \(1 < 100\) 이다. 귀납 단계에서 \(1, \ldots, n\) 이 모두 \(100\) 보다 작다고 가정하면 \(n < 100\) 이므로 \(n + 1 \le 100\) 이고, 따라서 성립한다. \(\blacksquare\)

힌트

결론이 명백히 거짓이므로 오류는 반드시 있다. 그런데 기저는 옳으니 남은 곳은 귀납

단계뿐이다. 귀납 단계는 “모든 \(n\) 에 대해” 성립해야 하는 조건문임을 떠올리고,

\(n\) 에 구체적인 값을 하나씩 넣어 조건문이 거짓이 되는 \(n\) 을 찾는다. 답안이 도착한

곳(\(n+1 \le 100\))과 도착해야 할 곳(\(n+1 < 100\))의 차이도 함께 본다.

19. 모든 자연수 \(n\) 에 대해 \(n! \ge 2^{n-1}\) 임을 (a) 약한 귀납으로 (b) 최소 반례법으로 각각 증명하고, 어느 쪽이 자연스러운지 이유와 함께 논하시오.

힌트

두 풀이의 계산은 같다. \((n+1)! = (n+1) \cdot n!\) 이라는 쪼개기가 (a)의 관절이고,

\(m! = m \cdot (m-1)!\) 이 (b)의 관절이다. 가정을 대입한 뒤 \(n + 1 \ge 2\) (또는

\(m \ge 2\))를 써서 계수를 \(2\) 로 눌러 놓는 줄이 양쪽 모두에 필요하다. 논의에서는

§1.6의 첫째 물음이 어느 쪽을 가리키는지를 근거로 삼는다.

20. (서술) (a) “귀납 단계 = 조건문 증명”(S14주차)을 예제 2.1의 특정 줄로 뒷받침하고, “최소 반례법 = 귀납의 귀류판”을 예제 2.3의 특정 줄로 뒷받침한 뒤, 두 서식이 같은 명제를 증명한다는 것을 세 문장 이내로 쓰시오. (b) 강한 귀납이 필요한 이유(직전이 아닌 이전 항에 대한 의존)를 예제 2.2로 두 문장 이내로 설명하시오.

힌트

서술 문항의 답안은 개념 절의 문장을 옮겨 적는 것이 아니라, **지정된 예제의 어느

줄이 그 개념의 근거인지** 짚는 글이다. (a)는 예제 2.1에서 “가정을 선언한 줄”과

“가정을 소비한 줄”, 예제 2.3에서 “기저를 배제한 줄”과 “최소성을 소비한 줄”을 각각

짚어야 점수가 된다. (b)는 예제 2.2에서 “부등식을 \(2 \le a \le n\) 으로 정리한 줄”이

왜 필요했는지를 짚는다.

백지 재현 — 복습 프로토콜

이 과정의 한 주는 다섯 날로 나뉜다. 교안만 보는 주가 아니라 원서와 교안을 번갈아 읽는 주이므로, 백지 재현은 마지막 날에 놓인다.

요일	할 일
1일차	원서 Chartrand 6장 통독 — 모르는 문장은 표시만 하고 통과한다
2일차	교안 §0~§2 — 개념과 예제. 확인 상자를 연필로 먼저 채운다
3일차	원서 6장 재독 — 1일차에 표시한 문장을 해결하고, 원서 연습문제 몇 개를 직접 시도한다
4일차	교안 §3 빈칸 사다리와 §4 연습문제 20문항
5일차	백지 재현 1차(틀 카드)\(\cdot\)2차(완전 백지) + 체크리스트

1차 시도 — 틀 카드 허용. 세 형태의 원리(정의 8.1\(\cdot\)8.2\(\cdot\)8.3)와 §1.6의 세 물음만 한 장에 적어 펴 놓고, 예제 2.2를 처음부터 끝까지 적는다. 본문과 계산은 보지 않는다.

2차 시도 — 완전 백지. 아무것도 보지 않고 수행한다.

• 정의 8.1(약한 귀납)과 정의 8.2(강한 귀납)를 \(n_0\) 을 명시한 꼴로 썼고, 두 정의의 차이가 어디인지 손가락으로 짚었다.

• 최소 반례법의 다섯 걸음을 순서대로 썼고, 걸음 ③을 빼면 무엇이 무너지는지 한 문장으로 적었다.

• 예제 2.1을 재현하면서 쪼개기 줄과 가정 소비처를 각각 표시했다.

• 예제 2.2를 재현했고, 약한 귀납으로 안 되는 이유를 “가정의 폭”이라는 말로 적었다.

• 예제 2.3을 산문으로 재현했고, 충돌한 두 문장을 이름으로 지목했다.

• 세 형태의 대응표(§1.6)를 그렸고, 셋의 논리적 힘이 같다는 것과 그 근거를 적었다.

• 강한 귀납에서 기저 개수를 정하는 것이 무엇인지 쓰고, 3원\(\cdot\)5원 무대에서 그 개수를 계산했다.

• 무한강하가 최소 반례법의 어느 걸음의 변주인지 적었다.

• 원서 6장을 두 번 읽었고, 1일차에 표시한 문장이 모두 해결되었다.

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

막힌 지점	처방
어느 형태를 쓸지 정하지 못한다	§1.6의 세 물음 — \(P(n+1)\) 을 쪼개는 첫 줄만 적어 보면 필요한 이전 항이 드러난다
귀납 단계에서 다음 줄이 나오지 않는다	§1.2의 걸음 ③ — 막히는 자리의 대부분이 쪼개기다. 도착점의 식에서 가정의 식을 찾는다
답안을 다 썼는데 가정 소비처를 못 짚는다	확인 3 — 병명은 가정 미소비다. 그 답안은 순환일 가능성이 높다
기저를 몇 개 잡아야 할지 모른다	확인 5 — 귀납 단계의 목표가 \(P(N)\) 이고 그것이 쓰는 가장 깊은 항이 \(P(N-s)\) 이면 보폭은 \(s\) 이고 기저도 \(s\) 개다
최소 반례법의 첫 문장이 나오지 않는다	정의 8.3의 걸음 ①② — 개시문은 “반례가 존재한다고 가정하자”와 “최소원리에 의해” 두 줄로 정해져 있다
모순이라고 적었는데 당사자를 못 짚는다	예제 2.3의 마지막 두 줄 — 충돌한 두 문장은 “\(m \in R\)” 과 “\(m \notin R\)” 이다
부등식 귀납에서 도착점에 못 닿는다	문제 8의 힌트 — 가정 소비 뒤에 연결 부등식을 따로 세워 이어 붙인다

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

해설

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

빈칸 사다리 — 훈련 1

(1) \(1\) (2) \((n+1)^2\) (3) \(2n+3\) (4) \(\frac{n(n+1)(2n+1)}6\) (5) \(14\)

※ (2)에서 떼어 낼 항은 \(i = n+1\) 일 때의 항이므로 \((n+1)^2\) 이다. \(n^2\) 으로 적으면 \(i = n\) 일 때의 항이 되어 아무것도 늘지 않는다. (3)의 인수분해는 \(2n^2 + 7n + 6 = (n+2)(2n+3)\) 이고, 곱을 전개해 \(2n^2 + 3n + 4n + 6 = 2n^2 + 7n + 6\) 으로 검산한다. (4)가 이 훈련의 가정 소비처이고, 훈련 전체에서 가정 \(P(n)\) 이 쓰인 자리는 여기 한 곳뿐이다.

빈칸 사다리 — 훈련 2

(1) 최소원리 (정렬성) (2) \(m \ge 2\) (3) ③ (기저 배제) (4) \(4k+1\) (5) \(4(5k+1)\) (6) ② (닫힘성) (7) 모든 자연수 \(n\) 에 대해 \(4 \mid (5^n - 1)\) 이다

※ (4)는 가정 소비처다 — \(5^{m-1} - 1 = 4k\) 를 \(5^{m-1} = 4k+1\) 로 옮겨 대입한 순간에만 최소성이 쓰였다. (5)에서 \(20k + 4 = 4(5k+1)\) 로 묶는 것이 도착점의 꼴 “\(4 \times (\text{정수})\)” 를 만드는 줄이고, 그 괄호 안이 정수임을 밝히는 것이 (6)이다. 검산: \(n = 3\) 에서 \(5^3 - 1 = 124 = 4 \cdot 31\) 이다.

빈칸 사다리 — 훈련 3

(1) 강한 귀납. \(n+1\) 을 \((n+1) - 5\) 로 되돌려 가정을 쓰므로 귀납 단계가 실제로 사용하는 항은 \(P(n-4)\) 이고, 이것은 직전 항이 아니다. §1.6의 둘째 물음에 걸린다.

(2) 기저는 다섯 개 — \(24, 25, 26, 27, 28\). 되돌아보는 보폭이 \(5\) 이므로 그만큼의 칸을 손으로 채워야 재귀가 돈다(확인 5의 계산). 각각의 표현은 \(24 = 5 \cdot 2 + 7 \cdot 2\), \(25 = 5 \cdot 5\), \(26 = 5 + 7 \cdot 3\), \(27 = 5 \cdot 4 + 7\), \(28 = 7 \cdot 4\) 이다.

(3) 귀납 단계. \(n \ge 28\) 이라 하고, \(24 \le i \le n\) 인 모든 정수 \(i\) 가 \(5a+7b\) 꼴이라고 가정하자. 이때 \(n + 1 \ge 29\) 이므로 \((n+1) - 5 = n - 4 \ge 24\) 이고, 가정에 의해 \(n - 4 = 5a' + 7b'\) 인 음이 아닌 정수 \(a', b'\) 이 존재한다. 그러면 \(n + 1 = (n-4) + 5 = 5(a'+1) + 7b'\) 이고 \(a' + 1\) 과 \(b'\) 은 음이 아닌 정수이므로 \(P(n+1)\) 이 참이다.

(4) 마무리. 기저 단계와 귀납 단계가 모두 성립하므로, 강한 귀납법에 의해 \(24\) 이상의 모든 정수는 \(5a + 7b\) 꼴이다. \(\blacksquare\)

※ 문제 12와 나란히 놓으면 보폭과 기저 개수의 관계가 보인다. 3원\(\cdot\)5원 무대에서는 작은 동전이 \(3\) 이라 보폭이 \(3\) 이고 기저가 셋(\(8, 9, 10\))이며, 5원\(\cdot\)7원 무대에서는 작은 동전이 \(5\) 라 보폭이 \(5\) 이고 기저가 다섯이다.

문제 1

접근. 백지 문항의 채점은 문장의 유무가 아니라 조각의 유무로 한다. 네 항목 각각에서 빠지면 무너지는 조각이 무엇인지 §1.2와 §1.4의 해부 표로 확인해 두면, 일부를 잊었을 때 나머지에서 복구할 수 있다.

풀이. 아래 네 항목이 모두 있어야 만점이다.

① 약한 귀납의 원리(정의 8.1). “정수 \(n_0\) 이상의 모든 \(n\) 에 대해 \(P(n)\) 을 보이려면 ㉠ \(P(n_0)\) 이 참이고 ㉡ \(n_0\) 이상의 모든 \(n\) 에 대해 \(P(n) \Rightarrow P(n+1)\) 임을 보이면 충분하다.” 채점 조각은 \(n_0\) 의 명시와 ㉡의 “모든 \(n\) 에 대해”다. ㉡에서 “모든”이 빠지면 문제 18의 결함을 진단할 수 없다.

② 강한 귀납법(정의 8.2). 귀납 단계의 출발점이 “\(n_0 \le i \le n\) 인 모든 \(i\) 에 대한 \(P(i)\)” 이고, 기저가 여러 개일 수 있다는 것. 채점 조각은 가정의 폭을 구간으로 적었는가와 기저 개수를 보폭이 정한다고 적었는가다.

③ 최소 반례법의 다섯 걸음(정의 8.3). 귀류 개시 \(\to\) 최소 반례 확보(최소원리) \(\to\) 기저 배제 \(\to\) 최소성 소비와 모순 \(\to\) 결론 복귀. 채점 조각은 걸음 ③의 존재다 — 이것이 없으면 확인 7의 붕괴가 재연된다.

④ 세 형태의 대응표(§1.6). 형태 \(\cdot\) 귀납 단계의 출발점 \(\cdot\) 논법의 방향 세 열을 채우고, 셋이 최소원리에서 나오며 논리적 힘이 같다는 문장을 덧붙인다.

복기. 서식 암기의 검사법은 “빼면 무엇이 무너지는가”를 걸음마다 한 줄씩 말해 보는 것이다. 말할 수 있으면 그 걸음은 외운 것이고, 말할 수 없으면 적어만 둔 것이다.

문제 2

접근. 판정 절차는 §1.6의 세 물음이다. 명제마다 \(P(n+1)\) 을 쪼개는 첫 줄만 적어 보고, 그 줄이 요구하는 이전 항의 개수와 위치를 센다. 증명을 하지 않고도 판정만으로 답이 되는 문항이므로, 이유 한 줄이 곧 채점 대상이다.

풀이.

(a) 약한 귀납. 쪼개기 줄은 \(\sum_{i=1}^{n+1} i^3 = \left(\sum_{i=1}^{n} i^3\right) + (n+1)^3\) 이다. 요구하는 이전 항은 \(P(n)\) 하나이고 그것이 직전이므로 첫째 물음에서 걸린다.

(b) 강한 귀납. 쪼개기 줄은 \(n+1 = ab\) (\(2 \le a \le n\), \(2 \le b \le n\))이다. 요구하는 항이 \(P(a)\) 와 \(P(b)\) 둘이고, 그것이 구간의 어디인지 미리 알 수 없다. 둘째 물음에 걸린다.

(c) 강한 귀납. 쪼개기 줄은 점화식 \(F_{n+2} = F_{n+1} + F_n\) 자체다. 요구하는 항이 \(P(n)\) 과 \(P(n+1)\) 둘이므로 둘째 물음에 걸리고, 보폭이 \(2\) 이므로 기저도 두 개다.

(d) 강한 귀납 + 유한 검사. “최대”라는 낱말은 두 가지를 요구한다. ㉠ \(11\) 자신이 \(4a+5b\) 꼴이 아님 — 이것은 \(b = 0, 1, 2\) 에서 각각 \(11, 6, 1\) 이 되어 어느 것도 \(4\) 의 배수가 아니라는 유한 검사로 끝난다. ㉡ \(12\) 이상의 모든 정수는 그 꼴임 — 이쪽이 무한 주장이고, 귀납 단계가 \(P(n-3)\) 을 쓰므로 보폭 \(4\) 의 강한 귀납이다(기저 \(12, 13, 14, 15\)). 1권 33주차 문제 12가 ㉡을 다룬다.

복기. 판정에서 최소 반례법이 답이 되는 경우는 (d)처럼 “최대”\(\cdot\)”없다”가 들어간 명제이거나, 사다리를 걸 변수 자체가 없는 명제다. (d)의 ㉡은 사다리가 있으므로 굳이 귀류로 갈 이유가 없다 — 형태 선택은 답안이 짧아지는 쪽을 고르는 일이다.

문제 3

접근. 재현 문항의 채점 대상은 결과가 아니라 걸음이다. 다섯 걸음이 모두 있는가, 그리고 쪼개기 줄과 가정 소비처를 스스로 지목할 수 있는가를 본다.

풀이. \(P(n)\) 을 “\(\sum_{i=1}^n (2i-1) = n^2\)” 이라 하자.

(기저) \(n = 1\) 일 때 좌변은 \(2 \cdot 1 - 1 = 1\), 우변은 \(1^2 = 1\) 이므로 \(P(1)\) 이 참이다.

(귀납 단계) \(n\) 을 자연수라 하고 \(P(n)\) 을 가정하자. 그러면

\[ \sum_{i=1}^{n+1}(2i-1) = \left(\sum_{i=1}^{n}(2i-1)\right) + \big(2(n+1)-1\big) = n^2 + (2n+1) = (n+1)^2 \]

이므로 \(P(n+1)\) 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 \(n\) 에 대해 \(\sum_{i=1}^n (2i-1) = n^2\) 이다. \(\blacksquare\)

표시. 쪼개기 줄은 첫 등호가 있는 줄이고, 가정 소비처는 둘째 등호에서 \(\sum_{i=1}^n (2i-1)\) 을 \(n^2\) 으로 바꾼 지점이다. 셋째 등호는 완전제곱 정리이므로 근거 ③이며 가정과 무관하다.

검산. \(n = 4\) 에서 \(1+3+5+7 = 16 = 4^2\) 이다.

문제 4

접근. 사다리의 자가 채점은 답을 맞혔는가가 아니라 관절을 짚었는가로 한다. 훈련마다 관절이 하나씩 있고, 그 줄을 틀리면 나머지가 다 맞아도 증명이 서지 않는다.

풀이. 답은 위의 “빈칸 사다리 — 훈련 1~3” 항목에 있다. 대조할 때 다음 세 가지를 확인한다.

훈련 1의 관절 — (2). 떼어 낼 항이 \((n+1)^2\) 인가. \(n^2\) 으로 적었다면 새로 늘어난 항이 아니라 이미 합 안에 있던 항을 떼어 낸 것이므로, 그 아래의 계산 전체가 무너진다.

훈련 2의 관절 — (2)와 (3). 기저 배제를 적었는가. \(m \ge 2\) 를 확보하지 않으면 \(m - 1\) 이 자연수라는 보장이 없고, 그러면 “\(m-1\) 은 반례가 아니다”라는 문장이 아무것도 말하지 못한다(확인 7).

훈련 3의 관절 — (2)의 개수. 기저를 다섯 개 두었는가. 하나만 두면 \(n+1\) 이 \(25, 26, 27, 28\) 일 때 \((n+1) - 5\) 가 \(24\) 보다 작아 가정의 사정권 밖으로 나간다 — 확인 5의 삭제 실험이 그대로 재연된다.

복기. 세 관절은 각각 “쪼개기”, “기저 배제”, “기저 개수”다. §1.2\(\cdot\)§1.4의 해부 표에서 “빼면 무너지는 것”으로 적혀 있던 항목이 사다리에서 그대로 채점 항목이 된다.

문제 5

접근. 대조표를 만들려면 먼저 두 증명을 각각 재현해야 한다. 재현한 뒤에는 걸음 단위로 줄을 짝지어 본다 — 계산이 같고 방향만 다른 짝이 두 개 나온다(확인 8).

풀이 — 재현. 예제 2.3의 증명은 다음과 같다. 공식이 성립하지 않는 자연수 전체의 집합을 \(R\) 라 하고 \(R \neq \varnothing\) 이라 가정하자. 최소원리에 의해 \(R\) 에 최소원소 \(m\) 이 있다. \(n = 1\) 에서 \(1 = \frac{1 \cdot 2}2\) 이므로 \(1 \notin R\) 이고 \(m \ge 2\) 이다. 최소성에 의해 \(m - 1 \notin R\) 이므로 \(\sum_{i=1}^{m-1} i = \frac{(m-1)m}2\) 이고,

\[ \sum_{i=1}^{m} i = \frac{(m-1)m}{2} + m = \frac{m(m+1)}{2} \]

이므로 \(m \notin R\) 이다. \(m \in R\) 와 충돌하므로 모순이고, 따라서 \(R = \varnothing\) 이다. \(\blacksquare\)

풀이 — 대조표.

최소 반례법 (예제 2.3)	약한 귀납 (예제 2.1)	관계
① 반례가 존재한다고 가정	대응하는 것 없음	귀류 개시는 최소 반례법에만 있다
② 최소원리로 최소 반례 \(m\) 확보	대응하는 것 없음	최소원리를 명시적으로 인용하는 유일한 걸음
③ \(1 \notin R\) 확인 \(\to\) \(m \ge 2\)	기저 \(P(1)\) 확인	계산이 같다. 쓰는 곳만 다르다
④ \(P(m-1) \Rightarrow P(m)\) 유도 후 모순	\(P(n) \Rightarrow P(n+1)\) 유도	계산이 같다. 방향만 뒤집혔다
⑤ 반례 없음 \(\to\) 원 명제	원리 인용 \(\to\) 원 명제	결론 선언은 양쪽 모두에 있다

복기. 두 서식의 실질적 차이는 ①②의 두 줄뿐이다. 같은 계산을 위로 타고 올라가면 귀납이고, 아래에서 이미 참이었다는 사실로 최소성을 깨뜨리면 최소 반례법이다. 그래서 최소 반례법을 귀납의 귀류판이라 부른다(S14주차 문제 14).

문제 6

접근. 나누어떨어짐 명제이므로 \(P(n)\) 을 “\(n^3 - n = 3m\) 인 정수 \(m\) 이 존재한다”로 번역해 두고 시작한다. 쪼개기는 \((n+1)^3 - (n+1)\) 을 전개해 \(n^3 - n\) 덩어리를 드러내는 일이고, 남는 항이 \(3\) 의 배수임을 별도로 밝히는 것이 마무리다.

풀이. \(P(n)\) 을 “\(3 \mid (n^3 - n)\)” 이라 하자.

(기저) \(n = 1\) 일 때 \(n^3 - n = 1 - 1 = 0\) 이고 \(0 = 3 \cdot 0\) 이므로 \(3 \mid 0\) 이다. 따라서 \(P(1)\) 이 참이다.

(귀납 단계) \(n\) 을 자연수라 하고 \(P(n)\) 을 가정하자. 곧 \(n^3 - n = 3m\) 인 정수 \(m\) 이 존재한다. 전개하면

\[ (n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3n^2 + 3n \]

이고, 가정을 대입하면

\[ (n+1)^3 - (n+1) = 3m + 3n^2 + 3n = 3\big(m + n^2 + n\big) \]

이다. \(m\) 과 \(n\) 이 정수이므로 \(m + n^2 + n\) 도 정수이고 [근거 ②], 따라서 \(3 \mid \big((n+1)^3 - (n+1)\big)\) 이다. 곧 \(P(n+1)\) 이 참이다.

기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 \(n\) 에 대해 \(3 \mid (n^3 - n)\) 이다. \(\blacksquare\)

복기. 나누어떨어짐 귀납의 리듬은 세 박자다 — 전개 \(\to\) 가정의 덩어리 드러내기 \(\to\) 남는 항에서 공통 인수 묶기. S14주차 예제 2.2가 같은 리듬이고, 문제 13이 이 리듬을 \(6\) 으로 확장한다.

검산. \(n = 3\) 에서 \(27 - 3 = 24 = 3 \cdot 8\) 이다.

문제 7

접근. 가정을 대입하면 \(\left(\frac{n(n+1)}2\right)^2 + (n+1)^3\) 이 되고, 도착점은 \(\left(\frac{(n+1)(n+2)}2\right)^2\) 이다. 양쪽 모두 \((n+1)^2\) 을 인수로 가지므로 그것으로 묶어 놓고 나머지를 비교하는 것이 계산량이 가장 적다.

풀이. \(P(n)\) 을 “\(\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}2\right)^2\)” 이라 하자.

(기저) \(n = 1\) 일 때 좌변은 \(1^3 = 1\), 우변은 \(\left(\frac{1 \cdot 2}2\right)^2 = 1\) 이므로 \(P(1)\) 이 참이다.

(귀납 단계) \(P(n)\) 을 가정하자. 마지막 항을 떼어 내고 가정을 대입하면

\[ \sum_{i=1}^{n+1} i^3 = \left(\sum_{i=1}^{n} i^3\right) + (n+1)^3 = \left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3 \]

이다. \((n+1)^2\) 으로 묶으면

\[ = (n+1)^2\left(\frac{n^2}{4} + (n+1)\right) = (n+1)^2 \cdot \frac{n^2 + 4n + 4}{4} = (n+1)^2 \cdot \frac{(n+2)^2}{4} \]

이고, 이것은 \(\left(\frac{(n+1)(n+2)}{2}\right)^2\) 이다. \(n+2 = (n+1)+1\) 이므로 이 식은 \(P(n+1)\) 의 우변과 같다. 곧 \(P(n+1)\) 이 참이다.

기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 \(n\) 에 대해 \(\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}2\right)^2\) 이다. \(\blacksquare\)

복기. 도착점의 식을 먼저 적어 두면 “무엇으로 묶을지”가 저절로 정해진다. 여기서는 도착점에 \((n+1)^2\) 이 들어 있는 것이 보였으므로 그것을 묶었다. 도착점을 적지 않고 좌변만 밀면 \(\frac{n^2(n+1)^2 + 4(n+1)^3}4\) 에서 길을 잃기 쉽다.

검산. \(n = 3\) 에서 좌변은 \(1 + 8 + 27 = 36\) 이고 우변은 \(\left(\frac{3 \cdot 4}2\right)^2 = 36\) 이다.

문제 8

접근. 부등식 귀납은 2단이다. 가정을 소비하면 중간값까지만 가고, 거기서 도착점까지는 연결 부등식을 따로 세워 이어 붙인다(1권 32주차). 여기서 중간값은 \(2n^2\) 이고 도착점은 \((n+1)^2\) 이므로, 세워야 할 연결 부등식은 \(2n^2 \ge (n+1)^2\) 이다.

풀이. \(P(n)\) 을 “\(2^n \ge n^2\)” 이라 하고 \(n_0 = 4\) 로 둔다.

(기저) \(n = 4\) 일 때 \(2^4 = 16\) 이고 \(4^2 = 16\) 이므로 \(2^4 \ge 4^2\) 이다. 따라서 \(P(4)\) 가 참이다.

(연결 부등식) \(n \ge 3\) 인 모든 정수에서 \(2n^2 \ge (n+1)^2\) 이다. 실제로

\[ 2n^2 - (n+1)^2 = n^2 - 2n - 1 = (n-1)^2 - 2 \]

이고, \(n \ge 3\) 이면 \((n-1)^2 \ge 4 > 2\) 이므로 이 값은 양수다.

(귀납 단계) \(n \ge 4\) 라 하고 \(P(n)\) 을 가정하자. 그러면

\[ 2^{n+1} = 2 \cdot 2^n \ge 2n^2 \ge (n+1)^2 \]

이다. 첫 부등호가 가정 소비처이고, 둘째 부등호가 방금 세운 연결 부등식이다 (\(n \ge 4 \ge 3\) 이므로 적용 조건이 충족된다). 곧 \(P(n+1)\) 이 참이다.

기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 \(4\) 이상의 모든 정수 \(n\) 에 대해 \(2^n \ge n^2\) 이다. \(\blacksquare\)

복기. 부등식 귀납에서 답안이 미완성이 되는 가장 흔한 자리는 연결 부등식을 세우지 않고 “\(2n^2 \ge (n+1)^2\) 이므로”로 넘어가는 곳이다. 그 부등식은 자명하지 않고 \(n \ge 3\) 에서만 성립하므로, 별도의 문단으로 증명하고 적용 조건까지 밝혀야 한다.

검산. \(n = 5\) 에서 \(32 \ge 25\), \(n = 6\) 에서 \(64 \ge 36\) 이다. 참고로 \(n = 3\) 에서는 \(8 < 9\) 이므로 기저를 \(4\) 로 잡은 것이 필수였다.

문제 9

접근. 점화식이 두 항을 참조하므로 되돌아보는 보폭이 \(2\) 이고, 확인 5의 계산에 따라 기저도 두 개다. 귀납 단계에서는 \(F_{n+2}\) 를 얻는 데 \(P(n)\) 과 \(P(n+1)\) 이 함께 필요하므로 가정의 폭을 구간으로 잡는다.

풀이. \(P(n)\) 을 “\(F_n \le 2^{n-1}\)” 이라 하자.

(기저) \(F_1 = 1\) 이고 \(2^{1-1} = 2^0 = 1\) 이므로 \(F_1 \le 2^0\) 이다. \(F_2 = 1\) 이고 \(2^{2-1} = 2\) 이므로 \(F_2 \le 2^1\) 이다. 따라서 \(P(1)\) 과 \(P(2)\) 가 참이다.

(귀납 단계) \(n \ge 1\) 이라 하고, \(1 \le i \le n+1\) 인 모든 \(i\) 에 대해 \(P(i)\) 를 가정하자. 특히 \(F_n \le 2^{n-1}\) 과 \(F_{n+1} \le 2^n\) 을 쓸 수 있다. 점화식에 의해

\[ F_{n+2} = F_{n+1} + F_n \le 2^n + 2^{n-1} = 2^{n-1}(2 + 1) = 3 \cdot 2^{n-1} \]

이고, \(3 < 4\) 이므로

\[ 3 \cdot 2^{n-1} < 4 \cdot 2^{n-1} = 2^{n+1} = 2^{(n+2)-1} \]

이다. 따라서 \(F_{n+2} \le 2^{(n+2)-1}\) 이고 \(P(n+2)\) 가 참이다.

기저 두 개와 귀납 단계가 성립하므로, 강한 귀납법에 의해 모든 자연수 \(n\) 에 대해 \(F_n \le 2^{n-1}\) 이다. \(\blacksquare\)

기저가 두 개 필요한 이유. 귀납 단계가 만드는 것은 \(P(n+2)\) 이고 그 재료가 \(P(n)\) 과 \(P(n+1)\) 이다. 기저를 \(P(1)\) 하나만 두면 \(P(2)\) 를 만들 재료가 없다 — \(P(2)\) 는 \(P(0)\) 과 \(P(1)\) 을 요구하는데 \(P(0)\) 은 무대 밖이다. 보폭이 \(2\) 이므로 손으로 채워야 할 칸도 두 개다(S14주차 문제 15).

검산. \(F_5 = 5\) 이고 \(2^4 = 16\) 이므로 \(5 \le 16\) 이다. 부등식이 헐겁다는 것은 증명이 틀렸다는 뜻이 아니라, 이 상계가 성기다는 뜻이다.

문제 10

접근. 증명 평가는 C5주차의 평가 다섯 걸음으로 검사하고, 판정은 옳음\(\cdot\)틀림\(\cdot\)불완전 가운데 하나로 적는다. 답안에는 판정 뒤에 결함 줄 지목과 병명(S11주차의 어휘), 수리를 덧붙인다. 귀납 답안의 평가에서 먼저 세는 것은 §1.2의 걸음 다섯 개 중 몇 개가 실제로 있는가이고, 그 다음이 인용된 근거가 목록 안에 있는가이다.

풀이.

판정 — 틀림. 인용한 근거가 증명 대상 자신이므로 결함이 있는 줄이 특정된다 (평가 다섯 걸음의 ② 논리와 ③ 가정 사용에서 걸린다). 빠진 걸음까지 함께 보면 불완전이기도 하지만, 순환은 틀린 줄이므로 판정 낱말은 틀림으로 적는다. 이 답안은 증명이 아니다.

결함 줄. “등차수열의 합 공식에 의해 이는 참이다”라는 줄. 그리고 그 앞에 있어야 할 쪼개기 줄과 기저 확인 줄이 통째로 없다.

병명 — 가정 미소비에 의한 순환. 답안에 기저(걸음 ①)가 없고, 귀납 가정을 선언한 줄(걸음 ②)도 없으며, \(\sum_{i=1}^{n+1} i\) 를 \(\left(\sum_{i=1}^n i\right) + (n+1)\) 로 재그룹한 줄(걸음 ③)도 없다. 따라서 가정 \(P(n)\) 이 한 번도 쓰이지 않았다. 그 자리를 메운 “등차수열의 합 공식”은 지금 증명하려는 명제 자신이므로, 결론을 다른 이름으로 인용한 것이다 — 근거 목록의 ④가 되려면 그 명제가 이미 증명되어 있어야 하는데 그렇지 않다(S14주차 문제 12).

수리. 약한 귀납으로 고치려면 예제 2.1(또는 1권 31주차 예제 2.1)의 서식을, 최소 반례법으로 고치려면 예제 2.3의 서식을 따른다. 아래에 적는 것은 앞쪽 갈래다. 기저에서 \(n = 1\) 의 좌\(\cdot\)우변을 각각 계산하고, 귀납 단계에서

\[ \sum_{i=1}^{n+1} i = \left(\sum_{i=1}^{n} i\right) + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2} \]

으로 적는다. 둘째 등호가 가정 소비처이며, 이 한 줄이 있어야 답안이 순환에서 벗어난다.

복기. 귀납 답안을 채점할 때 가장 빠른 검사는 “가정에 의해”라고 적힌 줄을 찾는 것이다. 그 줄이 없으면 나머지를 읽을 필요 없이 미완성이다.

문제 11

접근. 예제 2.3과 다섯 걸음이 같고 재료만 바뀐다. 걸음 ④에서 \(\sum_{i=1}^{m-1}\) 에 더할 항은 \(i = m\) 일 때의 항, 곧 \(2m - 1\) 이다. 걸음 ③을 빠뜨리면 확인 7의 붕괴가 그대로 재연되므로 반드시 적는다.

풀이. 이 등식이 성립하지 않는 자연수가 존재한다고 가정하고, 그런 자연수 전체의 집합을 \(R\) 라 하자. \(R\) 는 공집합이 아닌 자연수 집합이므로 최소원리에 의해 최소원소 \(m\) 이 존재한다.

\(n = 1\) 일 때 좌변은 \(2 \cdot 1 - 1 = 1\) 이고 우변은 \(1^2 = 1\) 로 같으므로 \(1 \notin R\) 이고, 따라서 \(m \ge 2\) 이다. 곧 \(m - 1\) 은 자연수다.

\(m\) 이 \(R\) 의 최소원소이고 \(m - 1 < m\) 이므로 \(m - 1 \notin R\) 이다. 곧

\[ \sum_{i=1}^{m-1}(2i-1) = (m-1)^2 \]

이다. 양변에 \(i = m\) 일 때의 항 \(2m-1\) 을 더하면

\[ \sum_{i=1}^{m}(2i-1) = (m-1)^2 + (2m-1) = m^2 - 2m + 1 + 2m - 1 = m^2 \]

이므로 \(m \notin R\) 이다. 이것은 \(m \in R\) 와 충돌하므로 모순이다. 따라서 \(R\) 는 공집합이고, 모든 자연수 \(n\) 에 대해 \(\sum_{i=1}^n (2i-1) = n^2\) 이다. \(\blacksquare\)

복기. 예제 2.1과 이 증명은 같은 명제의 두 서식이다. 계산으로 보면 “\((m-1)^2 + (2m-1) = m^2\)” 과 “\(n^2 + (2n+1) = (n+1)^2\)” 은 \(m = n+1\) 을 넣으면 완전히 같은 식이다 — 서식만 다르고 산수는 하나다.

검산. \(m = 3\) 으로 두면 \((3-1)^2 + (2 \cdot 3 - 1) = 4 + 5 = 9 = 3^2\) 이다.

문제 12

접근. 기저 개수는 §1.3의 삭제 실험(확인 5)이 이미 계산했다. 귀납 단계가 쓰는 항이 \(P(n-2)\) 이므로 보폭이 \(3\) 이고, 그 보폭만큼의 칸을 손으로 채워야 한다. 답안에서 “\(n+1 \ge 11\)” 이라는 적용 조건을 밝히는 줄이 채점 대상이다.

풀이. \(P(n)\) 을 “\(n\) 은 3원 동전과 5원 동전으로 지불할 수 있다”, 곧 “\(n = 3a + 5b\) 인 음이 아닌 정수 \(a, b\) 가 존재한다”라 하자.

(기저) \(8 = 3 + 5\), \(9 = 3 \cdot 3\), \(10 = 5 \cdot 2\) 이므로 \(P(8), P(9), P(10)\) 이 모두 참이다.

(귀납 단계) \(n \ge 10\) 이라 하고, \(8 \le i \le n\) 인 모든 정수 \(i\) 에 대해 \(P(i)\) 를 가정하자. 이때 \(n + 1 \ge 11\) 이므로

\[ (n+1) - 3 = n - 2 \ge 8 \]

이고, 또한 \(n - 2 \le n\) 이므로 \(n-2\) 는 가정의 사정권 안에 있다. 가정에 의해 \(n - 2 = 3a' + 5b'\) 인 음이 아닌 정수 \(a', b'\) 이 존재하고, 따라서

\[ n + 1 = (n-2) + 3 = 3(a'+1) + 5b' \]

이다. \(a' + 1\) 과 \(b'\) 이 음이 아닌 정수이므로 \(P(n+1)\) 이 참이다.

기저 세 개와 귀납 단계가 성립하므로, 강한 귀납법에 의해 \(8\) 이상의 모든 정수는 3원\(\cdot\)5원 동전으로 지불할 수 있다. \(\blacksquare\)

기저를 세 개 잡은 근거. 귀납 단계는 \(P(n+1)\) 을 만들기 위해 \(P(n-2)\) 를 쓰므로, \(n - 2 \ge 8\) 곧 \(n + 1 \ge 11\) 인 곳에서만 작동한다. 따라서 \(8, 9, 10\) 의 세 칸은 귀납이 닿지 못하고 손으로 채워야 한다. 보폭이 \(3\) 이므로 기저도 셋이다.

검산. \(11 = 3 \cdot 2 + 5\), \(12 = 3 \cdot 4\), \(13 = 3 + 5 \cdot 2\) 로 실제로 지불된다. \(7\) 은 지불되지 않으므로 \(n_0 = 8\) 이 최선이라는 것도 확인된다.

문제 13

접근. 문제 6과 리듬이 같다. 전개해서 \(n^3 + 5n\) 덩어리를 드러내고, 남는 항이 \(6\) 의 배수임을 보인다. 남는 항 중 \(3n(n+1)\) 이 관문인데, \(n(n+1)\) 이 짝수라는 사실(§1.7의 목록)을 쓰면 \(3 \times (\text{짝수}) = 6 \times (\text{정수})\) 가 된다.

풀이. \(P(n)\) 을 “\(6 \mid (n^3 + 5n)\)” 이라 하자.

(기저) \(n = 1\) 일 때 \(1 + 5 = 6 = 6 \cdot 1\) 이므로 \(P(1)\) 이 참이다.

(귀납 단계) \(P(n)\) 을 가정하자. 곧 \(n^3 + 5n = 6m\) 인 정수 \(m\) 이 존재한다. 전개하면

\[ (n+1)^3 + 5(n+1) = n^3 + 3n^2 + 3n + 1 + 5n + 5 = (n^3 + 5n) + 3n^2 + 3n + 6 \]

이고, \(3n^2 + 3n = 3n(n+1)\) 이므로

\[ (n+1)^3 + 5(n+1) = (n^3 + 5n) + 3n(n+1) + 6 \]

이다. 여기서 \(n(n+1)\) 은 연속한 두 정수의 곱이므로 짝수이고(§1.7의 목록, 1권 1주차 문제 16), \(n(n+1) = 2k\) 인 정수 \(k\) 가 존재한다. 그러면 \(3n(n+1) = 6k\) 이다. 가정을 대입하면

\[ (n+1)^3 + 5(n+1) = 6m + 6k + 6 = 6(m + k + 1) \]

이고 \(m + k + 1\) 은 정수이므로 [근거 ②] \(P(n+1)\) 이 참이다.

기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 \(n\) 에 대해 \(6 \mid (n^3 + 5n)\) 이다. \(\blacksquare\)

복기. \(3n^2 + 3n\) 을 \(3(n^2 + n)\) 으로만 묶고 멈추면 \(3\) 의 배수까지밖에 가지 못한다. 도착점이 \(6\) 의 배수이므로 \(2\) 를 하나 더 확보해야 하고, 그 \(2\) 를 공급하는 것이 연속한 두 정수의 곱이다. 도착점의 꼴이 어디까지 묶으라고 지시한다.

검산. \(n = 2\) 에서 \(8 + 10 = 18 = 6 \cdot 3\), \(n = 3\) 에서 \(27 + 15 = 42 = 6 \cdot 7\) 이다.

문제 14

접근. 사다리를 걸 변수가 없는 부재 명제이므로 §1.6의 셋째 물음에 걸린다. 최소로 잡을 양은 \(x\) 다. \(3 \mid x^2\) 에서 \(3 \mid x\) 로 가는 줄에 유클리드 보조정리가 필요하며, 그 정리의 가정(”\(p\) 는 소수”)이 \(p = 3\) 에서 충족됨을 밝혀야 한다.

풀이. \(x^2 = 3y^2\) 인 양의 정수 \(x, y\) 가 존재한다고 가정하자.

그런 해들의 첫 성분 \(x\) 가 이루는 집합은 공집합이 아닌 양의 정수 집합이므로, 최소원리에 의해 최소원소가 존재한다. \(x\) 가 최소인 해를 \((x, y)\) 라 하자.

\(x^2 = 3y^2\) 이므로 \(3 \mid x^2\), 곧 \(3 \mid x \cdot x\) 이다. \(3\) 은 소수이므로 유클리드 보조정리에 의해 \(3 \mid x\) 이고, \(x = 3x'\) 인 양의 정수 \(x'\) 이 존재한다. 대입하면

\[ 9x'^2 = 3y^2, \qquad \text{곧} \qquad y^2 = 3x'^2 \]

이다. 같은 논증을 \(y\) 에 적용하면 \(3 \mid y^2\) 이므로 \(3 \mid y\) 이고, \(y = 3y'\) 인 양의 정수 \(y'\) 이 존재한다. 이것을 \(y^2 = 3x'^2\) 에 대입하면

\[ 9y'^2 = 3x'^2, \qquad \text{곧} \qquad x'^2 = 3y'^2 \]

이다. 따라서 \((x', y')\) 도 같은 방정식의 양의 정수 해이고, \(x' = \frac x3 < x\) 이다. 이것은 \(x\) 가 최소라는 사실과 충돌하므로 모순이다.

그러므로 \(x^2 = 3y^2\) 인 양의 정수 \(x, y\) 는 존재하지 않는다. \(\blacksquare\)

복기. 무한강하의 형태를 그대로 따랐다 — 최소인 것을 잡고, 그것에서 같은 조건을 만족하는 더 작은 것을 실제로 구성했다. 여기서 \(m - 1\) 은 한 번도 등장하지 않는다. C7주차 문제 17의 \(\sqrt2\) 판과 유일하게 다른 곳은 인용하는 소수가 \(2\) 대신 \(3\) 이라는 것뿐이고, 그 때문에 “짝수” 대신 유클리드 보조정리를 명시적으로 인용해야 한다.

따름. 이 명제는 \(\sqrt3\) 이 무리수라는 것과 같은 말이다. \(\sqrt3 = \frac xy\) 이면 양변을 제곱해 \(x^2 = 3y^2\) 이 되기 때문이다(1권 21주차 문제 7).

문제 15

접근. 예제 2.2와 무대는 같지만 결론이 더 약하다 — 분해 전체가 아니라 소인수 하나만 있으면 된다. 그래서 합성수 \(n+1 = ab\) 에서 \(a\) 한쪽에만 가정을 쓰면 되고, 마지막에 “\(a\) 의 소인수는 \(n+1\) 의 소인수이기도 하다”를 나누어떨어짐의 추이성으로 잇는다.

풀이. \(P(n)\) 을 “\(n\) 은 소수인 약수를 가진다”라 하자.

(기저) \(n = 2\) 는 소수이고 \(2 \mid 2\) 이므로 \(2\) 자신이 \(2\) 의 소수인 약수다. 따라서 \(P(2)\) 가 참이다.

(귀납 단계) \(n \ge 2\) 라 하고, \(2 \le i \le n\) 인 모든 정수 \(i\) 에 대해 \(P(i)\) 를 가정하자. \(n+1\) 을 두 경우로 나눈다.

경우 1: \(n+1\) 이 소수. 그러면 \(n+1\) 자신이 \(n+1\) 의 소수인 약수이므로 \(P(n+1)\) 이 참이다.

경우 2: \(n+1\) 이 합성수. 합성수의 정의에 의해 \(n+1 = ab\) 이면서 \(1 < a < n+1\), \(1 < b < n+1\) 인 정수 \(a, b\) 가 존재한다. \(a\) 는 정수이므로 \(2 \le a \le n\) 이고, 따라서 \(a\) 는 가정의 사정권 안에 있다. 가정에 의해 \(a\) 는 소수인 약수 \(p\) 를 가진다. 그러면 \(p \mid a\) 이고 \(a \mid (n+1)\) 이므로, 나누어떨어짐의 추이성(1권 2주차)에 의해 \(p \mid (n+1)\) 이다. 곧 \(p\) 는 \(n+1\) 의 소수인 약수이고 \(P(n+1)\) 이 참이다.

두 경우가 \(n+1\) 의 모든 가능성을 덮으므로 귀납 단계가 성립한다. 기저 단계와 귀납 단계가 모두 성립하므로, 강한 귀납법에 의해 \(2\) 이상의 모든 정수는 소수인 약수를 가진다. \(\blacksquare\)

복기. 이 명제는 S11주차 문제 15(소수가 무한히 많다)가 부품으로 쓰는 사실이다 — “\(N = p_1 \cdots p_k + 1\) 도 소인수를 가진다”는 줄이 정확히 이 명제의 인용이다. 1권 33주차 문제 6은 같은 것을 소인수분해 존재의 따름정리로 유도한다. 예제 2.2에서 곧바로 따라 나오지만, 여기서 독립적으로 증명해 두면 예제 2.2보다 약한 도구만으로도 소수의 무한성이 서는 것이 보인다.

검산. \(n + 1 = 91 = 7 \cdot 13\) 에서 \(a = 7\) 을 잡으면 \(7\) 이 소수이므로 \(p = 7\) 이고, 실제로 \(7 \mid 91\) 이다.

문제 16

접근. 기하 명제이지만 귀납이 붙을 자리는 개수뿐이다. \(P(n+1)\) 을 쪼개는 방법은 “\(n+1\) 번째 점을 하나 추가한다”이고, 그때 늘어나는 선분이 몇 개인지 세면 된다. 필요한 이전 항은 \(P(n)\) 하나이므로 약한 귀납이다.

풀이. \(P(n)\) 을 “어느 세 점도 한 직선 위에 있지 않은 \(n\) 개의 점을 서로 잇는 선분의 개수는 \(\binom n2\) 이다”라 하자 (\(n \ge 2\)).

(기저) \(n = 2\) 일 때 두 점을 잇는 선분은 하나뿐이고 \(\binom 22 = 1\) 이므로 \(P(2)\) 가 참이다.

(귀납 단계) \(n \ge 2\) 라 하고 \(P(n)\) 을 가정하자. 조건을 만족하는 \(n+1\) 개의 점이 주어졌다고 하자. 그중 하나를 \(Q\) 라 하고 나머지 \(n\) 개를 보면, 그 \(n\) 개도 어느 세 점이 한 직선 위에 있지 않으므로 가정에 의해 그들 사이의 선분은 \(\binom n2\) 개다.

새로 세어야 할 것은 \(Q\) 를 끝점으로 하는 선분이다. \(Q\) 는 나머지 \(n\) 개의 점 각각과 선분을 하나씩 이루고, 서로 다른 점끼리는 서로 다른 선분을 주므로 그 개수는 \(n\) 이다. 모든 선분은 \(Q\) 를 끝점으로 갖거나 갖지 않으므로 두 묶음은 겹치지 않고 전체를 덮는다. 따라서 선분의 총 개수는

\[ \binom n2 + n = \frac{n(n-1)}{2} + n = \frac{n(n-1) + 2n}{2} = \frac{n(n+1)}{2} = \binom{n+1}{2} \]

이다. 여기서 이항계수의 값 \(\binom n2 = \frac{n(n-1)}2\) 을 썼다(§1.7의 목록). 곧 \(P(n+1)\) 이 참이다.

기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 조건을 만족하는 \(n\) 개의 점에 대해 선분의 개수는 \(\binom n2\) 이다. \(\blacksquare\)

복기. “어느 세 점도 한 직선 위에 없다”는 조건은 선분의 개수에는 실제로 필요하지 않다. 선분은 두 끝점으로 결정되므로 서로 다른 점쌍은 언제나 서로 다른 선분을 준다 — 세 점 \(A, B, C\) 가 한 직선 위에 있어도 \(AB\), \(BC\), \(AC\) 는 끝점이 다른 세 개의 선분이다. 위 증명에서 조건이 나온 자리는 나머지 \(n\) 개의 점에도 가정을 적용하려고 조건이 부분집합에 유전됨을 확인한 한 곳뿐이고, 그 자리도 명제에 조건을 붙여 두었기 때문에 생긴 것이다. 조건이 힘을 갖는 것은 같은 세팅에서 결정되는 직선의 개수를 셀 때다 — 세 점이 한 직선 위에 있으면 세 점쌍이 같은 직선 하나를 주어 개수가 \(\binom n2\) 보다 작아진다. 조건이 어디서 소비되는지, 또는 소비되지 않는지를 짚는 것이 이 문항의 학습 목표다. C16주차에서 이 개수를 귀납 없이 세는 방법을 다룬다.

검산. \(n = 4\) 에서 \(\binom 42 = 6\) 이고, 사각형의 변 넷과 대각선 둘을 합해 실제로 여섯이다.

문제 17

접근. 쪼개기는 “가정의 양변에 \(1+x\) 를 곱한다”이다. 부등식의 양변에 곱할 때는 곱하는 수의 부호를 먼저 밝혀야 부등호 방향이 보존되므로, 조건 \(x > -1\) 이 소비되는 자리가 정확히 거기다. 곱한 뒤 남는 \(nx^2\) 을 버리는 것이 마지막 걸음이다.

풀이. \(x > -1\) 인 실수 \(x\) 를 하나 고정하고, \(P(n)\) 을 “\((1+x)^n \ge 1 + nx\)” 라 하자.

(기저) \(n = 1\) 일 때 좌변은 \((1+x)^1 = 1 + x\) 이고 우변은 \(1 + 1 \cdot x = 1 + x\) 이므로 두 값이 같고 \(P(1)\) 이 참이다.

(귀납 단계) \(P(n)\) 을 가정하자. 가정에 의해 \((1+x)^n \ge 1 + nx\) 이다. 여기서 \(x > -1\) 이므로 \(1 + x > 0\) 이다 — 이 줄이 조건 \(x > -1\) 의 소비처다. 양수를 곱하면 부등호 방향이 보존되므로, 가정의 양변에 \(1+x\) 를 곱해

\[ (1+x)^{n+1} = (1+x)^n (1+x) \ge (1 + nx)(1 + x) \]

를 얻는다. 우변을 전개하면

\[ (1+nx)(1+x) = 1 + x + nx + nx^2 = 1 + (n+1)x + nx^2 \]

이고, \(n > 0\) 이고 \(x^2 \ge 0\) 이므로 \(nx^2 \ge 0\) 이다. 따라서

\[ (1+x)^{n+1} \ge 1 + (n+1)x + nx^2 \ge 1 + (n+1)x \]

이고 \(P(n+1)\) 이 참이다.

기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 \(x > -1\) 인 모든 실수 \(x\) 와 모든 자연수 \(n\) 에 대해 \((1+x)^n \ge 1 + nx\) 이다. \(\blacksquare\)

조건의 소비처. 귀납 단계에서 “\(1 + x > 0\) 이므로 부등호 방향이 보존된다”라고 적은 줄이다. 이 조건이 없으면, 예컨대 \(x = -3\) 에서 \(1 + x = -2 < 0\) 이라 곱하는 순간 부등호가 뒤집혀 논증이 무너진다.

검산. \(x = 0.5\), \(n = 3\) 에서 좌변은 \(1.5^3 = 3.375\) 이고 우변은 \(1 + 1.5 = 2.5\) 이다. \(x = -0.5\), \(n = 3\) 에서는 좌변이 \(0.125\), 우변이 \(-0.5\) 로 역시 성립한다.

문제 18

접근. 결론이 명백히 거짓이므로(\(n = 100\) 이 반례다) 답안 어딘가가 반드시 틀렸다. 기저는 옳으니 남은 곳은 귀납 단계뿐이다. 귀납 단계는 “모든 \(n\) 에 대한” 조건문임을 떠올리고, 그 조건문이 거짓이 되는 \(n\) 을 하나 찾으면 진단이 끝난다.

풀이.

판정 — 틀림. 명제 자체가 거짓이므로 C5주차 평가 다섯 걸음의 ① 명제 진위에서 이미 걸린다 (\(n = 100\) 에서 \(100 < 100\) 이 거짓). 거짓 명제에 붙은 증명은 반드시 틀렸으므로 판정 낱말은 틀림이다.

결함 줄. “\(n < 100\) 이므로 \(n + 1 \le 100\) 이고, 따라서 성립한다”는 줄.

결함의 내용. 두 가지가 겹쳐 있다.

첫째, 도착점이 틀렸다. 보여야 할 것은 \(P(n+1)\), 곧 \(n + 1 < 100\) 인데 답안이 도착한 곳은 \(n + 1 \le 100\) 이다. 등호가 붙은 부등식은 도착점이 아니다.

둘째, 귀납 단계가 특정 \(n\) 에서 실제로 거짓이다. \(n = 99\) 를 넣어 보면 전건 “\(1, \ldots, 99\) 가 모두 \(100\) 보다 작다”는 참이고 후건 “\(100 < 100\)”은 거짓이므로, 이 \(n\) 에서 조건문이 거짓이다. 정의 8.1의 걸음 ②는 \(n_0\) 이상의 모든 \(n\) 에 대해 성립할 것을 요구하므로, 한 곳에서 끊기면 사다리가 거기서 멈춘다.

무엇이 무너졌는가. 강한 귀납이라는 이름을 붙였다고 해서 귀납 단계의 요구가 약해지지는 않는다. 가정의 폭을 넓히는 것과 귀납 단계가 모든 \(n\) 에서 성립해야 한다는 것은 별개의 조건이다. 이 답안은 앞쪽을 지키고 뒤쪽을 어겼다.

복기. 귀납 답안의 결함은 두 자리에만 있다 — 기저가 없거나(확인 2), 귀납 단계가 어떤 \(n\) 에서 끊기거나. 결론이 거짓인 답안을 만나면 이 두 곳을 순서대로 검사한다. S14주차 문제 17\(\cdot\)18이 같은 검사를 다른 소재에서 다룬다.

문제 19

접근. 두 풀이의 계산은 하나다. \((n+1)! = (n+1) \cdot n!\) 이라는 쪼개기가 (a)의 관절이고, \(m! = m \cdot (m-1)!\) 이 (b)의 관절이다. 가정을 대입한 뒤 계수 \((n+1)\) 또는 \(m\) 을 \(2\) 로 눌러 놓는 줄이 양쪽 모두에 필요하다. 논의에서는 §1.6의 첫째 물음이 어느 쪽을 가리키는지를 근거로 삼는다.

풀이 (a) — 약한 귀납. \(P(n)\) 을 “\(n! \ge 2^{n-1}\)” 이라 하자.

(기저) \(n = 1\) 일 때 \(1! = 1\) 이고 \(2^{0} = 1\) 이므로 \(P(1)\) 이 참이다.

(귀납 단계) \(P(n)\) 을 가정하자. \(n\) 이 자연수이므로 \(n + 1 \ge 2\) 이고, \(n! > 0\) 이므로

\[ (n+1)! = (n+1) \cdot n! \ge (n+1) \cdot 2^{n-1} \ge 2 \cdot 2^{n-1} = 2^{n} \]

이다. 첫 부등호가 가정 소비처이고, 둘째 부등호에서 \(n+1 \ge 2\) 를 썼다. \(2^n = 2^{(n+1)-1}\) 이므로 \(P(n+1)\) 이 참이다. 따라서 귀납의 원리에 의해 모든 자연수 \(n\) 에서 \(n! \ge 2^{n-1}\) 이다. \(\blacksquare\)

풀이 (b) — 최소 반례법. 이 부등식이 성립하지 않는 자연수가 존재한다고 가정하고, 그런 자연수 전체의 집합을 \(R\) 라 하자. 최소원리에 의해 \(R\) 에 최소원소 \(m\) 이 존재한다.

\(n = 1\) 에서 \(1! = 1 \ge 2^0 = 1\) 이므로 \(1 \notin R\) 이고, 따라서 \(m \ge 2\) 이며 \(m - 1\) 은 자연수다. 최소성에 의해 \(m - 1 \notin R\) 이므로 \((m-1)! \ge 2^{m-2}\) 이다. 그러면 \(m \ge 2\) 이고 \((m-1)! > 0\) 이므로

\[ m! = m \cdot (m-1)! \ge m \cdot 2^{m-2} \ge 2 \cdot 2^{m-2} = 2^{m-1} \]

이다. 곧 \(m \notin R\) 이고, 이것은 \(m \in R\) 와 충돌하므로 모순이다. 따라서 \(R = \varnothing\) 이고 모든 자연수 \(n\) 에서 \(n! \ge 2^{n-1}\) 이다. \(\blacksquare\)

논의 — 어느 쪽이 자연스러운가. 약한 귀납이 자연스럽다. §1.6의 첫째 물음에서 \(P(n+1)\) 을 쪼갠 결과 \((n+1)! = (n+1) \cdot n!\) 이 요구하는 이전 항은 \(P(n)\) 하나이고 그것이 직전이므로, 셋째 물음까지 갈 이유가 없다. 최소 반례법 쪽은 같은 계산을 하기 위해 귀류 개시와 최소원리 인용이라는 두 줄을 더 쓴다 — 얻는 것 없이 답안만 길어진다. 최소 반례법이 값을 하는 자리는 문제 14처럼 사다리를 걸 변수가 없는 무대다.

검산. \(n = 5\) 에서 \(5! = 120\) 이고 \(2^4 = 16\) 이다. 등호는 \(n = 1\) 과 \(n = 2\) 두 곳에서 성립하고(\(1! = 1 = 2^0\), \(2! = 2 = 2^1\)), \(n \ge 3\) 부터는 진부등식이다 (\(3! = 6 > 4 = 2^2\)). 귀납 단계의 둘째 부등호 \((n+1) \cdot 2^{n-1} \ge 2 \cdot 2^{n-1}\) 이 등호가 되는 것은 \(n + 1 = 2\), 곧 \(n = 1\) 일 때뿐이므로 등호가 두 곳에서만 나오는 것이 계산으로도 확인된다.

문제 20

접근. 서술 문항의 답안은 개념 절의 문장을 옮겨 적는 것이 아니라, 지정된 예제의 어느 줄이 그 개념의 근거인지 짚는 글이다. (a)는 예제 2.1과 2.3에서 각각 두 줄씩, (b)는 예제 2.2에서 한 줄을 지목해야 점수가 된다.

풀이. (예시 답안)

(a) 예제 2.1의 “\(n\) 을 자연수라 하고 \(P(n)\) 을 가정하자”는 줄이 조건문의 출발점을 무대에 올리는 줄이고, “\(= n^2 + (2n+1)\)” 이라 적은 줄이 그 출발점을 소비해 도착점 \(P(n+1)\) 로 가는 줄이다 — 귀납 단계 전체가 조건문 \(P(n) \Rightarrow P(n+1)\) 하나를 증명하는 일임이 이 두 줄로 확인된다(S14주차). 예제 2.3에서는 “\(1 \notin R\) 이므로 \(m \ge 2\)” 라는 줄이 예제 2.1의 기저와 같은 계산을 하고, “\(\sum_{i=1}^{m-1} i\) 에 \(m\) 을 더해 \(\frac{m(m+1)}2\) 을 얻은” 줄이 예제 2.1의 귀납 단계와 같은 계산을 한다. 두 서식은 같은 명제군을 증명하며, 같은 한 칸을 위로 타는가 아래에서 최소성을 깨뜨리는 데 쓰는가만 다르다.

(b) 예제 2.2에서 합성수 \(n+1 = ab\) 의 두 인수는 \(2\) 이상 \(n\) 이하의 어디든 될 수 있으므로, 증명이 실제로 쓰는 것은 \(P(a)\) 와 \(P(b)\) 이고 그중 어느 것도 \(P(n)\) 이라는 보장이 없다. 약한 귀납의 가정에는 \(P(n)\) 하나만 들어 있어 이 둘을 덮지 못하므로, “\(a\) 는 정수이므로 \(2 \le a \le n\) 이다”라는 줄이 뜻을 가지려면 가정이 \(P(2)\) 부터 \(P(n)\) 까지의 구간이어야 한다.

복기. 두 물음 모두 “어느 줄인가”를 묻는 문항이다. 개념 절의 요약만 적은 답안은 내용이 옳아도 점수가 되지 않는다 — 지목이 없으면 그 개념을 자신의 증명에서 찾아낼 수 있는지가 확인되지 않기 때문이다.

---

다음 주 예고 (C9주차): Chartrand 7장 — 증명 기법 리뷰와 채점자 되기, 그리고 전반부 종합 시험이다. C1~C8주차에서 세운 기법들이 “명제의 겉모양이 기법을 정한다”는 하나의 지도로 접히고, 무작위로 배치된 명제 앞에서 어느 기법을 꺼낼지를 시험한다. 이번 주의 확인 3\(\cdot\)문제 10\(\cdot\)문제 18에서 한 진단 — 걸음이 비었는가, 가정이 소비되었는가, 귀납 단계가 모든 \(n\) 에서 성립하는가 — 이 다음 주의 채점 훈련에서 그대로 항목이 된다. C1~C8주차의 백지 체크리스트를 총복습하고 원서 7장을 먼저 통독한 뒤에 온다.