1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ After some numerical experimentation, one may arrive at the basic strategy. If I can get $4$ in a row good, it's all over. The problem-setter kindly said to start at $18$. $\endgroup$ – André Nicolas Dec 15 '15 at 15:10
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Okay, but why 4 cases, why not just 1? $\endgroup$ – lucidgold Dec 15 '15 at 15:15
1
$\begingroup$

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}$
$\endgroup$
  • $\begingroup$ Okay, but I am trying to understand how to select the base-cases. I have the solution. Could you explain how you choose base-cases? $\endgroup$ – lucidgold Dec 15 '15 at 15:06
  • 1
    $\begingroup$ @lucidgold: You need $4$ base-cases for this question. The ones you've picked look fine to me. $\endgroup$ – barak manos Dec 15 '15 at 15:06
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.