# How to prove what amounts of postage can be formed with normal mathematical induction?

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.

• If you can prove anything by "strong induction", you can already prove it by "regular" induction, by just making your inductive hypothesis for "regular" induction stronger, so that it matches what you get with strong induction. Strong induction is not different that regular induction: it is just a special case of regular induction. – Carl Mummert Mar 9 '15 at 2:51

## 2 Answers

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$.

• How did you come up with theses cases? How do you know there aren't any more? – committedandroider Mar 9 '15 at 2:14
• @committedandroider I came up with them by trying a few, and I've seen very similar inductions before, so I knew where to start. There are no more cases, because either you use at least one stamp worth $11$, or no stamps worth $11$ cents (only stamps worth $4$ cents). There are not other possibilities. – Johanna Mar 9 '15 at 2:39

As an alternative to Johanna's answer, you can take four values at a time in the same induction step. If there is a valid collection of stamps for each of $\{k,k+1,k+2,k+3\}$, then there is a valid collection for $\{k+4,k+5,k+6,k+7\}$ which can be formed by adding one $4$-cent stamp to each.

• Can you explain four values at a time? I thought regular induction just used one value for the basis step. – committedandroider Mar 9 '15 at 2:12
• It's the same as doing four different inductions with base cases $30, 31, 32, 33$ using $P(x) \implies P(x+4)$ as the inductive step in each. – Dan Brumleve Mar 9 '15 at 2:15
• I am so confused. Isn't what you're doing there strong induction? I did that for part c. – committedandroider Mar 9 '15 at 2:16
• Well, it's a way of avoiding strong induction by looking at it as induction on blocks of 4 numbers instead of the numbers themselves. If one block of 4 consecutive numbers can be represented, then so can the next block. But it's just ordinary induction not strong induction because it doesn't rely on all earlier blocks being representable, only the previous one. – Dan Brumleve Mar 9 '15 at 2:24
• To do it with strong induction, if all $x$ with $30 \le x \le n$ can be represented, then we can represent $n+1$ by adding $4$ to the representation of $n-3$. – Dan Brumleve Mar 9 '15 at 2:29