## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required