0
$\begingroup$

I'm new to generating functions, and my lecture showed how to obtain exact closed form expression for Fibonacci numbers.

The coefficients of the generating function F(x) is the Fibonacci sequence {f_n}. After some manipulation,

$$\begin{align} (1-x-x^2)F(x) &= x \tag{A} \\ \\ F(x) &= \frac{x}{1-x-x^2} \tag{B} \\ \\ F(x) &= \frac{\frac{A}{1-a_1x}+\frac{B}{1-a_2x}}{\sqrt 5} \tag{C} \\ \\ F(x) &= \sum_{n=0} f_nx^n \tag{D} \end{align}$$

After doing the partial fraction decomposition, F(x) can then be written as a sum of 2 geometric series the coefficients of the series can be read off to obtain the closed form expression.

The equality in the first line is between formal power series; and the equality in the following lines is in terms of the function. I struggling to understand how the second line follows the first line.

Can someone please explain the sense of the steps?

$\endgroup$
8
  • $\begingroup$ when you say you don't get how the "second line follows from the first line", did you mean how the "third line follows from the second line"? If not, the result is trivial (as I share in my answer... unless you are counting from 0, which is an odd thing to do here. Perhaps line numbers would help?). $\endgroup$
    – Brevan Ellefsen
    Commented Oct 3, 2015 at 4:15
  • $\begingroup$ I guess I just want to know if all the items in the lines should be viewed as are formal power series or functions. $\endgroup$
    – user276396
    Commented Oct 3, 2015 at 4:36
  • $\begingroup$ Thanks I meant the trivial one result like you posted. $\endgroup$
    – user276396
    Commented Oct 3, 2015 at 4:37
  • $\begingroup$ The only lines I don't follow are $$F(x)=\frac{x}{1-x-x^2}$$ $$=F(x)=\frac{1}{\frac{1}{1-a_2}-\frac{\sqrt{5}}{1-a_1}}$$ What intermediate steps are there, because this is a massive leap. $\endgroup$
    – Brevan Ellefsen
    Commented Oct 3, 2015 at 4:44
  • $\begingroup$ Sorry there was a typo I edited the line. $\endgroup$
    – user276396
    Commented Oct 3, 2015 at 5:01

2 Answers 2

Reset to default
1
$\begingroup$

The solutions to $1-y-y^2=0$ are $A=(1+\sqrt 5)/2$ and $B=(1-\sqrt 5)/2$.Therefore for all $x$ we have $1-x-x^2=(1-x/A)(1-x/B)$. Then for $A \ne x \ne B$ we have $$\frac {1}{1-x-x^2}=$$ $$ \frac {1}{(1-x/A)(1-x/B)}=$$ $$\left( \frac {1/A}{1-x/A}- \frac {1/B}{1-x/B} \right) \frac{1}{1/A-1/B}$$ which simplifies a little because $1/A-1/B=(B-A)/AB$ and $B-A=-\sqrt 5$ and $AB=-1$

$\endgroup$
0
$\begingroup$

The second line follows the first line by division. You simply divide both sides by $(1-x-x^2)$

$\endgroup$
1
  • $\begingroup$ i think he was puzzled by the step from 2nd to 3rd line $\endgroup$
    – DanielWainfleet
    Commented Oct 4, 2015 at 13:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .