# 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 $P(n)$ is the propositional function:
$n = 3p + 5q$, where $n, p, q \in \mathbb{N}_0$ (i.e. non-negative integers)
Then we need to show that $P(n) \Rightarrow P(n+1)$ and $P(n+2)$. $P(n+3)$ is self-evident since we may replace $p$ by $(p+1)$; hence we will then have shown that $P(n)\Rightarrow P(n+i)$ for all $i \ge 1$.

So $P(n) \Rightarrow$
$n+1 = 3p+5q+1$
$=3p+6 +5q-5$

$= 3(p+2) + 5(q-1)$

$\Rightarrow P(n+1)$, provided $q \ge 1$
and:
$n+2 = 3p + 5q+2$
$= 3(p-1) + 5(q+1)$
$\Rightarrow P(n+2)$, provided $p \ge 1$
Hence, provided $p \ge 1$ and $q \ge 1,\; P(n) \Rightarrow P(n+1)$ and $P(n+2)$.

Now $P(8)$ states:
$8 = 3p+5q$
which is true when $p = 1$ and $q = 1$, and thus the conditions on $p$ and $q$ are satisfied for $n = 8$. Hence, by Induction, $P(n)$ is true for all $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 $1$ to both sides of the equation.

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

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