O'Reilly logo

Discrete Mathematics and Combinatorics by T. Sengadir

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

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

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

Start Free Trial

No credit card required