1장. 증명하는 법

고등학교 수학은 주로 '답을 구하는' 수학이었다면, 대학 수학과 논문은 '왜 그런지 보이는' 수학입니다. 증명은 이미 받아들인 사실에서 출발해 한 줄씩 이유를 대며 결론에 이르는 글입니다. 이 장에서는 증명을 읽고 쓰는 기본 틀(직접 증명, 귀류법, 귀납법, 반례)을 짧은 예로 익힙니다. 이산수학 3강에서 같은 방법을 정수 문제로 더 연습할 수 있습니다.

1.1 증명의 필요성

질문. $2 + 4 = 6$ , $10 + 8 = 18$ , $100 + 36 = 136$ . 짝수 두 개를 더하면 항상 짝수가 나오는 것 같습니다. 몇 개를 더 확인하면 “항상”이라고 말할 수 있을까요?

답은 “몇 개를 확인해도 안 됩니다”입니다. 예를 하나 봅시다. $n^2 + n + 41$ 에 $n = 0, 1, 2, \ldots, 39$ 를 넣으면 40개 모두 소수가 나옵니다. 그런데 $n = 40$ 이면 $40^2 + 40 + 41 = 41^2$ 이 되어 소수가 아닙니다. 40번 연속으로 맞아도 41번째에 틀릴 수 있습니다.

짝수는 무한히 많으므로 하나씩 확인하는 방법으로는 끝낼 수 없습니다. 모든 경우를 한 번에 다루는 논증이 필요하고, 그것이 증명(proof)입니다.

선형대수의 후반부는 거의 증명으로 이루어져 있습니다. 이 장에서는 그 증명들이 사용하는 기본 기술 다섯 가지를 익힙니다.

1.2 직접 증명

1.2.1 정의 펼치기

증명의 첫 단계는 거의 언제나 같습니다. 명제에 나오는 단어를 정의로 바꿔 쓰는 것입니다.

정의 1.1 (짝수와 홀수). 정수 $n$ 에 대해 $n = 2k$ 인 정수 $k$ 가 존재하면 $n$ 을 짝수(even), $n = 2k + 1$ 인 정수 $k$ 가 존재하면 홀수(odd)라 합니다.

모든 정수는 짝수이거나 홀수이고, 둘 다일 수는 없습니다. 이 사실은 받아들이고 씁니다.

정리 1.2. 두 짝수의 합은 짝수입니다.

아이디어. “짝수”를 정의로 바꾸면 “2 × (정수)”가 됩니다. 두 수를 더한 다음 2로 묶을 수 있는지 봅니다.

증명. $m$ , $n$ 이 짝수라 합시다. 정의에 의해 $m = 2a$ , $n = 2b$ 인 정수 $a$ , $b$ 가 있습니다. 그러면

m + n = 2a + 2b = 2(a + b)

이고 $a + b$ 는 정수이므로, $m + n$ 은 짝수입니다. $\blacksquare$

이 증명의 구조를 일반화한 것이 직접 증명(direct proof)입니다. $P \Rightarrow Q$ 를 직접 증명하려면 $P$ 를 가정하고, 정의와 이미 아는 사실을 이용해 한 단계씩 $Q$ 에 도착합니다.

증명에서 $m = 2a$ , $n = 2b$ 처럼 서로 다른 문자를 쓴 것에 주의합시다. $m = 2k$ , $n = 2k$ 로 쓰면 $m = n$ 이라고 가정한 셈이 되어, 같은 짝수 두 개를 더하는 경우만 증명한 것이 됩니다. 처음 증명을 쓸 때 가장 흔한 실수입니다.

1.2.2 나누어떨어짐

정의 1.3 (약수). 정수 $a \ne 0$ , $b$ 에 대해 $b = ak$ 인 정수 $k$ 가 존재하면 “ $a$ 가 $b$ 를 나눕니다”고 하고 $a \mid b$ 로 씁니다.

예를 들어 $3 \mid 12$ 이고 $5 \nmid 12$ 입니다. 짝수의 정의는 “ $2 \mid n$ ”으로 바꿔 쓸 수 있습니다.

예제 1.4. “ $a \mid b$ 이고 $a \mid c$ 이면 $a \mid (b + c)$ ”를 증명합시다. $b = ak$ , $c = al$ 인 정수 $k$ , $l$ 이 있으므로 $b + c = a(k + l)$ 이고, $k + l$ 은 정수입니다. $\square$

▶ 문제 1.1–1.3

1.3 대우를 이용한 증명

