## CPSC 170 Postlab 7

Use the First Principle of Mathematical Induction to prove the following:
1. n2 >= 2n+3   for   n>=3
```
Base case: n=3  32 ?>= 2*3+3
9 >= 9

Inductive step: If k2 >= 2k+3 then (k+1)2 >= 2(k+1)+3,
or k2+2k+1 >= 2k+5.

Proof: By the inductive hypothesis, k2 >= 2k+3.
Adding 2k+1 to both sides gives

k2+2k+1 >= 2k+3 + 2k+1

=>   k2+2k+1 >= 4k+4

But we're trying to show that  k2+2k+1 >= 2k+5.  This will be true
by the transitive property of >= if

4k+4 >= 2k+5

=>  2k >= 1, or k >= 1/2.  We are concerned only with k>=3, so the property holds.

```
Use the Second Principle of Mathematical Induction to prove the following:
2. Any amount of postage greater than or equal to 12 cents can be built using only 4-cent and 5-cent stamps.
```Base cases:
n=12: 12=4+4+4
n=13: 13=4+4+5
n=14: 14=4+5+5
n=15: 15=5+5+5

Inductive step: If any amount of postage r, 12<=r<=k, can be built
using only 4-cent and 5-cent stamps, then postage k+1 can be built using only
4-cent and 5-cent stamps.

Proof: Cases k=12, k=13, k=14, and k=15 were proved in the base case,
so here we can assume that k+1 >= 16.  By the inductive hypothesis, we know
that the postage for k-3 can be formed using 4-cent and 5-cent stamps since
(k+1)>=16 => (k-3)>=12.  Now take the postage for k-3 and add a 4-cent stamp;
this gives the postage for k+1.
```