# Thread: Proof using mathematical induction

1. ## Proof using mathematical induction

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.

2. 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.
If n is the total cents, it can be written as
n = 5*x + 3*y
If you replace x and y by (x+1) and (y+1), then
n' = 5*(x+1) + 3*(y+1) = 5x + 3y + 5 + 3 = n + 8.

3. 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$.

4. i don't get how n+1=3q+5p+1
i don't get where the one comes from on the right side

5. Hello kullgirl418
Originally Posted by kullgirl418
i don't get how n+1=3q+5p+1
i don't get where the one comes from on the right side
Sorry, I don't really understand where the problem is. I've simply added $\displaystyle 1$ to both sides of the equation.

If
$\displaystyle n = 3p + 5q$
then
$\displaystyle n+1 = 3p+5q+1$
The reason I've added $\displaystyle 1$ to both sides is that I wanted to set up an expression that would enable me to show that $\displaystyle P(n) \Rightarrow P(n+1)$; in other words, to show that if we can express the sum $\displaystyle n$ cents using $\displaystyle 3$'s and $\displaystyle 5$'s then we can express $\displaystyle (n+1)$ using $\displaystyle 3$'s and $\displaystyle 5$'s.

This, after all, is what induction is all about.