CHAPTER **25**

**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 ...

Start Free Trial

No credit card required