0
$\begingroup$

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?

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

3 Answers 3

1
$\begingroup$

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$.

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

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$).

$\endgroup$
0
$\begingroup$

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..."

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.