
Problem 6. Find the number of non-empty sets of $S_{n}=\{1,2, \ldots, n\}$ such that there are no two consecutive numbers in one and the same set.


Solution: Denote the required number by $f_{n}$. It is easy to see that $f_{1}=1, f_{2}=2, f_{3}=4$.

Divide the subsets of $S_{n}$ having no two consecutive numbers into two groups-those that do not contain the element $n$ and those that do. Obviously the number of subsets in the first group is $f_{n-1}$.

Let $T$ be a set of the second group. Therefore either $T=\{n\}$ or $T=\left\{a_{1}, \ldots, a_{k-1}, n\right\}$, where $k>1$. It is clear that $a_{k-1} \neq n-1$, so $\left\{a_{1}, \ldots a_{k-1}\right\} \subset S_{n-2}$, whence the number of sets in the second group is $f_{n-2}+1$. Therefore

$$
f_{n}=f_{n-1}+f_{n-2}+1
$$

After substituting $u_{n}=f_{n}+1$ we get

$$
u_{1}=2, u_{2}=3, \quad u_{n}=u_{n-1}+u_{n-2}
$$

Therefore the sequence $\left\{u_{n}\right\}_{n=1}^{\infty}$ coincides with the Fibonacci sequence from its third number onwards. Thus we obtain

$$
f_{n}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+2}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+2}\right)-1
$$

