## CPSC 220 Fall 2007 HW 3: Review of Proof by Induction

1. Use mathematical induction to show that Sum(i=3,n)2i = (n+3)(n-2)    n>=3.
```Base case: n=____.  Left side:________________  Right side:__________________

Inductive step:

If _____________________________________  then ____________________________________.
(property for k)                         (property for k+1)

=> ____________________________________
(simplify property for k+1)

Proof:
By the inductive hypothesis, ________________________________________________.

To make the left side of this look like what we are trying to show, add

___________ to both sides.

This gives ___________________________________________________________________.

Simplifying, we get __________________________________________________________

______________________________________________________________________________.
```

2. Use mathematical induction to show that Sum(i=0,n)2i = 2n+1-1    n>=1
```Base case:

Inductive step:

Proof:
By the inductive hypothesis, _________________________________________________.

(... You finish!)

```