Lucas numbers and fibonacci

This is a question straight from the Applied Combinatorics book.

Suppose that chairs are arranged in a circle. Let $L_n$ count the number of subsets of $n$ chairs which don't contain consecutive chairs. show that $$L_{n+1} = F_n + F_{n+2}.$$

What is meant here? Could some one explain this to me?

• Do you need a proof, or do you have difficulties to understand the statement ? Feb 26, 2015 at 10:35
• What confuses me is that the number of chairs is not given. Feb 26, 2015 at 10:37
• Proof and explanation please. I don't understand what is meant by the question. Feb 26, 2015 at 10:56

If $n$ chairs are arranged in a circle, let $a_n$ be the number of subsets of the chairs that don’t contain consecutive chairs. (I’ll call these good subsets.) Clearly $a_0=1$, $a_1=2$, $a_2=3$, and $a_3=4$, since the empty subset satisfies the condition.

Now suppose that $n\ge 4$, and number the chairs from $1$ to $n$ around the circle. Temporarily remove chair $n$; the circle of remaining chairs has $a_{n-1}$ good subsets, none of which contains both chair $1$ and chair $n-1$. Of course none of these contains chair $n$, either. Moreover, every good subset of the $n$ chairs that does not contain chair $n$ and contains at most one of chairs $1$ and $n-1$ is counted here, so there are $a_{n-1}$ such subsets.

Now we’ll count the good subsets that contain either contain chair $n$ or contain both chair $1$ and chair $n-1$. Start by removing chairs $n-1$ and $n$; the remaining circle has $a_{n-2}$ good subsets. Let $S$ be one of these good subsets. If chair $1$ is in $S$, form $S'$ by adding chair $n-1$ to $S$; if chair $1$ is not in $S$, form $S'$ by adding chair $n$ to $S$. It’s not hard to check that in each case $S'$ is a good subset of the ring of $n$ chairs, and that every such subset that contains either chair $n$ or both of chairs $1$ and $n-1$ is obtained in this way. (It’s here that we need to have $n\ge 4$: in order to form $S'$ this way when chair $1$ is in $S$, we need to know that $n-1>2$.)

This argument shows that the sequence $\langle a_n:n\in\Bbb N\rangle$ satisfies the recurrence

$$a_n=a_{n-1}+a_{n-2}\tag{0}$$

for $n\ge 4$. By inspection $a_2=3=2+1=F_3+F_1$ and $a_3=4=3+1=F_4+F_2$, so a straightforward induction shows that $$a_n=F_{n+1}+F_{n-1}\tag{1}$$ for $n\ge 2$:

\begin{align*} a_{n+1}&=a_n+a_{n-1}\\ &=\left(F_{n+1}+F_{n-1}\right)+\left(F_n+F_{n-2}\right)&\text{induction hypothesis}\\ &=\left(F_{n+1}+F_n\right)+\left(F_{n-1}+F_{n-2}\right)\\ &=F_{n+2}+F_n\;. \end{align*}

Apart from the fact that I used $a_n$ instead of $L_n$ for the number of good subsets of a ring of $n$ chairs, $(1)$ is exactly relationship that you were to prove.

Nothing in the wording of the question or the original tagging indicates that $L_n$ is supposed to be the $n$-th Lucas number: $L_n$ is explicitly defined to be the number of good subsets of a ring of $n$ chairs. (The tag was added by Martin Sleziak.) The choice of the notation $L_n$ for my $a_n$ in the problem statement was very likely motivated by the fact that $a_n$ is the $n$-th Lucas number, $L_n$, for $n>1$. This follows immediately from the fact that the sequence $\langle L_n:n\in\Bbb Z^+\rangle$ of Lucas numbers by definition satisfies the same recurrence $(0)$ as the sequence $\langle a_n:n\in\Bbb N\rangle$, with $L_1=1$ and $L_2=3=a_2$: $L_3=4=a_3$, and the recurrence then ensures that $a_n=L_n$ for all $n\ge 2$.

• Thanks for the clear explaination! Mar 1, 2015 at 11:41
• @Discreteballoons: My pleasure! Mar 1, 2015 at 11:55

The Lucas numbers are defined recursively by \begin{align*} L_1 & = 1\\ L_2 & = 3\\ L_n & = L_{n - 1} + L_{n - 2}, n \geq 3 \end{align*} The first few terms of the Lucas sequence are $\{1, 3, 4, 7, 11, 18, 29, 47, 76, 123, \ldots\}$.

The Fibonacci numbers are defined recursively by \begin{align*} F_1 & = 1\\ F_2 & = 1\\ F_n & = F_{n - 1} + F_{n - 2}, n \geq 3 \end{align*} The first few terms of the Fibonacci sequence are $\{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\}$.

We can prove the assertion that $L_{n + 1} = F_n + F_{n + 2}$ by induction on $n$. Let $P(n)$ be the statement that $L_{n + 1} = F_n + F_{n + 2}$.

