Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.