Closed form of recurrence relation $F(n) = 2 + F(n-1) + F(n-2)$ I was figuring out an answer to the question,

How many Boolean arrays of length $n$ could be formed if there are to
  be no two falses in a row?

I could see that it boils down to a Fibonacci like equation,
$$F(n) = 2 + F(n-1) + F(n-2)$$
But I am unable to find a closed form for this recursion. May be I am following the wrong direction here.
Please help.
 A: Given that
$$
F(n + 2) = 2 + F(n + 1) + F(n)
$$
we have
$$
G(n + 2) = G(n + 1) + G(n)
$$
where $G(n) = F(n) + 2$. Because $G(1) = 3$ and $G(2) = 5$, we have
$$
G(n) = H(n + 3)
$$
where $H(n)$ is Fibonacci sequence with $H(1) = 1$ and $H(2) = 1$. The closed form then can be derived from the closed form of Fibonacci numbers.
A: The recurrence stated in the question is incorrect. If it were correct, you’d have $$F(3)=2+1+3=6\;,$$ but in fact $F(3)=5$; the valid strings are $111,110,101,011$, and $010$, and the invalid strings are $000,001$, and $100$, where $0$ represents false, and $1$ represents true.
This is a very good example of a problem in which a little numerical experimentation pays off. It’s not hard to compute the first few $F(n)$ by hand:
$$\begin{array}{rcc}
n:&0&1&2&3&4\\
F(n):&1&2&3&5&8
\end{array}$$
They look suspiciously like the Fibonacci numbers, but offset by two places: if the Fibonacci numbers are denoted by $f_n$ (with $f_0=0$ and $f_1=1$), the table suggests the conjecture that $F(n)=f_{n+2}$. This conjecture would be proved if could show that $F(n)=F(n-1)+F(n-2)$ for $n\ge 2$.
This is fairly straightforward. Say that a Boolean string is good if it does not contain two adjacent instances of false. Let $\sigma$ be a good Boolean string of length $n$, and let $\tau$ be the substring obtained by deleting the last element of $\sigma$. 


*

*If $\sigma$ ends in true, $\tau$ can be any good string of length $n-1$; there are $F(n-1)$ of these, so there are $F(n-1)$ good Boolean strings of length $n$ that end in true.

*If $\sigma$ ends in false, the last element of $\tau$ must be true (because $\sigma$ is good), but the first $n-2$ elements of $\tau$ can be any good string of length $n-2$. There are $F(n-2)$ of these, so there are $F(n-2)$ good Boolean strings of length $n$ that end in false (and hence actually in true false).
These are the only possibilities, and they’re disjoint, so $F(n)=F(n-1)+F(n-2)$. And since we already know that $F(0)=f_2$ and $F(1)=f_3$, it follows immediately that $F(n)=f_{n+2}$ for all $n\ge 0$. We can now use any of the various closed form expressions for the Fibonacci numbers.
A: The standard way is to form the homogeneous solution as a sum of powers obtained from the characteristic equation, and to add a particular solution.
$$f_n-f_{n-1}-f_{n-2}=2$$
corresponds to
$$r^2-r-1=0$$ which has the same roots ($\phi$ and $-\phi^{-1}$ as that of Fibonacci), and is solved by
$$f_n=-2.$$
Hence the general solution
$$f_n=A\phi^n+B(-\phi)^{-n}-2.$$
$A$ and $B$ are determined by plugging the initial conditions,
$$\begin{cases}f_0=A+B-2\\f_1=\phi A-\phi^{-1}B-2.\end{cases}$$
A: I like to do these recurrences in terms of generating functions:
Let $A(x) = \sum_{n\geq1} F(n)x^n$ for some $x<1$. Now take your recurrence, 
$$
F(n+2) = 2 + F(n+1) + F(n),
$$
multiply it by $x^n$ and sum over all $n$. We get
$$
\frac{A(x) - x^2 F(2) - xF(1)}{x^2} = \frac{2x}{1-x} + \frac{A(x)-xF(1)}{x} + A(x),
$$
which, after solving for $A(x)$, gives
$$
A(x) = \frac{x(x+1)}{(1-x)(1-x-x^2)} = \frac{x+2}{1-x-x^2} - \frac{2}{1-x}.
$$
It is well known that the generating functions for the Fibonacci and Lucas numbers are
$$
f(x) = \frac{x}{1-x-x^2}, \quad L(x) = \frac{2-x}{1-x-x^2}
$$
Hence, 
$$
A(x) = 2f(x) + L(x) - \frac{2}{1-x}.
$$
Recall now that $F(n)$ are the coefficients of the series expansion of $A(x)$, and thus
$$
F(n) = 2f_n + L_n - 2,
$$
where $f_n$ and $L_n$ are the $n$th Fibonacci and Lucas numbers respectively.
