I'm new to Math Induction, I don't know how it goes from $ + 1 = 3 + 5 + 1$ into $5 = 5 − 5 + 5.$
I'm trying to prove that:
Any whole number of at least 8 cents can be obtained using coins of 3 and 5 cents
Assume: There is a number $$ for which there are $$ and $$ such that $ = 3 + 5$
Here's my working:
$ = 3 + 5$
Therefore $ + 1 = 3 + 5 + 1$
$5 = 5 − 5 + 5$
$5 = 5 − 1 + 5$
$ + 1 = 3 + 5 + 1$
$ + 1 = 3 + 5( − 1) + 5 + 1$
$ + 1 = 3 + 5( − 1) + 6$
$ + 1 = 3( + 2) + 5( − 1)$
$ + = ' + '$
On
$3*2 - 5*1 = 1$ and $2*5 - 3*3 = 1$.
So if $k = 3a + 5b$ we can get $k+1 = 3(a+2) + 5(b-1)$. But that assumes $b > 0$. What if $b = 0$?
Well then you can do $k + 1 = 3(a-3) + 5(b+2)$. That that assumes $a > 2$. What if $a \le 2$?
Well, you go back to square one and do $k+1 = 3(a+2) + 5(b-1)$.
... in short .....
If $a \le 2$ you do $k+1 = 3(a-3) + 5(b+2)$.
If $b = 0$ you do $k + 1 = 3(a+2) + 5(b-1)$.
If $a > 2$ and $b> 0$ then you do either one, it doesn't matter which.
But what if $b = 0$ and $a \le 2$?
Well that means $k = 3a + 5b \le 6< 8$. That's below our base case. We don't have to worry about it.
====== alternative ====
Don't do induction to show $k+1$ is possible. Do induction to show $k + 3$ is possible.
Base cases(plural)
$k = 8; k = 5*1+3*1$
$k = 9; k = 5*0 + 3*3$
$k = 10; k = 5*2 + 3*0$.
If $k = 5a + 3b$ then $k + 3 = 5a + 3(b+1)$
That takes care of every case at least $8$.
$11$ is possible because $8$ is possible. $12$ is possible because $9$ is possible. $13$ is possible because $10$ is possible. $14$ is possible because $11$ is possible. And so on.
A good induction argument should take you from the base case, as far as you want to go. You need to establish the $8$ cent case, and a rule that shows how to take the $k$ cent case, and produce the $k + 1$ cent case. You're missing the $8$ cent case, but that's easy: $8 = 3 + 5$.
Now, we should be able to apply your rule to make every subsequent number of cents. Your rule is as follows: $$3x + 5y = k \implies 3(x + 2) + 5(y - 1) = k + 1.$$ Here's a question: how do you know that $y - 1$ is a sensible number of $5$ cent coins? To see this, let's try applying this rule to $8$ cents in order to get $9$ cents: $$3 \cdot 1 + 5 \cdot 1 = 8 \implies 3 \cdot 3 + 5 \cdot 0 = 9.$$ This works out; three $3$ cent coins will make $9$ cents. Let's try again for $10$ cents: $$3 \cdot 3 + 5 \cdot 0 = 9 \implies 5 \cdot 3 + 5 \cdot (-1) = 10.$$ Arithmetically, this is true, but we can't allow negative one $5$ cent coins! The combination $3(x + 1) + 5(y - 1)$ works fine, provided $y > 0$, but you haven't dealt with the $y = 0$ case!
Instead, I suggest first manually dealing with $8$, $9$, and $10$ individually. We have ways of making $8$ and $9$ already. To make $10$, we have $$10 = 0 \cdot 3 + 2 \cdot 5.$$ Then, $11$ is just $8$ with $3$ more cents added on, $12$ is $9$ with another $3$ cents, similarly $13$ is $10$ with another $3$ cents, etc. If you do strong induction, and assume for a given $n$, $k$ cents can be made for every $8 \le k < n$, then appeal to $n - 3$, and add another $3$ cent coin to the collection. That is, provided $n > 10$; otherwise refer back to the three explicit cases.