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: