[Math] We can use an unlimited supply of 4-cent and 7-cent postage stamps to make (exactly) any amount of postage that is 18 cents or more.

induction

$P(n)$: postage of exactly n cents can be made using only 4 cents and 7 cents

Basis ($n=18$)

$1 \cdot 4 + 2\cdot7 = 18$, thus $P(18)$ holds

Induction step:

Let $i$ be an arbitrary number such that $i \geq18$ and suppose that $k, L \in \mathbb N$ such that $i = 4\cdot k + 7 \cdot L$ k representing the # of 4 stamps and L representing the # of 7 stamp

I was told I have to prove 2 cases with them being $L > 0$ and $L =0$. I don't get how they got the two cases. I'm only aware that I have to prove that any number $i \geq 18$ can be achieved with 4 stamps and 7 stamps.

Could someone explain this proof?

Best Answer

Remember that in general, the structure of the inductive step would be like this:

Let $i\in\mathbb N$ and $i \geq 18,$ and suppose $P(i)$ is true. We wish to show that $P(i+1)$ is true.

Since $P(i),$ ...
...
... and therefore $P(i+1).$ This proves the inductive step.

Your problem is to fill in the "..." parts with a valid mathematical argument.

Your instructor's hint about cases $L > 0$ and $L=0$ gives you a little more detail about how the inductive step can be structured. The hint says to try this:

Let $i\in\mathbb N$ and $i \geq 18,$ and suppose $P(i)$ is true. We wish to show that $P(i+1)$ is true.

Since $P(i),$ there exist $k, L \in \mathbb N$ such that $i = 4\cdot k + 7 \cdot L.$ Consider the following two cases, which cover all possible values of $L$:

Case 1: Suppose $L>0.$ Then ...
...
... and therefore $P(i+1).$

Case 2: Suppose $L=0.$ Then ...
...
... and therefore $P(i+1).$

Hence in either case we have shown $P(i+1).$ This proves the inductive step.

You still have to fill in the "..." parts. With two separate arguments. But the only way to learn how to do this is to start trying.

By the way, the details of your question seem to imply that your book and/or instructor consider the least element of $\mathbb N$ to be $0.$ In some other contexts, people consider the least element of $\mathbb N$ to be $1$ (and therefore $0 \not\in\mathbb N$). I think what you have written so far is probably perfectly OK, but in general, when dealing with $\mathbb N$ make sure you know which way it has been defined.

Related Question