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

n=1

n

n+1

For c), the usual strategy for a summation +++…+=f(n) is to manipulate into the form .

a

1

a

2

a

3

a

n

f(n)+

a

n+1

f(n+1)

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