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!

  • $\begingroup$ You don't need to use induction here. After your observation the statement is proven. $\endgroup$ – question Oct 16 '16 at 21:15
  • $\begingroup$ 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. $\endgroup$ – 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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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