질문. “ $n^2$ 이 짝수이면 $n$ 도 짝수입니다.” 직접 증명하려고 $n^2 = 2k$ 에서 출발하면, $n = \sqrt{2k}$ 가 되어 더 나아가기 어렵습니다. 다른 길이 없을까요?

0장 정리 0.11에 의해 $P \Rightarrow Q$ 를 증명하는 대신 대우 $\neg Q \Rightarrow \neg P$ 를 증명해도 됩니다. 위 명제의 대우는 “ $n$ 이 짝수가 아니면 $n^2$ 도 짝수가 아닙니다”, 즉 “ $n$ 이 홀수이면 $n^2$ 도 홀수입니다”입니다. 이번에는 출발점이 $n = 2k + 1$ 로 깔끔합니다.

정리 1.5. 정수 $n$ 에 대하여 $n^2$ 이 짝수이면 $n$ 은 짝수입니다.

증명. 대우를 증명합니다. $n$ 이 홀수라 하면 $n = 2k + 1$ 인 정수 $k$ 가 있습니다.

n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1

이고 $2k^2 + 2k$ 는 정수이므로 $n^2$ 은 홀수입니다. $\blacksquare$

직관. 가정이 “정보가 적은” 형태( $n^2$ 이 짝수)이고 결론이 “다루기 쉬운” 형태( $n$ 이 짝수)라면, 뒤집어서 다루기 쉬운 쪽에서 출발하는 것이 대우 증명입니다.

▶ 문제 1.4–1.5

1.4 귀류법

질문. “ $\sqrt{2}$ 는 유리수가 아닙니다.” 무엇이 아니라는 명제는 출발점이 없습니다. 어디서부터 시작해야 할까요?

귀류법(proof by contradiction)은 증명하려는 명제가 거짓이라고 가정하고, 그 가정에서 모순(참이면서 거짓인 것, 예를 들어 “ $a$ 는 짝수이고 동시에 홀수입니다”)을 이끌어 내는 방법입니다. 모순이 나왔다면 가정이 틀린 것이므로, 원래 명제가 참입니다.

정리 1.6. $\sqrt{2}$ 는 무리수입니다.

증명. $\sqrt{2}$ 가 유리수라고 가정합시다. 그러면 $\sqrt{2} = \frac{p}{q}$ 인 정수 $p$ , $q$ ( $q \ne 0$ )가 있고, 약분을 끝까지 해서 $p$ 와 $q$ 가 둘 다 짝수인 경우는 없다고 할 수 있습니다.

양변을 제곱하면 $2 = \frac{p^2}{q^2}$ , 즉 $p^2 = 2q^2$ 입니다. 따라서 $p^2$ 은 짝수이고, 정리 1.5에 의해 $p$ 도 짝수입니다. $p = 2r$ 로 쓰면 $4r^2 = 2q^2$ , 즉 $q^2 = 2r^2$ 이므로 같은 이유로 $q$ 도 짝수입니다.

$p$ 와 $q$ 가 둘 다 짝수가 되었으므로, 약분을 끝냈다는 가정과 모순입니다. 따라서 $\sqrt{2}$ 는 유리수가 아닙니다. $\blacksquare$

이 증명이 정리 1.5를 사용했다는 점을 봅시다. 수학은 증명된 정리를 쌓아서 다음 정리를 증명합니다. 선형대수에서도 앞 장의 정리를 계속 가져다 쓰므로, 정리를 외우기보다 무엇을 가정하고 무엇을 결론 내리는지를 정확히 기억해 두는 것이 중요합니다.

정리 1.7 (유클리드). 소수는 무한히 많습니다.

증명. 소수가 유한하다고 가정하고, 그 전부를 $p_1, p_2, \ldots, p_n$ 이라 합시다. $N = p_1p_2\cdots p_n + 1$ 을 생각합니다. $N > 1$ 이므로 $N$ 은 어떤 소수로 나누어떨어지고, 그 소수는 목록 안의 어떤 $p_i$ 입니다. 그런데 $p_i \mid p_1\cdots p_n$ 이고 $p_i \mid N$ 이므로 $p_i \mid \big(N - p_1\cdots p_n\big) = 1$ 입니다. 1을 나누는 소수는 없으므로 모순입니다. $\blacksquare$

▶ 문제 1.6–1.7

1.5 수학적 귀납법

질문. $1 + 2 + \cdots + n = \frac{n(n + 1)}{2}$ 이 모든 자연수 $n$ 에 대해 성립함을 어떻게 보일까요?

