4

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.

Qbik
  • 790
  • 1
    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

5 Answers5

8

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

Brian M. Scott
  • 616,228
  • 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
7

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

AndreasT
  • 3,772
6

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,

André Nicolas
  • 507,029
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.

Ron Gordon
  • 138,521
  • 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
  • 1
    $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
  • 1
    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
2

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

Ishan Banerjee
  • 6,459