Proof using mathematical induction

**kullgirl418** · March 18th 2010, 06:23 PM

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.

**sa-ri-ga-ma** · March 18th 2010, 08:05 PM

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.

**Grandad** · March 19th 2010, 01:15 AM

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

Grandad

**kullgirl418** · March 21st 2010, 08:41 PM

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

**Grandad** · March 22nd 2010, 01:36 AM

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.

Grandad

Thread: Proof using mathematical induction

LinkBack

Thread Tools

Display

Proof using mathematical induction

Similar Math Help Forum Discussions

Proof by Mathematical Induction

Mathematical Induction Proof

mathematical induction proof

Proof by mathematical Induction

Proof Of Mathematical Induction

Search Tags