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.

This is the generating function for the fibonnaci sequence:

$$F(x) = \frac{x}{1 - x - x^{2} }$$

I need to get the sequence to find any element from this sequence directly. So I'm trying to find an $x$ coefficient:

$$F(x) = \frac{x}{1 - x - x^{2} } = \frac{x}{(1 - x y_{-})(1 - x y_{+}) } $$

1) I know quadratic equations can be written as $(x - x_{1})(x + x_{2})$, but here it's written differently - does this work for every quadratic equation?

$$F(x) = \frac{1}{(x_{1} - x_{2})}\left(\frac{1}{(1-xx_{1})} - \frac{1}{(1-xx_{2})}\right)$$

This step is understood.

$$F(x) = \frac{1}{\sqrt{5}}\left(\sum{x_{1}}^{n}{x}^{n} - \sum{x_{2}}^{n}{x}^{n}\right)$$

2) What happens here? How come that the epsilons have appeared here?

The next step is to take out the coefficients, it's not difficult so I understand this part.

share|improve this question
2  
What "epsilons"? –  DonAntonio Apr 24 '13 at 15:16
    
uhm, the \sum ($\sum$) thing –  khernik Apr 24 '13 at 15:20
1  
@khernik: It's the geometric series: $\displaystyle \frac{1}{1-xx_1}=\sum_{k=0}^\infty (xx_1)^k$ when $|xx_1|<1$. –  Mårten W Apr 24 '13 at 15:22
2  
@khernik It's a capital Sigma, not an epsilon! –  A.P. Apr 24 '13 at 15:30
add comment

2 Answers

up vote 3 down vote accepted

If you want the sequence $\{1,1,2,3,5,...\}$ as fibonacci sequence, then the generating function is: $$F(x)=\frac{1}{1-x-x^2}$$$$=-\frac{1}{(x_1-x)(x_2-x)}.$$ Otherwise, see another answer. It does not make much difference. Just multiply by $x$. \Then this is same as your decomposition, just done differently. After this, after partial fraction decomposition, you will get that both coefficients are equal and in fact are equal to $-\frac{1}{x_1-x_2}$. To understand this, try the partial fraction decomposition. $$=\frac{1}{x_1-x_2}\left(\frac{1}{x_1-x}-\frac{1}{x_2-x}\right)$$ From here, you take $$\frac{1}{x_1-x}=\frac{1}{\frac{1}{x_1}}\frac{1}{1-\frac{x}{x_1}}$$ Treat this as geometric series so that $\frac{x}{x_1}\le 1$ $$=\frac{1}{x_1-x_2}\sum_{i=0}^{\infty}\left(\frac{x^i}{x_1^{i+1}}-\frac{x^i}{x_2^{i+1}}\right)$$ In the initial factorisation with $x_1$ and $x_2$, you should have obtained roots as $$x_1=-\frac{1-\sqrt{5}}{2};x_2=-\frac{1+\sqrt{5}}{2}$$Thus you have $$\sum_{i=0}^{\infty}\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{i+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{i+1}\right)x^i$$

share|improve this answer
    
I think the formula after "try the partial fraction..." is lacking a minus sign –  DonAntonio Apr 24 '13 at 15:47
    
Thank you for noticing it. It's rather that coefficients are negative. Corrected it. –  user45099 Apr 24 '13 at 15:52
    
My pleasure. Very nicely put and explained answer. + 1 –  DonAntonio Apr 24 '13 at 15:55
    
I think that your Fibonacci sequence begins with two 1s. If you begin with a zero, the generating function should be $x/(1-x-x^2)$ instead of $1/(1-x-x^2)$. Other than that it looks good! –  Jyrki Lahtonen Apr 24 '13 at 16:17
    
@JyrkiLahtonen, Thank You. –  user45099 Apr 24 '13 at 16:31
add comment

Well, given a function $$F(x) = \frac{x}{1-x-x^2}$$ you would like to find the sequence $a_n$ such that $F(x) = \sum_{n=0}^\infty a_n x^n$ (i.e. the Maclaurin series).

Multiplying by $x$ is easy, so you want to represent $\frac{1}{1-x-x^2}$ as something of which you may know the series representation for. A natural choice is the geometric series $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$.

So now, you would like to decompose $$\frac{1}{1-x-x^2} = \frac{A}{1-x\cdot x_+} + \frac{B}{1-x\cdot x_-}.$$

(Find which $x_+$ and $x_-$ are the magic ones that work, and get $A,B$ as well.)

Now

$$F(x) = \frac{x}{1-x-x^2} = \frac{Ax}{1-x\cdot x_+} + \frac{Bx}{1-x\cdot x_-} = Ax \sum_{n=0}^\infty x_+^n x^n + Bx \sum_{n=0}^\infty x_-^n x^n = \sum_{n=0}^\infty \left(A x_+^n + B x^n_-\right) x^{n+1} $$

from where you can easily read off the coefficients you want.

share|improve this answer
add comment

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.