4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is solved using generating functions. This approach is well described in $\textit{Concrete Mathematics}$, chapter on generating functions. $\endgroup$ – Alex Feb 21 '13 at 13:01
  • $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Feb 21 '13 at 18:39
8
$\begingroup$

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

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

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

$\endgroup$
7
$\begingroup$

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,

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How to find a and b, if I have only given value of F(n) (without knowledge of n) ? $\endgroup$ – Qbik Feb 21 '13 at 13:04
  • 1
    $\begingroup$ $F_n = [z^n]g(z)$. You need two coefficients in the series to solve for $a$ and $b$. $\endgroup$ – Ron Gordon Feb 21 '13 at 13:09
  • $\begingroup$ as I thought, but is there way to effectively search for them ? $\endgroup$ – Qbik Feb 21 '13 at 13:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Ron Gordon Feb 21 '13 at 13:42
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.