Hello kullgirl418 Originally Posted by
kullgirl418 Show that any postage greater than or equal to 8 cents can be made from 3 cent and/or 5 cent stamps using mathematical induction. For example, 31 cents can be made by using five 5 cent stamps and two 3 cent stamps for a total of 25+6=31 cents.
Suppose that $\displaystyle P(n)$ is the propositional function:$\displaystyle n = 3p + 5q$, where $\displaystyle n, p, q \in \mathbb{N}_0$ (i.e. non-negative integers)
Then we need to show that $\displaystyle P(n) \Rightarrow P(n+1)$ and $\displaystyle P(n+2)$. $\displaystyle P(n+3)$ is self-evident since we may replace $\displaystyle p$ by $\displaystyle (p+1)$; hence we will then have shown that $\displaystyle P(n)\Rightarrow P(n+i)$ for all $\displaystyle i \ge 1$.
So $\displaystyle P(n) \Rightarrow$ $\displaystyle n+1 = 3p+5q+1$$\displaystyle =3p+6 +5q-5$
$\displaystyle = 3(p+2) + 5(q-1)$
$\displaystyle \Rightarrow P(n+1)$, provided $\displaystyle q \ge 1$ and:$\displaystyle n+2 = 3p + 5q+2$$\displaystyle = 3(p-1) + 5(q+1)$
$\displaystyle \Rightarrow P(n+2)$, provided $\displaystyle p \ge 1$ Hence, provided $\displaystyle p \ge 1$ and $\displaystyle q \ge 1,\; P(n) \Rightarrow P(n+1)$ and $\displaystyle P(n+2)$.
Now $\displaystyle P(8)$ states: $\displaystyle 8 = 3p+5q$
which is true when $\displaystyle p = 1$ and $\displaystyle q = 1$, and thus the conditions on $\displaystyle p$ and $\displaystyle q$ are satisfied for $\displaystyle n = 8$. Hence, by Induction, $\displaystyle P(n)$ is true for all $\displaystyle n \ge 8$.
Grandad