도미노를 떠올립시다. 첫 번째 것이 넘어지고, 어떤 것이 넘어지면 다음 것도 넘어진다면, 모두 넘어집니다.

정리 1.8 (수학적 귀납법). 자연수 $n$ 에 대한 명제 $P(n)$ 이 다음 두 조건을 만족하면, 모든 자연수 $n$ 에 대해 $P(n)$ 은 참입니다.

(기초 단계) $P(1)$ 이 참입니다.
(귀납 단계) 모든 $k \in \mathbb{N}$ 에 대해 $P(k) \Rightarrow P(k + 1)$ 이 참입니다.

이것은 자연수의 성질로 받아들입니다. 귀납 단계에서 하는 일은 “ $P(k)$ 가 참이라고 가정하고 $P(k + 1)$ 을 보이는 것”입니다. 이 가정을 귀납 가정(induction hypothesis)이라 합니다. $P(k)$ 가 참이라는 것 자체를 보이는 게 아니라, “ $P(k)$ 이면 $P(k + 1)$ ”이라는 연결을 보이는 것입니다.

정리 1.9. 모든 $n \in \mathbb{N}$ 에 대하여 $\displaystyle\sum_{k=1}^n k = \frac{n(n + 1)}{2}$ 입니다.

증명. $P(n)$ 을 위 등식이라 합시다.

기초 단계. $n = 1$ 이면 좌변은 1, 우변은 $\frac{1 \cdot 2}{2} = 1$ 입니다.

귀납 단계. $P(k)$ 가 참이라고 가정합시다. 즉 $\sum_{i=1}^k i = \frac{k(k + 1)}{2}$ 입니다. 그러면

\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k + 1) = \frac{k(k + 1)}{2} + (k + 1) = \frac{(k + 1)(k + 2)}{2}

이고, 이것은 정확히 $P(k + 1)$ 입니다. 두 번째 등호에서 귀납 가정을 썼습니다. $\blacksquare$

귀납 단계의 핵심은 “ $P(k + 1)$ 의 좌변 안에서 $P(k)$ 의 좌변을 찾아내는 것”입니다. 위 증명에서는 1부터 $k + 1$ 까지의 합을 “1부터 $k$ 까지의 합 + 마지막 항”으로 쪼갰습니다. 대부분의 귀납 증명이 이런 쪼개기로 시작합니다.

▶ 문제 1.8–1.10

1.6 집합이 같음을 보이기, 반례

1.6.1 두 방향의 포함

0장 정의 0.5에 의해 $A = B$ 를 증명하려면 $A \subseteq B$ 와 $B \subseteq A$ 를 각각 보이면 됩니다. $A \subseteq B$ 를 보이는 표준적인 문장은 “ $x \in A$ 라 합시다”로 시작해서 “따라서 $x \in B$ 다”로 끝납니다.

정리 1.10. 집합 $A$ , $B$ , $C$ 에 대하여 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ 입니다.

증명. ( $\subseteq$ ) $x \in A \cap (B \cup C)$ 라 합시다. 그러면 $x \in A$ 이고, $x \in B$ 또는 $x \in C$ 입니다. $x \in B$ 이면 $x \in A \cap B$ 이고, $x \in C$ 이면 $x \in A \cap C$ 입니다. 어느 경우든 $x \in (A \cap B) \cup (A \cap C)$ 입니다.

( $\supseteq$ ) $x \in (A \cap B) \cup (A \cap C)$ 라 합시다. $x \in A \cap B$ 이면 $x \in A$ 이고 $x \in B \subseteq B \cup C$ 입니다. $x \in A \cap C$ 인 경우도 같습니다. 어느 경우든 $x \in A \cap (B \cup C)$ 입니다. $\blacksquare$

이 증명에서 “ $x \in B$ 또는 $x \in C$ ”를 두 경우로 나누어 처리했습니다. 이를 경우 나누기(proof by cases)라 합니다. “또는”이 가정에 나오면 대개 경우를 나눕니다.

1.6.2 반례로 반증하기

$\forall x,\ P(x)$ 가 거짓임을 보이려면 무엇을 해야 할까요? 0장 정리 0.13에 의해 그 부정은 $\exists x,\ \neg P(x)$ 입니다. 즉 $P(x)$ 가 성립하지 않는 $x$ 를 하나만 찾으면 됩니다. 이런 $x$ 를 반례(counterexample)라 합니다.

