수학적 귀납법 연습문제 — Sundstrom, Mathematical Reasoning · 4.2절

Sundstrom, Mathematical Reasoning · 4.2절영어 원문

Consider the following question:

For which natural numbers

n

do there exist nonnegative integers

x

and

y

such that

n = 3x + 5y

?

To help answer this question, we will let $\mathbb{Z}^* = \left\{ {x \in \mathbb{Z} \mid x \geq 0} \right\}$ , and let $P \left( n \right)$ be There exist $x,y \in \mathbb{Z}^*$ such that $n = 3x + 5y$ . Notice that $P(1)$ is false since if both $x$ and $y$ are zero, then $3x + 5y = 0$ and if either $x > 0$ or $y > 0$ , then $3x + 5y \geq 3$ . Also notice that $P(6)$ is true since $6 = 3 \cdot 2 + 5 \cdot 0$ and $P(8)$ is true since $8 = 3 \cdot 1 + 5 \cdot 1$ .

Explain why $P(9)$ , $P(10)$ , $P(11)$ , and $P(12)$ are true.

정답·풀이 보기 (영어 원문)

Construct the following table and use it to answer the first two questions. The table shows that $P\left( 3 \right)$ , $P\left( 5 \right)$ , and $P\left( 6 \right)$ are true. We can also see that $P(2)$ , $P(4)$ , and $P(7)$ are false. It also appears that if $n \in \mathbb{N}$ and $n \geq 8$ , then $P\left( n \right)$ is true.

| $x$ | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 0 | 1 | 1 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | $y$ | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 3 | 3 | | $3x + 5y$ | 0 | 3 | 6 | 9 | 12 | 5 | 8 | 11 | 10 | 13 | 18 |

한 번 더 — 비슷한 문제Sundstrom, Mathematical Reasoning · 4.2절 · 8번영어 원문

Can each natural number greater than or equal to 4 be written as the sum of at least two natural numbers, each of which is a 2 or a 3? Justify your conclusion. For example, $7 = 2 + 2 + 3$ , and $17 = 2 + 2 + 2 + 2 + 3 + 3 + 3$ .

다 풀었으면 정답 확인

Let $P( n )$ be, “The natural number $n$ can be written as a sum of natural numbers, each of which is a 2 or a 3.” Verify that $P( 4 ), P( 5 ), P( 6 )$ , and $P( 7 )$ are true. To use the Second Principle of Mathematical Induction, assume that $k \in \mathbb{N}, k \geq 5$ and that $P( 4 ), P( 5 ), \ldots , P( k )$ are true. Then notice that

$k + 1 = ( {k - 1} ) + 2$

. Since $k - 1 \geq 4$ , we have assumed that $P( {k - 1} )$ is true. This means that $(k-1)$ can be written as a sum of natural numbers, each of which is a 2 or a 3. Since $k + 1 = (k - 1) + 2$ , we can conclude that $(k+1)$ can be written as a sum of natural numbers, each of which is a 2 or a 3. This completes the proof of the inductive step.

이 문제로 이어서 풀기

# 수학적 귀납법계산자동 분류