Let \(a_n\) be the number of binary strings of length \(n\) with no two consecutive zeros. It satisfies \(a_n=a_{n-1}+a_{n-2}\) with \(a_1=2\) and \(a_2=3\). What is \(a_5\)?
\(a_3=5,\ a_4=8,\ a_5=13\). The recurrence comes from a valid string ending in 1 (valid rest of length \(n-1\)) or in 10 (valid rest of length \(n-2\)).
A recurrence relation is an equation that expresses each term \(a_n\) of a sequence in terms of the previous \(k\) terms; with initial values, it determines the whole sequence.