Mathematical-Reasoning · Unit 13 · Video 4 · Interactive Practice

Three Basis Cases: Every n from 8 On Is a Sum of 3s and 5s

IKey Formulas

Piece of the proof	Formula
The statement $P(n)$	there exist $x, y \in \mathbb{Z}^$ with $n = 3x + 5y$ , where $\mathbb{Z}^ = \{x \in \mathbb{Z} \mid x \ge 0\}$
Basis step: three cases	$8 = 3\cdot 1 + 5\cdot 1$ , $\;9 = 3\cdot 3 + 5\cdot 0$ , $\;10 = 3\cdot 0 + 5\cdot 2$
Reach back three places	$k + 1 = 3 + (k-2)$ , and $k \ge 10 \Rightarrow k - 2 \ge 8$
Inductive step	$k - 2 = 3u + 5v \;\Rightarrow\; k + 1 = 3(1+u) + 5v$

Key Insight: The inductive step uses $P(k-2)$ , not $P(k)$ , so it needs the Second Principle; and because it reaches back three places, the basis step must check three consecutive cases. The only natural numbers that are not of the form $3x + 5y$ are $1$ , $2$ , $4$ and $7$ .

IIWhich Numbers Can Be Reached?

For each $n$ , checking every $y$ with $5y \le n$ decides exactly whether $n = 3x + 5y$ has a solution in $\mathbb{Z}^*$ .

n 7

IIIWhy Three Basis Cases?

The step from $P(k-2)$ to $P(k+1)$ jumps three places, so each basis case starts its own chain.

Steps applied 0

IVUnwinding the Step Builds x and y

Stepping back by $3$ from any $n \ge 8$ lands on $8$ , $9$ or $10$ ; each $3$ added back raises $x$ by one.

n 13

VQuiz Questions

Problem 1 · The Unreachable Numbers

Find the set of all natural numbers $n$ that cannot be written as $n = 3x + 5y$ with $x, y \in \mathbb{Z}^*$ .

✅ Correct! Below

8

only

3

5

and

6

are reached, and the proof covers every

n \ge 8

❌ Not quite.

7

is also out of reach:

y \in \{0, 1\}

would need

3x = 7

3x = 2

, and neither

7

nor

2

is a multiple of

3

❌ Not quite.

11

can be reached:

11 = 3\cdot 2 + 5\cdot 1

. Every

n \ge 8

is of the form

3x + 5y

❌ Not quite.

1

is not reached either.

x = y = 0

gives

0

, and if

x

y

is positive then

3x + 5y \ge 3

Show solution

For $n \le 7$ check each $y$ with $5y \le n$ :

$n = 1, 2$ : only $y = 0$ , and $3x = 1$ , $3x = 2$ have no solution (if $x \ge 1$ then $3x \ge 3$ ).
$n = 3 = 3\cdot 1$ , $n = 5 = 5\cdot 1$ , $n = 6 = 3\cdot 2$ : reached.
$n = 4$ : $y = 0$ forces $3x = 4$ , impossible.
$n = 7$ : $y = 0$ gives $3x = 7$ and $y = 1$ gives $3x = 2$ ; both impossible.

The proposition proved in the video shows every $n \ge 8$ is reached. So the unreachable natural numbers are exactly $\{1, 2, 4, 7\}$ .

Problem 2 · Running the Inductive Step

Given: in the inductive step with $k = 15$ , the hypothesis $P(k-2)$ supplies $13 = 3\cdot 1 + 5\cdot 2$ , so $u = 1$ and $v = 2$ . Which representation of $k + 1 = 16$ does the step produce?

✅ Correct!

k + 1 = 3 + (3u + 5v) = 3(1+u) + 5v = 3\cdot 2 + 5\cdot 2 = 16

❌ Not quite. Raising

v

by one adds

5

, not

3

3\cdot 1 + 5\cdot 3 = 18

. The extra

3

goes into the

x

-part.

❌ Not quite. Adding one

