This is similar to my other question Strong induction but it addresses standard mathematical induction.
Problem:
a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps.
b) Prove your answers to (a) using the principle of mathematical induction. Be sure to state explicitly your inductive hypothesis in the inductive step.
c) Prove your answers to (a) using strong induction. How does the inductive hypothesis in this proof differ from that in the inductive hypothesis for a proof using mathematical induction.
My Work
I am currently wokring on part b of the problem. For part a, with help from @BaronVT, I was able to find a sequence of four postage amounts – 30, 31, 32, 33- that can be formed using just 4 cent stamps and 11 cent stamps. From that I stated, postage amounts of 30 and more can be formed using just 4 cent stamps and 11 cent stamps.
I know for mathematical induction that I have to have a basis step and an inductive step.
My basis step was showing that 30(start) can be formed with just using 4 cent stamps and 11 cent stamps
$\quad$30 = 11(2) + 4(2)
Now the inductive step
If $k$ cents, $k$ being some integer $\ge$ 30, can be formed with just using 4 cent stamps and 11 cent stamps, then $k + 1$ cents can also be formed with just using 4 cent stamps and 11 cent stamps. My inductive hypothesis by the way is the "$k$ cents, $k$ being some integer $\ge$ 30, can be formed with just using 4 cent stamps and 11 cent stamps" portion of the statement. So now I have the algebraic expressions
$\quad$ $k$ = 11a + 4b for some integers a and b, with k $\ge$ 30
$\quad$ $k + 1$ = 11c + 4d for some integers c and d.
Where do I go from here? I tried substituting $k$ in the second equation to get
$\quad$ 11a + 4b + 1 = 11c + 4d
but that didn't get me closer to showing that $k + 1$ cents can be formed with just using 4 cent stamps and 11 cent stamps.
Best Answer
There is a special trick for induction problems like this one that can be hard to figure out if you've never seen it before. This is how it works:
Case $1$: You can form $k$ cents using at least one stamp worth $11$ cents. Solution: replace the stamp worth $11$ cents by $3$ stamps worth $4$ cents to find $k+1$.
Case $2$: You can form $k$ cents using only stamps worth $4$ cents. Since $k > 30$, there are at least $8$ of them. Replace these $8$ by $3$ stamps worth $11$ cents to form $k+1$.