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
    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?2012-11-07
  • 0
    You lost me there ~_~2012-11-07
  • 0
    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.$$2012-11-07
  • 0
    Yes i know that, but how do you prove this formally?2012-11-07
  • 0
    Think about it for a bit. You will use that $k+1 = (k-2) + 3$.2012-11-07
  • 0
    So we create the S(k-2) in our hypothesis to prove that k+1 = (k-2)+3 and this is always true because (k-2) is true, and whatever it is, +3 will also make it true which in turn is the same thing as (k+1) therefore S(k+1) is true. Now how do I write this out as a legitimate solution? If I just wrote down what I just said, would that be a legitimate proof?2012-11-07
  • 0
    @aaron: The majority of your "legitimate solution" is already in my answer above. Essentially, you want to show that if $S(k)$ is true for all $14 \leq n \leq k$, then $S(k+1)$ is true. To this end, suppose $S(n)$ is true for all values $14 \leq n \leq k$. In particular $S(k-2)$ is true. This implies... (I'll let you fill in the rest of the details)2012-11-07
  • 0
    Thank you for your help, and sorry for being stupid2012-11-07
  • 0
    You're welcome for the help, and I don't find it helpful in any situation to think of oneself as stupid. You struggled with a problem, and you seem to get it now. This is how learning goes.2012-11-07