How do you select base-cases for this proof?

Question

Let $P(n)$ be the statement that a postage of n cents can be formed using just $4$-cent and $7$-cent stamps. Show by mathematical induction that $P(n)$ is true for $n ≥ 18$. Hint: carefully determine what the base cases are.

My question is, how do you select bases cases here? Usually I pick the smallest case, so for this problem I would choose $n = 1$? Right, I cant, then can't I just choose least acceptable value like 18? So I have only 1 case? Why do I need 4?

Solution from class instructor:

Base cases:

• $P(18)$ is true as $18 = 4 + 2 ∗ 7$
• $P(19)$ is true as $19 = 3 ∗ 4 + 7$
• $P(20)$ is true as $20 = 5 ∗ 4$
• $P(21)$ is true as $21 = 3 ∗ 7$

Induction hypothesis: $P(n)$ are true for $18 ≤ n < k$, where $k ≥ 22$.

Induction step: Consider P(k). Since $k ≥ 22$, we have $k − 4 ≥ 18$.

By the induction hypothesis, there exists positive integers $x$ and $y$ such that $k−4 = 4x+7y$ which implies that $k = 4(x+1)+7y$.

Therefore, $P(k)$ is true.

Answer 1

You select them by the fact that you can always add 4c of stampage by just adding a 4c-stamp. If you have proven it for $P_{18}$, $P_{19}$, $P_{20}$ and $P_{21}$ the rest follows as steps of four up from these.

You of course start at $P_{18}$ because the task is only to prove it for $n\ge18$.

The proof will become four chains of induction proofs one for $n=18+4j$, one for $19+4j$ and so on.

You could have done by using only one chain noticing that the recipe is to alter between two ways of adding 1c. Either you add 2 4c stamps and remove one 7c or you add 3 7c stamps and remove 5 4c. This is a bit more complex as you have to prove that you can always use one of these recipes.

Answer 2

Here is how I would prove this:

• $P_{18} = \{4,7,7\}$
• $P_{19} = \{4,4,4,7\}$
• $P_{20} = \{4,4,4,4,4\}$
• $P_{21} = \{7,7,7\}$
• $P_{n} = \{4\} \cup P_{n-4}$

Answer 3

What is clear is that if the statement is true for $n$, it will also be true for $n+4$ and $n+7$. So you need to pick a set of base cases, such that if you add 4's and 7's to the base cases in all possible ways, you'll eventually get all numbers.

Here, the solution only really uses this fact for $n + 4$. If you pick the four consecutive numbers 18, 19, 20, 21, then it is clear that all larger numbers can be obtained by adding multiples of 4 to these numbers. So this set was bound to work.