# 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$?

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.

-
This is solved using generating functions. This approach is well described in $\textit{Concrete Mathematics}$, chapter on generating functions. – Alex Feb 21 '13 at 13:01
Once you know a formula for the (standard) Fibonacci numbers $F_i$ which is the case $(a,b)=(0,1)$, you can get a soltuion for $(a,b)=(1,0)$ by a simple shift (since $F_{-1}=1$) and all that remains is to apply linearity of the recursion equation (see answer by Ishan Banerjee). You can get a formula for Fibinacci using linear algebra, generating series or Wikipedia, and probably in many other ways. – Marc van Leeuwen Feb 21 '13 at 18:39

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

-
great, I have value of $F(n)$ and have to find smallest $a,b>0$ your answer is going to be very helpful – Qbik Feb 21 '13 at 13:02

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

-

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,

-

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.

-
How to find a and b, if I have only given value of F(n) (without knowledge of n) ? – Qbik Feb 21 '13 at 13:04
$F_n = [z^n]g(z)$. You need two coefficients in the series to solve for $a$ and $b$. – Ron Gordon Feb 21 '13 at 13:09
as I thought, but is there way to effectively search for them ? – Qbik Feb 21 '13 at 13:37
That's the point of the generating function: it generates the coefficients in terms of $a$, $b$, and $n$. As an example, the coefficient of $z^2$ is $a+b$, $z^3$ is $a+2 b$, etc. You can show that coefficient of $z^n$ for $n>1$ is $f_{n-2} a+f_{n-1} b$, where $f_n$ is the $n$th Fibonacci number. – Ron Gordon Feb 21 '13 at 13:42

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

-