I am trying to solve the following problem:
There are a bunch of boys and girls (assuming an unlimited supply of each). Let $ f(N) $ be the number of ways we can seat them into N seats such that none of the boys sit together. Find a recurrence relation for $f(N)$
One example is when $ N = 3 $, we have $ GGG $, $ GBG $, $ GGB $, $ BGB $ and $ BGG $. Hence $ f(3) = 5 $
Normally, in this type of problem, we will are given a finite set of boys and girls so we can simply apply the permutation and combination formulas to get our answer. But in this case, I can't see how we can use recurrence for this.
The only step that I could think of is:
\begin{align} &\text{Number of ways to arrange boys and girls into N seats (conditionally)} \\ &=2^N - \text{Number of ways boys can seat together} \end{align}
In this case, the number of boys is in the range $ [ 2,N ] $. So I am not sure how to handle this. I have spent hours trying to think of a solution but to no avail. Could someone please advise me?
Lets assume, that $a_n$ = number of ways to sit $n$ persons, where on the last position is girl, $b_n$ - number of ways, where on the last position is boy.
It is clear, that $a_1=b_1=1$
If on the last position there is girl, we can set next to her boy or girl. If on the last position there is boy, we can set next to him only another girl. In other words - girl can be placed next to the boy or another girl, and boy can be placed only next to the girl. We have then:
$\left\{\array{a_{n+1}=a_n+b_n\\b_{n+1}=a_n}\right.$
Of course $f(n)=a_n+b_n$
We can write it also in another way:
$a_{n+2}=a_{n+1}+b_{n+1}=a_{n+1}+a_n$
Which gives us the Fibonacci sequence (starting form 1,1 instead of 0,1).
We have also $f(n+2) = a_{n+2}+b_{n+2} = a_{n+2}+a_{n+1} = a_{n+3}$
So for $a_0=1$, $a_1=1$, our number of ways to place $n$ people is equal to $(n+2)$'th element of Fibonacci sequence.