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