# Proof by Induction

Proof by Induction

An induction proof of a formula consists of three parts.

a) Show the formula is true for.

b) Assume the formula is true for.

c) Using b), show the formula is true for.

a) Show the formula is true for

n=1

b) Assume the formula is true for

n

c) Using b), show the formula is true for

n+1

For c), the usual strategy for a summation is to manipulate into the form .

a+a+a+…+a=f(n)

1

2

3

n

f(n)+a

n+1

f(n+1)

Induction is a method for checking a result; discovering the result may be hard.