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.