0
$\begingroup$

$14 = 3+3+8,\\ 15 = 3+3+3+3+3\\ 16 = 8+8$

For every $n \in \mathbb{Z}^+$ where $n \ge 14$,

$S(n): n$ can be written as sum of 3's and/or 8's

$n_0 = 14, n_1 = 16$

Then, $S(14),S(15),S(16)$ is my base case

But i'm stuck at the next step

The textbook shows

(Inductive Hypothesis for when $k \ge 16$)

$S(14),S(15),\dots,S(k-2),S(k-1)$, and $S(k)$ for some $k \in \mathbb{Z}^+$

Where and why and how is $S(k-2)$ there? and why $k \ge 16$? Shouldn't it be $k > 16$

1 Answers 1

1

Strong hint:

You have shown $S(14), S(15)$, and $S(16)$ are true. The inductive step is the following:

Suppose that $S(k)$ is true for all values $14 \leq n \leq k$. Show that this implies that $S(k+1)$ is true.

We can take $k \geq 17$ as this has already been verified for $14 \leq k < 17$. Suppose that we want to write $k+1$ as a sum of $3$s and $8$s. We are assuming (via the inductive hypothesis), that we can already write $k - 2$ as a sum of $3$s of $8$s (as $k-2 \leq k$), say $k-2 = 3x + 8y$. How can we then write $k+1$ as a sum of $3$s and $8$s?

  • 0
    You're welcome for the help, and I don't find it helpful in any situation to thin$k$ of oneself as stupid. You struggled with a problem, and you seem to get it now. This is how learning goes.2012-11-07