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.