Puzzle de bombillas

Question

Existen $10$ bombillas seguidas, encendidas o apagadas. ¿Cuántas combinaciones de bombillas encendidas y apagadas podemos tener si no puede haber dos bombillas encendidas una al lado de la otra?

Parece que forma una secuencia de Fibonacci si partimos de un caso base de $1$ bulbo y trabajar hacia arriba, pero no entiendo intuitivamente por qué es así.

$$F(1) = 2\\ F(2) = 3\\ F(3) = 5$$

Dónde $F(X)$ es el número de combinaciones que podemos tener con $X$ bombillas en fila.

Gracias por cualquier ayuda.

Answer 1

Supongamos que $F(n)$ es el número de formas de hacerlo con $n$ bombillas.

Si tiene $n+1$ bombillas, entonces usted puede tener la última bombilla apagada, en cuyo caso se obtiene $F(n)$ formas de hacerlo (cualquier combinación de las primeras $n$ servirá). O puede tener la última activada, en cuyo caso necesitará una combinación de la primera $n$ en el que el último está apagado; hay $F(n-1)$ formas de hacer que . Así que en total tienes que $$F(n+1) = F(n) + F(n-1).$$ Desde $F(0)=1$ y $F(1)=2$ se obtiene la secuencia de Fibonacci "adelantada en $1$ ".