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$ 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$ Commented Oct 3, 2015 at 4:36
  • $\begingroup$ Thanks I meant the trivial one result like you posted. $\endgroup$ 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$ Commented Oct 3, 2015 at 4:44
  • $\begingroup$ Sorry there was a typo I edited the line. $\endgroup$ 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$ Commented Oct 4, 2015 at 13:05

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.