There are $10$ lightbulbs in a row, on or off. How many combinations of on and off lightbulbs can we have if no two turned on bulbs can be next to each other?
It seems like it forms a Fibonacci sequence if we start from a base case of $1$ bulb and work up, but I don't understand intuitively why this is the case.
$$F(1) = 2\\ F(2) = 3\\ F(3) = 5$$
Where $F(X)$ is the number of combinations we can have with $X$ light bulbs in a row.
Thanks for any help.
Suppose $F(n)$ is the number of ways of doing it with $n$ bulbs.
If you have $n+1$ bulbs, then you can have the last bulb off, in which case you get $F(n)$ ways of doing it (any combination of the first $n$ will do). Or you can have the last one on, in which case you need a combination of the first $n$ in which the last one is off; there are $F(n-1)$ ways of doing that. So in total you have that $$F(n+1) = F(n) + F(n-1).$$ Since $F(0)=1$ and $F(1)=2$, you get the Fibonacci sequence "moved up by $1$".