Find the total number of sequences of length $n$ containing only letters $A$ and $B$ such that no two $A$s are next to each other. For example, for $n = 2$, there are $3$ possible sequences: $AB$, $BA$, and $BB$.
Let's call a sequence without consecutive $A$s a good sequence, and $F_n$ be the number of good sequences with $n$ letters. Such a sequence can either start with letter $A$ or letter $B$.
If it starts with $A$, then the $2^{nd}$ letter must be $B$ and the $3^{rd}$ letter can be either $A$ or $B$. In other words, if a good sequence of $n$ letters starts with $A$, then its first two letters are fixed. Hence such a $n$-letter sequence is uniquely determined by its subsequence starting from the $3^{rd}$ letter which has $(n-2)$ letters. This means that the number of such sequences with $n$-letter equals that of corresponding sequences having $(n-2)$ letters, i.e. $F_{n-2}$.
If it starts with $B$, then the $2^{nd}$ letter can be either $A$ or $B$. This means that the number of such sequences is the same as that of corresponding subsequence of $(n-1)$ letters, i.e. $F_{n-1}$.
It follows that it must hold that $$F_{n}=F_{n-1}+F_{n-2}$$
where $F_{1}=1$ and $F_2=2$. This is a standard linear regression and its solution is $$F_n=\boxed{\frac{5+3\sqrt{5}}{10}\left(\frac{1+\sqrt{5}}{2}\right)^n+\frac{5-3\sqrt{5}}{10}\left(\frac{1-\sqrt{5}}{2}\right)^n}$$