Prove the recursive formula $a(n)=a(n-1)+a(n-2)$ A set $S$ of integers is said to be lacunar if no two consecutive integers
occur in $S$ (that is, there exists no $i\in\mathbb{Z}$ such that both $i$ and $i+1$ belong to $S$). For example, $\{1,3,6\}$ is lacunar, but $\{2,4,5\}$ is not. (The empty set and any $1$-element set are lacunar, of course.)
For a positive integer $n$, let $a(n)$ denote the number of all lacunar subsets of $[n]$. Find and prove a recursive formula for $a(n)$ in terms of $a(n−1)$ and $a(n−2)$.
I think I already found the recursive formula to be $a(n)=a(n-1)+a(n-2)$ but I could be wrong. Proving it is what I'm really stuck on. Thanks!
 A: A lacunar subset of $[n]$ either contains the number $n$, or it does not. If it does not, then it is a lacunar subset of $[n-1]$. If it does contain $n$, then it does not contain $n-1$, and it can be expressed as the union of $\{n\}$ with a lacunar subset of $[n-2]$.
This gives us two bijections: one between the lacunar subsets of $[n-1]$ and the lacunar subsets of $[n]$ not containing $n$, and one between the lacunar subsets of $[n-2]$ and the lacunar subsets of $[n]$ containing $n$.
Does that work?
A: Maybe try like this:
Let's split $S_n$ into two parts:
$$S_n=A_n\cup B_n$$
where $A_n$ is a set of all lacunar subsets containing $n$ and $B_n$ is set of all lacunar subsets not containing $n$. Of course $A_n\cap B_n = \emptyset$, so $|S_n|=|A_n|+|B_n|$.
$A_n$ can be generated like this:
\begin{align}
A_n
&=\{a\cup \{n\}: a \text{ is lacunar} \wedge n\not\in a \wedge n-1\not\in a\} \\
&=\{a\cup \{n\}: a \text{ is a lacunar subset of } [n-2] \}
\end{align}
Thus
$$A_n = S_{n-2}+\{n\}$$
and 
$$|A_n|=|S_{n-2}|$$
$B_n$ can be defined as:
$$B_n=\{a: a \text{ is lacunar } \wedge n\not\in a\}$$
so 
$$B_n = S_{n-1}\\
|B_n|=|S_{n-1}|$$
Finally:
$$|S_n|=|A_n|+|B_n| = |S_{n-2}|+|S_{n-1}|$$