예제 1.11. “모든 실수 $x$ 에 대해 $x^2 \ge x$ 다”는 거짓입니다. 반례: $x = \frac{1}{2}$ 이면 $x^2 = \frac{1}{4} < \frac{1}{2}$ 입니다.

증명과 반증의 비대칭을 기억합시다. “모든”을 증명하려면 일반적인 논증이 필요하지만, “모든”을 반증하는 데는 예 하나면 충분합니다.

▶ 문제 1.11–1.13

1.7 증명을 쓰는 습관

다음은 증명 문제를 풀 때 매번 점검할 목록입니다.

가정과 결론을 분리해서 적습니다. “가정: ⋯. 보일 것: ⋯.” 무엇을 보여야 하는지가 흐릿하면 증명도 흐릿해집니다.
정의를 펼칩니다. 결론에 나오는 단어(짝수, 부분집합, 단사, span, 일차독립, …)를 정의로 바꿔 쓰면, 보여야 할 식이 구체적으로 보입니다.
새 문자는 새 대상에만. 서로 다른 대상에 같은 문자를 쓰지 않습니다(1.2절의 $m = 2a$ , $n = 2b$ ).
$\forall$ 를 보이려면 “임의의”로 시작합니다. “임의의 $x \in A$ 를 잡읍시다”라고 쓴 뒤로는 $x$ 에 대해 아무것도 더 가정하지 않습니다.
$\exists$ 를 보이려면 만들어 보입니다. 존재한다고 말만 하지 말고, 구체적인 대상을 제시하고 조건을 만족함을 확인합니다.
각 줄의 근거를 댈 수 있어야 합니다. 정의인가, 앞의 정리인가, 가정인가, 계산인가.
끝을 표시합니다. 증명이 끝나면 ■나 □를 붙입니다.

직관. 좋은 증명은 읽는 사람이 한 줄도 건너뛰지 않고 따라올 수 있는 글입니다. 처음에는 자세하게, 지루할 만큼 자세하게 씁시다. 어떤 단계를 생략해도 되는지는 경험이 쌓이면서 알게 됩니다.

▶ 문제 1.14

쓰이는 곳. 논문의 '정리(Theorem)', '보조정리(Lemma)', '증명(Proof)' 부분은 이 장의 방법으로 쓰여 있습니다. 증명을 끝까지 따라가지 않더라도, 가정이 무엇이고 결론이 무엇인지 구분할 수 있으면 논문의 주장을 정확히 읽을 수 있습니다.

이 장의 요약

예를 여러 개 확인하는 것은 증명이 아닙니다.
직접 증명: 가정에서 출발해 정의와 정리로 결론에 도착합니다. 첫 단계는 정의를 펼치는 것입니다.
대우: $P \Rightarrow Q$ 대신 $\neg Q \Rightarrow \neg P$ 를 보입니다. 결론 쪽이 다루기 쉬울 때 씁니다.
귀류법: 결론의 부정을 가정하고 모순을 이끕니다. “~가 아닙니다” 형태의 명제에 자주 씁니다.
귀납법: $P(1)$ 과 “ $P(k) \Rightarrow P(k + 1)$ ”을 보입니다.
집합의 같음은 두 방향의 포함으로, “모든”의 반증은 반례 하나로 보입니다.

문제

이 장의 증명 문제는 1.7절의 점검 목록을 옆에 두고 풉니다. 특히 “가정: ⋯ / 보일 것: ⋯”을 먼저 적고 시작합니다.

1.1 [증명]

두 홀수의 합은 짝수임을 증명합니다.

풀이

$m = 2a + 1$ , $n = 2b + 1$ 로 둡니다(서로 다른 문자!). $m + n = 2a + 2b + 2 = 2(a + b + 1)$ 입니다.

1.2 [증명]

짝수와 임의의 정수의 곱은 짝수임을 증명합니다.

풀이

$m = 2a$ , $n$ 은 정수입니다. $mn = 2(an)$ 이고 $an$ 은 정수입니다.

1.3 [증명]

정수 $a$ , $b$ , $c$ ( $a, b \ne 0$ )에 대하여 $a \mid b$ 이고 $b \mid c$ 이면 $a \mid c$ 임을 증명합니다.

풀이

$b = ak$ , $c = bl$ ( $k, l \in \mathbb{Z}$ )입니다. $c = (ak)l = a(kl)$ 입니다.

1.4 [증명]

정수 $n$ 에 대하여 $n^2$ 이 홀수이면 $n$ 도 홀수임을 증명합니다.

풀이

대우: $n$ 이 짝수이면 $n^2$ 이 짝수입니다. $n = 2k$ 이면 $n^2 = 2(2k^2)$ 입니다.

