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.
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.
I like to do these recurrences in terms of generating functions:

Let $A(x) = \sum_{n\geq1} F(n)x^n$ for some $x&lt;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.