Given infinite number of red and blue balls, how many ways are there to arrange n balls such that no two red balls are adjacent?
Answers
ongratulations 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≥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 F0=0, F1=1 for the Fibonacci sequence, then f(n)=Fn+2.