So Many Chairs, No???

Let's deal with the generalized form first. Suppose we have $n$ chairs arranged in a row. Keep in mind that we can't choose two consecutive chairs. Let $P(n)$ denote the number of ways to choose two chairs as the question says, in case of $n$ chairs. We'll now divide the counting process into two sub-cases.

Firstly, we count the number of ways when we don't choose the first chair in the line. So we are left with $n-1$ more chairs and we can choose two chairs from them satisfying the question in $P(n-1)$ ways.

Lastly, we count the number of ways when we do choose the first chair. So clearly we can't choose the second chair since that would be two consecutive chairs. Hence, we are left with $n-2$ more chairs and we can choose two chairs from them satisfying the question in $P(n-2)$ ways.

In total, we have the following:

$P(n)=P(n-1)+P(n-2)$

The above recursion looks familiar, doesn't it? It's the definition of the famous Fibonacci Sequence:

$1,1,2,3,5,8,13,21,34,55,89,...$

Note that $P(1)=2=F_{3}$ and $P(2)=3=F_{4}$ . So in general, we have:

$P(n)=F_{n+2}$

Where $F_n$ is the $n$ th Fibonacci number. For a direct formula, we can use Binet's $n$ th Fibonacci term formula: $F_n=\dfrac{(1+\sqrt5)^n-(1-\sqrt5)^n}{2^n\sqrt5}$

Therefore, our desired answer is:

$P(14)=F_{16}=\fbox{987}$

The problem is asking for the number of subsets of $14$ chairs such that no two chairs in the subset are next to each other.

Let $s_n$ be the number of such subsets of $n$ chairs. Such a subset will either contain the first chair, or not.

• If the subset contains the first chair, then it can't contain the second chair. Thus there will be $s_{n-2}$ ways to construct the rest of the subset.

• If the subset does not contain the first chair, then there are $s_{n-1}$ ways to choose a subset of the remaining chairs.

Therefore, $s_n = s_{n-2} + s_{n-1}$ . Moreover, $s_0 = 1$ and $s_1 = 2$ . We immediately recognize this as the Fibonacci sequence, with $s_n = F_{n+2}$ ; in particular, $s_{14} = F_{16} = \boxed{987}$ . (Alternatively, we can use the recursion directly to compute everything up to $F_{16}$ .)