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.
Best Answer
Here is how I would prove this: