Proof by Induction

The simplest proofs by induction have two steps. This is maybe best illustrated with an example.

Suppose we wanted to prove that(1) for allW e sayis the proposition thatand we can write this as

The first step, writtenoris the statement thatoris true.

We can takeas the statementiewhich is true.

Now we assume thatare all true. If we can prove thatis true then we will have proved thatis true for allsince we can take any value for includinghence provingorhence provingetc.

To proveis true, we first write down

We work with the left hand side:

Now use


We have provedsois proved and we have proved (1).

This is the general procedure:

Showor P(1) then assumeand useto prove

Example: Prove

is true since both sides equal 3



because of


Example Prove(2)



We must prove

which we obtain from (2) by replacingbythroughout.

Hence (2) is proved.

You have no rights to post comments