1.5 [증명]

정수 $x$ 에 대하여 $x^2 - 6x + 5$ 가 짝수이면 $x$ 는 홀수임을 증명합니다.

풀이

대우: $x$ 가 짝수이면 $x^2 - 6x + 5$ 는 홀수입니다. $x = 2k$ 이면 $x^2 - 6x + 5 = 4k^2 - 12k + 5 = 2(2k^2 - 6k + 2) + 1$ 입니다.

1.6 [증명]

$\sqrt{3}$ 이 무리수임을 증명합니다. 필요하면 먼저 다음 보조정리를 증명하고 씁니다.

보조정리. 정수 $n$ 에 대하여 $3 \mid n^2$ 이면 $3 \mid n$ 입니다.

풀이

보조정리를 대우로 보입니다. $3 \nmid n$ 이면 $n = 3k + 1$ 또는 $n = 3k + 2$ 입니다.

(3k + 1)^2 = 3(3k^2 + 2k) + 1, \qquad (3k + 2)^2 = 3(3k^2 + 4k + 1) + 1

이므로 어느 경우든 $n^2$ 을 3으로 나눈 나머지는 1이고 $3 \nmid n^2$ 입니다.

본 증명(귀류법): $\sqrt{3} = \frac{p}{q}$ 이고 $p$ , $q$ 가 둘 다 3의 배수인 경우는 없도록 약분했다고 합시다. $p^2 = 3q^2$ 이므로 $3 \mid p^2$ , 보조정리로 $3 \mid p$ 입니다. $p = 3r$ 이면 $9r^2 = 3q^2$ , $q^2 = 3r^2$ 이므로 $3 \mid q$ 입니다. 모순입니다.

1.7 [증명]

가장 작은 양의 유리수는 존재하지 않음을 증명합니다.

풀이

귀류법. 가장 작은 양의 유리수 $r$ 이 있다고 합시다. $\frac{r}{2}$ 도 양의 유리수이고 $\frac{r}{2} < r$ 이므로 모순입니다.

1.8 [증명]

모든 $n \in \mathbb{N}$ 에 대하여 $\displaystyle\sum_{k=1}^n k^2 = \frac{n(n + 1)(2n + 1)}{6}$ 임을 증명합니다.

풀이

기초: $n = 1$ 이면 $1 = \frac{1 \cdot 2 \cdot 3}{6}$ 입니다. 귀납: $P(k)$ 를 가정하면

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

입니다. 마지막 식이 $P(k + 1)$ 의 우변( $n = k + 1$ 을 대입한 것)과 같은지 확인합니다.

1.9 [증명]

모든 $n \in \mathbb{N}$ 에 대하여 $2^n \ge n + 1$ 임을 증명합니다.

풀이

기초: $2^1 = 2 \ge 2$ 입니다. 귀납: $2^{k+1} = 2 \cdot 2^k \ge 2(k + 1) = 2k + 2 \ge k + 2$ 입니다. 마지막 부등식은 $k \ge 0$ 에서 성립합니다.

1.10 [증명]

모든 $n \in \mathbb{N}$ 에 대하여 $3 \mid (4^n - 1)$ 임을 증명합니다.

풀이

기초: $4 - 1 = 3$ 입니다. 귀납: $4^k - 1 = 3m$ 이라 하면 $4^{k+1} - 1 = 4 \cdot 4^k - 1 = 4(4^k - 1) + 3 = 3(4m + 1)$ 입니다.

1.11 [증명]

집합 $A$ , $B$ , $C$ 에 대하여 $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ 임을 증명합니다.

풀이

( $\subseteq$ ) $x \in A$ 이면 $x \in A \cup B$ 이고 $x \in A \cup C$ 입니다. $x \in B \cap C$ 이면 $x \in B \subseteq A \cup B$ 이고 $x \in C \subseteq A \cup C$ 입니다.

( $\supseteq$ ) $x \in (A \cup B) \cap (A \cup C)$ 라 합시다. $x \in A$ 이면 끝입니다. $x \notin A$ 이면 $x \in A \cup B$ 에서 $x \in B$ , $x \in A \cup C$ 에서 $x \in C$ 이므로 $x \in B \cap C$ 입니다.

( $\supseteq$ 에서 “ $x \in A$ 인 경우 / 아닌 경우”로 나눈 것이 요령입니다.)

1.12 [계산]

다음 명제는 모두 거짓입니다. 각각 반례를 하나씩 듭니다.

