Counting the number of non-consecutive subsets of integers from $1$ to $n$. [closed]

Given a set $X=\{1,2,\ldots,n\}$, how would I count the number of subsets containing only nonconsecutive elements?

For example:

$X=\{1,2,3,4\}$

implies 3 nonconsecutive subsets:

$\{1,3\}, \, \{2,4\}, \, \{1,4\}$

• Doesn't $\{1,3,4\}$ contain $3,4$ which are consecutive? Commented Jan 30, 2017 at 16:16
• As a hint, these subsets would either contain 1 or not. The subsets containing 1 would not contain 2, but anything from 3 on out would be allowed (as long as they're still not consecutive). The subsets not containing 1 could contain anything from 2 on out (again, as long as they're still not consecutive). This leads to a recurrence relation, which will likely be familiar to you. Commented Jan 30, 2017 at 16:19
• Why did you count $\{1,3,4\}$ but not $\{1,2,4\}$?
– MJD
Commented Jan 30, 2017 at 16:24
• @MJD Yes, a typo. Fixed. Commented Jan 30, 2017 at 16:27
• Why did you count $\{1,2,4\}$ but not $\{1,3,4\}$?
– MJD
Commented Jan 30, 2017 at 16:28

Let $f_1(x)$ be the number of ways to pick a subset of numbers from $\{1,2,\cdots,x-1,x\}$ such that the set does not contain 2 consecutive elements and must contain $x$. Let $f_2(x)$ be defined similarly but instead the subset must not contain $x$.

We can see that $f_1(x+1) = f_2(x)$ since if the subset contains $x+1$, it cannot contain $x$

Also, $f_2(x+1) = f_1(x) + f_2(x)$ as you can choose to add $x$ into the subset or not

We also know that $f_1(1) = 1$ and $f_2(1) = 1$

Simplifying:

\begin{align} f_2(x+1) &= f_1(x) + f_2(x)\\ &= f_1(x-1) + 2f_2(x-1)\\ &= 2f_1(x-2) + 3f_2(x-2)\\ &= 3f_1(x-3) + 5f_2(x-3)\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ &= F_x + F_{x+1}\\ &= F_{x+2} \end{align}

\begin{align} f_1(x+1) &= f_2(x)\\ &= f_1(x-1) + f_2(x-1)\\ &= f_1(x-2) + 2f_2(x-2)\\ &= 2f_1(x-3) + 3f_2(x-3)\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ &= F_{x-1} + F_{x}\\ &= F_{x+1} \end{align}

where $F_x$ is the $x$th Fibonacci Number.

Thus $f_1(x) + f_2(x) = F_x + F_{x+1} = F_{x+2}$

• Makes great sense. Accepted. Commented Feb 1, 2017 at 16:06