DMP 3.5: Induction and Recurrence

Reading

Epp Section 5.6 pages 325–335 and 347–348.

You will probably have met the idea of recurrence previously, now we combine it with proof by induction. The Fibonacci Numbers are well known, but you may not also have realised that compound interest is a recursive formula. An explicit formula for a recurrence relation can be proved by weak or strong induction. The video gives and introduction to recurrence and weak induction.

Video

Exercises

• Exercise Set 5.7 Questions 18, 21, and 26 (You can use the explicit formula given in the textbook answer for part (b) when solving part (c))

You can read about some famous recursive functions from the theory of computation on pages 372 and 373 of Section 5.9 in Epp.