6
$\begingroup$

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.

1 Answers 1

11

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$".

  • 0
    Moved up by 2, though, if you want to be able to write down reasonable divisibility relations of Fibonacci numbers.2012-05-22