Counting the number of non-consecutive subsets of integers from $1$ to $n$. 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\}$
 A: 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}$
