Chapter 6

Recurrence Relations

Learning Objectives

On completing this chapter, you should be able to:

  • formulate recurrence relations to solve problems involving an unknown sequence

  • solve certain first order and second order recurrence relations

  • define the generating function of a sequence

  • solve second order recurrence relations by finding the corresponding generating functions

6.1 INTRODUCTION

Can you guess the next number in the following sequence?

 

4, 11, 18, …

 

A fairly intelligent fifth standard girl can answer this question. The child perceives that the successive terms differ by 7, and so she adds 7 to the last term given and gives the answer as 25. Mathematically speaking, the child realizes that the difference between the (n

Get Discrete Mathematics and Combinatorics now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial