1. ## Induction proof

Exercise 2.9. Prove that if n ≥ 12 then n can be written as a sum of 4’s and 5’s. For example, 23 = 5 + 5 + 5 + 4 + 4 = 3 · 5 + 2 · 4. [Hint. In this case it will help to do the cases n = 12, 13, 14, and 15 separately. Then use induction to handle n ≥ 16.]

It's not too hard to provide cases for n = 12, 13, 14, 15, but the second bit is hard:
If n = 5a + 4b, then n + 1 = 5c + 4d?
Any tips on how to get started? I think I'm introducing too many variables, but I duno really :/

2. Originally Posted by DivideBy0
Exercise 2.9. Prove that if n ≥ 12 then n can be written as a sum of 4’s and 5’s. For example, 23 = 5 + 5 + 5 + 4 + 4 = 3 · 5 + 2 · 4. [Hint. In this case it will help to do the cases n = 12, 13, 14, and 15 separately. Then use induction to handle n ≥ 16.]

It's not too hard to provide cases for n = 12, 13, 14, 15, but the second bit is hard:
If n = 5a + 4b, then n + 1 = 5c + 4d?
Any tips on how to get started? I think I'm introducing too many variables, but I duno really :/
Well if n>=16, then you have one of the following cases:

1. 3x5 + some more 4's and 5's
2. 2x5 + 1x4 + other 4's
3. 1x5 + 1x4's + more 4's
4. 0x5 + 4x4's + more 4's

In the first case trade in 3x5's for 4x4's to reach n+1.
In the second case trade in 1x5 and 1x4 for 2x5's to reach n=1
In third case trade in 1x5 and 1x4 for 2x5's to reach n+1
In fourth case trade in 1x4 for 1x5 to reach n+1

RonL

3. If a and b are relatively prime then eventually ever number can be expressed as their sum.

4. Thanks, so I have to do induction on the three cases separately?

5. Originally Posted by DivideBy0
Thanks, so I have to do induction on the three cases separately?
No what you do is assume that the proposition is true for some k, and
observe that for this k one of the four cases applies (you don't know which),
but whichever it is the explanation in the earlier post means the proposition
is true for k+1.

RonL