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

Ifthen

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

Assume

Prove

because of

Ifthenhence

Example Prove(2)

Ifthen

Assumethen

We must prove

which we obtain from (2) by replacingbythroughout.

Hence (2) is proved.