## Appendix C

## Solutions of Recurrence Relations

#### C.1 Introduction

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

Example: *a _{n}* =

*a*

_{n}_{– 1}+

*a*

_{n}_{– 2}

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

Example: *a*_{1} = 2; *a*_{2} = 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 2^{n} strings of length *n*. Out of these, we accept the following strings:

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

Get *Design and analysis of Algorithms, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.