How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if $1$ and $n$ also count as consecutive? 
How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two
consecutive integers if 1 and n also count as consecutive?

It looks that the number of such subsets obeys the (Fibonacci-style) formula
$$ F(n) = F(n-1)+F(n-2) $$
with $F(0)=1$ and $F(1)=2$, but I wasn't able to prove this conjecture.
 A: For first, let we solve a sub-problem.

Claim: if $S_n$ is the set of the strings of $n$ characters over the alphabet $\Sigma=\{0,1\}$ such that no two consecutive "1"s occur and $l_n=|S_n|$, then
$$ l_n = F_{n+2} $$
where $F_0=0,F_1=1$ and $F_{m+2}=F_{m+1}+F_m$ define the usual Fibonacci numbers.
Lemma: the prefix of an element $s\in S_n$ can be only "0" or "10". This gives $l_{n+2}=l_{n+1}+l_{n}$ while $l_0=1=F_2$ and $l_1=2=F_3$.

See also Fibonacci coding and Zeckendorf's theorem.

Back to the original problem: let $T_n$ ($n\geq 3$) be the set of strings of $n$ characters over the alphabet $\Sigma=\{0,1\}$, where the last character is considered to be adjacent to the first one and no two consecutive "1"s occur.
If the first character of $s\in T_n$ is a "0", then its removal just leaves an element of $S_{n-1}$. Otherwise, if the first character of $s$ is a "1", then both the second character and the last one are zeros, and by removing these three characters we get an element of $S_{n-3}$. By the previous lemma, we have that the number of "neighbours-free" subsets of $\{1,\ldots,n\}$ is given by:
$$F_{n+1}+F_{n-1}=L_n = \left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n\tag{1}$$
for any $n\geq 3$. See also Lucas' numbers.
