# Use induction: prove any postal charge of $\geq$ 12 cents can be formed by 4 and 5-cent stamps

I'm reading from my book about mathematical induction, and there is an example that says "Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps"

let P(n) be the statement that postage of n cents can be formed using 4-cent and 5-cent stamps.

and it begins proving it using mathematical induction.

it gives the Basis Step: Postage of 12 cents can be formed using three 4-cent stamps. This is sorta confusing but I think I understand it, so I continue reading.

Inductive Step: The inductive hypothesis is the statement that P(K) is true. That is, under this hypothesis, postage of k cents can be formed using 4-cent or 5-cent stamps. To complete the inductive step, we need to show that when we assume P(k) is true, then P(k+1) is also true where k>=12. That is, we need to show that if we can form postage of k cents, then we can form postage of k+1 cents. So, assume the inductive hypothesis is true; that is assume that we can form postage of k cents using 4-cent and 5-cent stamps.

So far, so good. Then..

*We consider two cases, when at least one 4-cent stamp has been used and where no 4-cent stamps have been used. First, suppose that at least one 4-cent stamp was used to form postage of k cents. Then we can replace this stamp with a 5-cent stamp to form postage of k+1 cents. *

Here is where my mind basically just...stops following what is going on. Why are we considering those two cases? I mean..I guess I know that either at least one 4 cent stamp was used to form postage, or that no 4 cent stamps have been used, but couldn't this have been worded as "there are two cases, one where at least one 5 cent stamp was used and one where it wasn't"? Is that the same thing? Does it matter? And then it says to replace this stamp..and that's where I just lose it. Replace what? What are we replacing? Why are we replacing anything? What in the world are they talking about?

confusion continues: But if no 4-cent stamps were used, we can form postage of k cents using only 5 cent stamps. Moreover, because k>= 12, we needed at least three 5 cent stamps to form postage of k cents. So we can replace three 5 cent stamps with four 4 cent stamps to form postage of k+1 cents. This completes the inductive step

I know this is all written very clearly in English, but I just...I keep re-reading it over and over again and I'm not understanding anything, I'm not understanding what exactly my goal is, I'm not understanding how anything is being proven. I wish I could find a better way to express my question but I'm really just completely lost. soo..help plz? This is so different from other examples of mathematical induction that I've seen, and I think it has to do with the "4cent and 5 cent stamps" that just seems to add another dimension to the problem that complicates it to the point where I simply cannot follow along. Sorry if this question was too long

• Are confused about (1) how did the author come up with the idea to split into those two cases, or (2) once we split into those two cases, how does the induction work? Oct 31, 2013 at 6:48
• both. I basically just get completely confused when it gets split into two cases, and anything after that Oct 31, 2013 at 6:50
• @TrevorWilson especially when they start talking about "replacing stamps" Oct 31, 2013 at 6:51
• For the inductive step, you assume that there is a set of stamps (call it $S$) adding up to $k$, and you want to prove that there is a set of stamps (call it $S'$) adding up to $k+1$. You could try to build $S'$ from scratch, but it's easier to use the inductive hypothesis by taking $S$ and just "modifying" it a bit to get $S'$. In other words, $S'$ is defined in terms of how it differs from $S$. Oct 31, 2013 at 6:55
• @FrostyStraw FYI, your problem is a special case of using $2$ values of the "Frobenius coin problem", such as in the $n=2$ section of Wikipedia's "Coin problem" article. As shown there, with $a_1 = 4$ and $a_2 = 5$, the largest value which cannot be represented is $a_1 a_2 - a _1 - a_2 = 4 \times 5 - 4 - 5 = 11$, so any postal charge of $12$ cents or higher can be formed using just $4$ and $5$ cent stamps. However, they don't prove the result there using induction, so it's not quite the same as what you're doing. Sep 13, 2019 at 16:51

## 3 Answers

Perhaps there is a better, more "mathematical" way to phrase this problem, which might make the argument more transparent :

Show that, for any $n \geq 12$, there exist numbers $k, l \in \mathbb{N}\cup\{0\}$ such that $$n = 4k + 5l$$

Step 1 : If $n =12$, we take $k=3, l = 0$

Step 2 : If we can write $$n = 4k + 5l$$ we want to write $$n+1 = 4k'+ 5l'$$ for some $k', l' \in \mathbb{N}\cup \{0\}$

Case 1 : $k \geq 1$, then $n = 4k + 5l$, and so $$n+1 = 4k+1 +5l = 4(k-1) + 5 + 5l = 4(k-1) + 5(l+1)$$ so we take $k'= k-1$ (which lies in $\mathbb{N}\cup\{0\}$ since $k\geq 1$) and $l'=l+1$

Case 2 : $k=0$, then $n = 5l$, and hence $$n+1 = 1+5l$$ Now $n\geq 12$ means that $l\geq 3$, and hence $$n+1 = 1+15+5(l-3) = 16+5(l-3)$$ so we take $k'=4$ and $l'=(l-3)$ (which lies in $\mathbb{N}\cup\{0\}$ since $l\geq 3$)

• Why is it 4k+1+5l instead of 4(k+1)+5l? I do not fully understand this step. Oct 24, 2018 at 8:05

It might help to write the proof in more mathematical terms. We want to prove that for every natural number $k \ge 12$ there are natural numbers $a$ and $b$ with $4a + 5b = k$.

The base case $k=12$ holds with $a = 3$ and $b=0$.

For the inductive step, suppose that $k \ge 12$ and there are natural numbers $a$ and $b$ with $4a+5b = k$. We want to find $a'$ and $b'$ with $4a' + 5b' = k+1$.

If $a \ge 1$ then $a' = a-1$ and $b' = b+1$ works: $$4(a-1)+5(b+1) = 4a-4+5b+5 = (4a+5b) + (5-4) = k+1.$$

If $a =0$ then because $4a+5b = k \ge 12$ we must have $b \ge 3$, so $a' = a+4$ and $b' = b-3$ works: $$4(a+4)+5(b-3) = 4a+16+5b-15 = (4a+5b) + (16-15) = k+1.$$

In either case we have found natural numbers $a'$ and $b'$ with $4a' + 5b' = k+1$, as desired.

• I get kinda confused when you start using a' and b'. What do you mean by that? Oct 31, 2013 at 7:26
• @user98852 To complete the inductive step, we want to show that $k+1$ is 4 times something plus 5 times something. I used $a'$ and $b'$ as names for those two somethings. Oct 31, 2013 at 7:33

Another proof:

$i) 12=4(3); ii)13=5(1)+2(4); iii)14=5(2)+4(1); iv)15=5(3)$

Now any other number can be obtained by adding a multiple of 4 to any of these, depending on their remainder when dividing by $4$:

If $n=4k$ , clearly done

If $n=4k+1$ , add enough $4's$ to 13 ; $4k+1-13=4k-12=4(k-3)$,

If $n=4k+2$ add enough $4's$ to 14; $4k+2-14=4=4k-12=4(k-3)$

If $n=4k+3$ add enough $4's$ to 15 ; $4k+3-15=4k-12=4(k-3)$