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:
We have provedsois proved and we have proved (1).
This is the general procedure:
Showor P(1) then assumeand useto prove
is true since both sides equal 3
We must prove
which we obtain from (2) by replacingbythroughout.
Hence (2) is proved.