Proof by Induction

general term in summation

k

2

k

k-1

2

1

k(k+1)

Prove: 1 + 2 + 3 + … + n =

1

2

n(n + 1)

1) The base case is true: 1 =

1

2

1(1 + 1)

2) Assume the formula for n.

3) Write the sum for n+1, use 2) in the first step, and manipulate:

1 + 2 + 3 + … + n + (n+1) =

1

2

n(n + 1) + (n+1) =

(n+1)(

1

2

n + 1) =

1

2

(n+1)(n + 2) =

1

2

(n+1)((n + 1) + 1).

The last expression is the right-hand side of the formula for n+1,

so by induction, the formula is true for all n≥1.

An induction proof of a formula consists of three parts.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

a

1

+

a

2

+

a

3

+…+

a

n

=f(n)

is to manipulate

f(n)+

a

n+1

into the form

f(n+1)

.

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