(a) 모든 실수 $x$ , $y$ 에 대하여 $(x + y)^2 = x^2 + y^2$ . (b) 모든 자연수 $n$ 에 대하여 $2^n > n^2$ . (c) 정수 $a \ne 0$ , $b$ , $c$ 에 대하여 $a \mid bc$ 이면 $a \mid b$ 또는 $a \mid c$ .

풀이

(a) $x = y = 1$ : $(1 + 1)^2 = 4 \ne 2 = 1^2 + 1^2$ 입니다. (b) $n = 2$ : $2^2 = 4$ , $2^2 = 4$ 이므로 $4 > 4$ 는 거짓입니다( $n = 3, 4$ 도 반례). (c) $a = 4$ , $b = c = 2$ : $4 \mid 4$ 이지만 $4 \nmid 2$ 입니다.

1.13 [증명]

집합 $A$ , $B$ 에 대하여 $A \subseteq B$ 인 것과 $A \cap B = A$ 인 것이 동치임을 증명합니다.

풀이

( $\Rightarrow$ ) $A \cap B \subseteq A$ 는 항상 성립합니다(문제 0.4). $x \in A$ 이면 가정 $A \subseteq B$ 에서 $x \in B$ 이므로 $x \in A \cap B$ 입니다. 따라서 $A \subseteq A \cap B$ 입니다.

( $\Leftarrow$ ) $x \in A$ 이면 $x \in A \cap B$ 이므로 $x \in B$ 입니다.

1.14 [도전]

다음 “증명”에는 오류가 있습니다. 어느 줄이 왜 틀렸는지 정확히 지적합니다.

주장. 모든 $n \in \mathbb{N}$ 에 대하여, 말 $n$ 마리를 모으면 모두 같은 색입니다.

증명. $n$ 에 대한 귀납법을 씁니다. $n = 1$ 이면 말이 한 마리이므로 모두 같은 색입니다. 말 $k$ 마리는 항상 같은 색이라고 가정하고, 말 $k + 1$ 마리 $h_1, \ldots, h_{k+1}$ 을 생각합시다. $h_1, \ldots, h_k$ 는 $k$ 마리이므로 귀납 가정에 의해 모두 같은 색입니다. $h_2, \ldots, h_{k+1}$ 도 $k$ 마리이므로 모두 같은 색입니다. 두 무리는 $h_2, \ldots, h_k$ 를 공유하므로, $k + 1$ 마리 모두 같은 색입니다.

풀이

마지막 문장 “두 무리는 $h_2, \ldots, h_k$ 를 공유합니다”가 $k = 1$ 일 때 틀렸습니다. $k = 1$ 이면 두 무리는 $\{h_1\}$ 과 $\{h_2\}$ 이고 공유하는 말이 없습니다. 따라서 $P(1) \Rightarrow P(2)$ 가 증명되지 않았습니다. 귀납 단계는 모든 $k \ge 1$ 에 대해 성립해야 하므로, 사슬의 첫 고리가 끊어지면 전체 논증이 무너집니다. 다른 $k \ge 2$ 에서는 논증이 맞다는 점도 눈여겨봅시다.

문제 15 · 확인 문제

본문 1.1절의 식 $n^2 + n + 41$ 이 소수가 아닌 가장 작은 $n \ge 0$ 은?

정답

풀이

$n = 0, 1, \ldots, 39$ 에서는 모두 소수이고, $n = 40$ 이면 $40^2 + 40 + 41 = 41^2$ 입니다.

문제 16 · 확인 문제

정리 1.9로 $1 + 2 + \cdots + 100$ 을 구합니다.

정답

풀이

$\frac{100 \cdot 101}{2} = 5050$ 입니다.

문제 17 · 확인 문제

“정수 $n$ 에 대하여 $n^2$ 이 홀수이면 $n$ 도 홀수입니다”의 대우는?

$n$ 이 홀수이면 $n^2$ 도 홀수입니다.
$n$ 이 짝수이면 $n^2$ 도 짝수입니다.
$n^2$ 이 짝수이면 $n$ 도 짝수입니다.
$n$ 이 홀수이면 $n^2$ 은 짝수입니다.

정답

풀이

$P$ : “ $n^2$ 이 홀수”, $Q$ : “ $n$ 이 홀수”입니다. 대우 $\neg Q \Rightarrow \neg P$ 는 “ $n$ 이 홀수가 아니면(짝수이면) $n^2$ 도 홀수가 아닙니다(짝수입니다)”입니다. 1번은 역입니다.