# What would be the induction hypothesis in my proof?

I proved that any amount greater than 24 cents can be obtained by a combination of 5 cents and 7 cents using strong induction. First I proved the following base cases:

$$24=2(5)+2(7)$$ $$25=5(5)$$ $$26=5+3(7)$$ $$27=4(5)+7$$ $$28=4(7)$$

Then for my induction step, I used the fact that every number n greater than 24 can be written in one of the following forms: $$24+5k$$ $$25+5k$$ $$26+5k$$ $$27+5k$$ $$28+5k$$

I then substitued 24, 25, 26, 27 and 28 by the terms in the base cases to show that in each case, n could be written as a combination of 5 cents and 7 cents.

However, I used the base cases directly in the inductive step, I did not use any induction hypothesis. Is an induction hypothesis really needed in this case, or can we do without one? Thanks!

• You don't need to use induction here. After your observation the statement is proven. – question Oct 16 '16 at 21:15
• If you have proved your claim $24+5k$ etc. your proof is done. The "induction" would be to assume $24+5k$ to be true for $k$, and then substitute for $n = k+1$. Because your claim is true for all $n \in \mathbb N$, the proof is done. – Eemil Wallin Oct 16 '16 at 21:16

You used induction implicitly, when asserting that any number greater than $24$ can be written as $x+5k$, with $24\le x\le 28$.
Instead your (strong) induction hypothesis should be: let $n>28$ and assume every integer $k$ with $24\le k<n$ can be obtained with $5$ and $7$ cents.
Then $24\le n-5<n$ so, $n-5=5a+7b$ and therefore $n=5(a+1)+7b$.