3

raises

x

by one, not by three:

3\cdot 4 + 5\cdot 2 = 22

❌ Not quite. Only

x

changes;

v

stays

2

. As written,

3\cdot 2 + 5\cdot 3 = 21

Show solution

The step writes $k + 1 = 3 + (k-2)$ and substitutes $k - 2 = 3u + 5v$ :

16 = 3 + 13 = 3 + (3\cdot 1 + 5\cdot 2) = 3(1 + 1) + 5\cdot 2 = 3\cdot 2 + 5\cdot 2.

Check: $6 + 10 = 16$ . Here $1 + u = 2$ and $v = 2$ are both in $\mathbb{Z}^*$ , so $P(16)$ is true.

Problem 3 · One Basis Case Is Not Enough

Given: a student checks only $P(8)$ and then shows that $P(k-2)$ implies $P(k+1)$ for every $k \ge 10$ . Which values of $n$ has this argument actually established?

✅ Correct! Each use of the step moves exactly three places, so from

8

alone it reaches only

11

14

17

, …

❌ Not quite. Nothing produces

P(9)

: the step gives

P(k+1)

from

P(k-2)

, and

k + 1 = 9

would need

P(6)

, which is below the starting value

8

❌ Not quite.

P(12)

would need

P(9)

, and

P(13)

would need

P(10)

; neither was proved, so

12

and

13

are missing too.

❌ Not quite. The step applies again and again:

P(11)

gives

P(14)

, which gives

P(17)

, and so on without end.

Show solution

The step proves $P(k+1)$ only from $P(k-2)$ , three places back. Starting from $P(8)$ :

P(8) \Rightarrow P(11) \Rightarrow P(14) \Rightarrow P(17) \Rightarrow \cdots

No chain ever starts at $9$ or $10$ , so $P(9), P(12), P(15), \ldots$ and $P(10), P(13), P(16), \ldots$ are never reached. What is proved is $P(n)$ for $n = 8 + 3j$ with $j \in \mathbb{Z}^*$ . That is why the basis step checks $P(8)$ , $P(9)$ and $P(10)$ .

Problem 4 · Fours and Fives

Given: $11$ is not of the form $4x + 5y$ with $x, y \in \mathbb{Z}^*$ , and we want to prove that every $n \ge 12$ is. The inductive step writes $k + 1 = 4 + (k - 3)$ . Which basis step does this proof need?

✅ Correct! The step reaches back four places, so four consecutive basis cases are needed:

12 = 4\cdot 3

13 = 4\cdot 2 + 5\cdot 1

14 = 4\cdot 1 + 5\cdot 2

15 = 5\cdot 3

❌ Not quite. Three cases matched a step of

3

. Here the step adds

4

, so nothing produces

P(15)

: it would need

P(15 - 4) = P(11)

, which is false.

❌ Not quite. From

P(12)

alone the step reaches only

16, 20, 24, \ldots

; the values

13

14

and

15

start chains of their own.

❌ Not quite.

P(16)

already follows from the step with

k = 15

16 = 4 + 12

and

P(12)

is a basis case. Checking it directly is harmless but not needed.

Show solution

The step uses $P(k-3)$ , so it needs $k - 3 \ge 12$ , that is $k \ge 15$ . The first case it produces is $P(16)$ , from $P(12)$ . The cases $P(13)$ , $P(14)$ , $P(15)$ are not produced by the step, so they are checked directly together with $P(12)$ :

12 = 4\cdot 3 + 5\cdot 0,\quad 13 = 4\cdot 2 + 5\cdot 1,\quad 14 = 4\cdot 1 + 5\cdot 2,\quad 15 = 4\cdot 0 + 5\cdot 3.

For $k \ge 15$ , if $k - 3 = 4u + 5v$ with $u, v \in \mathbb{Z}^*$ , then $k + 1 = 4(1+u) + 5v$ . The step reaches back four places, so the basis step checks four consecutive cases.

Solved: 0 / 4