Closed form of recurrence relation $F(n) = 2 + F(n-1) + F(n-2)$

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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}$$

Answer 4

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.