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

## Solutions of Recurrence Relations

##### D.1 INTRODUCTION

A recurrence relation for a sequence is an equation that defines the present term by previous terms.

Example: an = an − 1 + an − 2

The initial conditions specify the terms before the recurrence relation takes effect.

Example: a1 = 2; a2 = 3

Many counting problems can be modelled by recurrence relations.

Example 1

How many bit strings of length n have no “00”? All strings begin with a 1 or a 0. There are total 2n strings of length n. Out of these, we accept the following strings:

1. Starts with a 1; remaining n − 1; bits can be any string with no 00.
2. Starts with a 0 and 2nd bit is a 1; remaining n − 2 bits can be any string with no 00.
3. 2 strings of length 1 and 3 strings of length 2 without ...

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