Problema...

¿Cuántas cadenas binarias de longitud n existen que no tengan dos ceros consecutivos?
Por ejemplo:
Con n = 1 tenemos el conjunto {0,1} es decir, hay dos cadenas que cumplen esa condición
Con n = 2 tenemos el conjunto {01,10,11}, tenemos tres elementos
Con n = 3 tenemos el conjunto {010, 011, 101, 110, 111}

En general podemos partir el conjunto en dos,

sea

cadenas(n)={Conjunto de todas las cadenas binarias de longitud n tal que no tienen dos ceros consecutivos}

Definamos

a*cadenas(x)={ a*x | a es 0 ó 1 y x está en cadenas(x)},

Por ejemplo:

1*cadenas(2) = {101, 110, 111}
0*cadenas(1) = {01, 00}

Entonces partamos el problema en dos casos. El conjunto de cadenas binarias de longitud n tal que no tienen dos ceros consecutivos es igual a, las cadenas que empiezan con 0 concatenadas con las cadenas de longitud n-1 binarias que no tienen dos ceros consecutivos, más las cadenas que empiezan con 10 concatenadas con las cadenas de longitud n-2 binarias que no tienen dos ceros consecutivos.

Podemos escribirlo así:

cadenas(n) = 1*cadenas(n-1) + 01*cadenas(n-2)

¿Te parece conocido? Es la sucesión de Fibonacci,

f(n) = f(n-1) + f(n-2)
f(1) = 1
f(0) = 1

sólo que las condiciones iniciales cambian,

c(n) = c(n-1) + c(n-2)
c(1) = 2
c(0) = 1