# 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? – Trevor Wilson Oct 31 '13 at 6:48
• both. I basically just get completely confused when it gets split into two cases, and anything after that – FrostyStraw Oct 31 '13 at 6:50
• @TrevorWilson especially when they start talking about "replacing stamps" – FrostyStraw Oct 31 '13 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$. – Trevor Wilson Oct 31 '13 at 6:55
• My mind basically just stopped following what you were saying when I got to this: "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. Please explain what is sorta confusing about "can make 12 cents postage using three 4-cent stamps". If you had to mail a letter, and postage was 12 cents, and all you had was a lot of 4-cent stamps and a lot of 5-cent stamps, what would you do?? – bof Oct 31 '13 at 7:07

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. – Simon Baars Oct 24 '18 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? – FrostyStraw Oct 31 '13 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. – Trevor Wilson Oct 31 '13 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)$