What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$,$F(1)=b$ and $a,b>0$?

Question

What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$, $F(1)=b$ and $a,b>0$ ? It seems to be simple generalization of Fibonacci sequence but I can't find closed form for it nor by myself neither using google.

Answer 1

All solutions to the recurrence $F(n)=F(n-1)+F(n-2)$ are of the form

$$F(n)=A\varphi^n+B\widehat\varphi^n\tag{1}$$

for some constants $A$ and $B$, where $$\varphi=\frac{1+\sqrt5}2\quad\text{and}\quad\widehat\varphi=\frac{1-\sqrt5}2\;.$$

To find $A$ and $B$, just substitute your initial values into $(1)$ to get

$$\left\{\begin{align*} &a=F(0)=A+B\\ &b=F(1)=\varphi A+\widehat\varphi B\;, \end{align*}\right.$$

and solve the resulting system for $A$ and $B$.

Answer 2

The analysis is essentially the same as the one that gives the "Binet" formula for the Fibonacci sequence. Let $\alpha$, $\beta$ be the two roots of the equation $x^2-x-1=0$. Then
$$F(n)=A\alpha^n+B\beta^n,$$ where $A$ and $B$ are chosen so that the initial conditions are satisfied.

So set $A+B=a$ and $A\alpha +B\beta=b$, and solve this system of two linear equations for $A$ and $B$. For example, with $a=2$ and $b=1$, we get the Lucas numbers,

Answer 3

$F(n)=aFib(n-1)+bFib(n)$ (This is assuming Fib(0)=0Fib(1)=1)

You get this by assuming $F(n)=ah_n+b g_n$ and realizing that h and g satisfy the Fibonacci recurrence and the initial conditions are shifted ahead.

Answer 4

You can form the generating function for this particular sequence; it is the same as that for the Fib Seq, but the different initial conditions lead to a different function:

$$g(z) = \frac{a+(b-a)z}{1-z-z^2}$$

To get the numbers in the sequence, Taylor expand this function.

Answer 5

Note that $$ \binom{F(n)}{F(n+1)} = \begin{bmatrix} 0 & 1\\[6pt] 1 & 1 \end{bmatrix} \cdot \binom{F(n-1)}{F(n)} = \begin{bmatrix} 0 & 1\\[6pt] 1 & 1 \end{bmatrix}^n \binom{a}{b} $$ so the problem essentially reduces to diagonalize the matrix $M=\begin{bmatrix}0&1\\1&1\end{bmatrix}$.

Denoting $\phi_1=\frac{1-\sqrt 5}{2}$ and $\phi_2=\frac{1+\sqrt 5}{2}$ (the roots of $x^2-x-1=0$) you have $$ \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix} = T \begin{bmatrix} \phi_1 & 0\\ 0 & \phi_2 \end{bmatrix} T^{-1} $$ where, $$ T = \begin{bmatrix} -\phi_2 & -\phi_1\\ 1 & 1 \end{bmatrix} \quad\text{and}\quad T^{-1} = \frac{1}{\sqrt 5} \begin{bmatrix} -1 & -\phi_1\\ 1 & \phi_2 \end{bmatrix} $$ so that $$ \binom{F(n)}{F(n+1)} = T \begin{bmatrix} \phi_1^n & 0\\[6pt] 0 & \phi_2^n \end{bmatrix} T^{-1} \binom{a}{b} $$ The first row tells you that $$ F(n) = \phi_1\phi_2 \frac { (\phi_1^{n-1}-\phi_2^{n-1})a + (\phi_1^n-\phi_2^n)b } { \sqrt 5 } $$