# Proving with Induction

$$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$

-

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?

-
Why is showing k-2 necessary? If you show k-1 shouldn't be that enough? and do you mean K-1 not K+1? –  Aaron Nov 7 '12 at 3:39
You lost me there ~_~ –  Aaron Nov 7 '12 at 3:47
Sorry. I used the wrong numbers. You have shown that you can write $14$ as a sum of $3$s and $8$s: $$14 = 2 \cdot 3 + 1 \cdot 8.$$ This then implies that you can also write $17$ as a sum of $3$s and $8$s: $$17 = \underline{14} + 3 = \underline{2 \cdot 3 + 1 \cdot 8} + 3 = 3 \cdot 3 + 1 \cdot 8.$$ –  JavaMan Nov 7 '12 at 3:50
Yes i know that, but how do you prove this formally? –  Aaron Nov 7 '12 at 3:53
Think about it for a bit. You will use that $k+1 = (k-2) + 3$. –  JavaMan Nov 7 '12 at 3:54