number of combination in which no two red balls are adjacent.

Question

given x spaces(you can fit 1 ball in 1 space) and unlimited number of identical red and white balls, find the total number of combinations in which no two red balls are adjacent to each other.

i tried this theory like lets says i have 5 spaces then i fill in the white balls like this

_W_W_ and W_W_W

then in the rest of the spaces i fill in either red or white balls but unfortunately values like RWWRW get left out, so my that theory is wrong. does any one have any idea how to solve this.

i know the number of values your are suppose to get if it helps.

for 3 spaces-->5

for 4 spaces-->8

for 5 spaces-->13

for 6 spaces-->21

Answer 1

Congratulations on the experimentation! That is always a good beginning. The question is an old standard, indeed, because of the connection with Fibonacci numbers, a golden oldie. Call an arrangement of balls good if there are never two red balls in a row.

Let $f(n)$ be the number of good arrangements of $n$ balls. How many good arrangements of $n$ balls end in a white? Clearly there is exactly one such good arrangement for every good arrangement of $n-1$ balls. For from every good arrangement of $n-1$ balls, we can get a good arrangement of $n$ balls ending in white by appending a white. And from every good arrangement of $n$ balls ending in white, we can get a good arrangement of $n-1$ balls by removing the last white. So the number of good arrangements of $n$ balls that end in a white is $f(n-1)$.

How many good arrangements of $n$ balls end in a red? The previous ball must be white. And by the preceding paragraph, there are just as many good arrangements of $n-1$ balls that end in white as there are good arrangements of $n-2$ balls (of course, we need $n-2\ge 0$). Since every good arrangement of $n$ balls either ends in a white or a red, we conclude that $f$ satisfies the recurrence $$f(n)=f(n-1)+f(n-2).$$ The initial conditions are $f(0)=1$ and $f(1)=2$. We get essentially the Fibonacci sequence, with slightly modified indexing. If (as in the Wikipedia article linked to) we use $F_0=0$, $F_1=1$ for the Fibonacci sequence, then $f(n)=F_{n+2}$.