Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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 Answers 5

up vote 8 down vote accepted

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

share|improve this answer
    
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 } $$

share|improve this answer

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,

share|improve this answer

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.

share|improve this answer
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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