Solutions of Recurrence Relations
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.
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:
- 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 ...