Sea \(a_n\) el número de cadenas binarias de longitud \(n\) sin dos ceros seguidos. Se cumple \(a_n=a_{n-1}+a_{n-2}\) con \(a_1=2\) y \(a_2=3\). ¿Cuánto vale \(a_5\)?
\(a_3=5,\ a_4=8,\ a_5=13\). La recurrencia sale de que una cadena válida termina en 1 (resto válido de longitud \(n-1\)) o en 10 (resto válido de longitud \(n-2\)).
Una relación de recurrencia es una ecuación que expresa cada término \(a_n\) de una sucesión en función de los \(k\) anteriores; con valores iniciales, determina toda la sucesión.