If $n = 1$, then $L_2 = L_{1 + 1} = 3 = 1 + 2 = F_1 + F_3$. Thus, $P(1)$ holds.

IF $n = 2$, then $L_3 = L_{2 + 1} = 4 = 1 + 3 = F_2 + F_4$. Thus, $P(2)$ holds.

Assume $L_{m + 1} = F_m + F_{m + 2}$ for each $n \leq m$, where $m \geq 2$. Let $n = m + 1$. Then \begin{align*} L_{m + 2} & = L_{m + 1} + L_{m} && \text{by definition of the Lucas sequence}\\ & = F_{m} + F_{m + 2} + F_{m - 1} + F_{m + 1} && \text{by the induction hypothesis}\\ & = F_{m} + F_{m - 1} + F_{m + 2} + F_{m + 1}\\ & = F_{m + 1} + F_{m + 3} && \text{by definition of the Fibonacci sequence} \end{align*} so $P(m) \Rightarrow P(m + 1)$. Hence, $P(n)$ holds for each positive integer $n$.

Let $a_m$ denote the number of subsets of $m$ chairs in which no two chairs are consecutive. We will consider the first few cases, where the chairs are numbered from $1$ to $m$.

\begin{align*} & m = 1: \emptyset, \color{blue}{\{1\}}\\ & m = 2: \color{red}{\emptyset, \{1\}}, \color{blue}{\{2\}}\\ & m = 3: \color{red}{\emptyset, \{1\}, \{2\}}, \color{blue}{\{3\}}\\ & m = 4: \color{red}{\emptyset, \{1\}, \{2\}, \{3\}}, \color{blue}{\{4\}}, \color{green}{\{1, 3\}}, \color{blue}{\{2, 4\}}\\ & m = 5: \color{red}{\emptyset, \{1\}, \{2\}, \{3\}, \{4\}}, \color{blue}{\{5\}} \color{red}{\{1, 3\}}, \color{green}{\{1, 4\}}, \color{red}{\{2, 4\}}, \color{blue}{\{2, 5\}, \{3, 5\}}\\ & m = 6: \color{red}{\emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{5\}}, \color{blue}{\{6\}}, \color{red}{\{1, 3\}, \{1, 4\}}, \color{green}{\{1, 5\}}, \color{red}{\{2, 4\}, \{2, 5\}}, \color{blue}{\{2, 6\}}, \color{red}{\{3, 5\}}, \color{blue}{\{3, 6\}, \{4, 6\}}, \color{green}{\{1, 3, 5\}}, \color{blue}{\{2, 4, 6\}}\\ \end{align*}

Based on these examples, we see that \begin{align*} a_1 & = 2\\ a_2 & = 3\\ a_3 & = 4\\ a_4 & = 7\\ a_5 & = 11\\ a_6 & = 18 \end{align*} Thus, the assertion that $a_1 = L_1$ is false. However, it appears that $a_m = L_m$ if $m > 1$.

Let $m = n + 1$ for $n \geq 1$.

I have used three colors to highlight the subsets of $m = n + 1$ chairs that do not contain consecutive chairs. Subsets marked in blue contain chair $n + 1$. Subsets marked in red in row $n + 1$ are those subsets that appeared in row $n$. Subsets marked in green contain both $1$ and $n$.

Observe that the elements in blue in row $n + 1$ are formed by taking the union of elements in row $n - 1$ that do not contain $1$ with the set $\{n + 1\}$, while the elements in green are formed by taking the union of elements in row $n - 1$ that do contain $1$ with the set $\{n\}$. Hence, the total number of elements in row $n + 1$ that are either blue or green is $L_{n - 1}$. The number of elements in row $n + 1$ that are red is the number of elements in row $n$, which is $L_n$. Hence, for each $n \geq 1$, \begin{align*} L_{n + 1} & = L_n + L_{n - 1}\\ & = F_{n - 1} + F_{n + 1} + F_{n - 2} + F_n\\ & = F_{n - 1} + F_{n - 2} + F_{n + 1} + F_n\\ & = F_{n} + F_{n + 2} \end{align*} We can see that the assertion is false when $n = 0$ since the empty set in row $n + 1 = m = 1$ is not a member of one of the three types of highlighted sets.

While I did not use this observation in my proof, it appears that for $n \geq 1$ that the number of sets containing $n + 1$ in row $n + 1$ is $F_n$, while the number of sets containing $1$ and $n$ in row $n + 1$ is $F_{n - 2}$ (where we define $F_0 = F_2 - F_1 = 0$ and $F_{-1} = F_1 - F_0 = 1 - 0 = 1$).

Are you sure of the formulation of your problem? I am wondering if the good one would not be: "Suppose that $n$ chairs are arranged in a circle. Let $L_n$ count the number of subsets of $k \geq 1$ chairs which don't contain consecutive chairs, show that..."

• Please see this tutorial on how to format mathematics on this site. Feb 26, 2015 at 12:46
• I have just checked it, thank you. Feb 26, 2015 at 13:50