More sophisticated induction techniques
Simplicity is the ultimate sophistication.
Leonardo da Vinci
In this chapter we investigate more sophisticated versions of induction. There are three variants we shall be most interested in.
(i) We use a different initial case. Rather than show that A(1) is true we show, for instance, A(7) or A(15) is true. Thus A(n) is true for all n ≥ 7 or all n ≥ 15 respectively.
(ii) We change the inductive step to ‘A(k − 1) and A(k) imply A(k + 1).’ This requires us to have as initial case that A(1) and ...