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
Best Answer
Perhaps there is a better, more "mathematical" way to phrase this problem, which might make the argument more transparent :
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$)