0
$\begingroup$

There's an example question about finding the general term of Fibonacci Sequence $a_n$ using generating function in my textbook. The solution it provides is as follows:

Step 1

Let $$f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots$$ be the generating function of the sequence, where $a_0=0, a_1=a_2=1$.

Therefore $$xf(x)=a_0x+a_1x^2+a_2x^3+\cdots+a_nx^{n+1}+\cdots$$ and $$x^2f(x)=a_0x^2+a_1x^3+a_2x^4+\cdots+a_nx^{n+2}+\cdots$$

Since $a_n=a_{n-1}+a_{n-2}$, we have $$f(x)-x=xf(x)+x^2f(x)\Longrightarrow f(x)=\frac{x}{1-x-x^2}$$

Step 2

$$f(x)=\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\cdot\frac{\alpha}{x-\alpha}-\frac{1}{\sqrt{5}}\cdot\frac{\beta}{x-\beta}$$

where $\alpha=\frac{-1-\sqrt{5}}{2}, \beta=\frac{-1+\sqrt{5}}{2}$.

$$=-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\frac{x}{\alpha}}+\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\frac{x}{\beta}}\\=-\frac{1}{\sqrt{5}}[1+\frac{x}{\alpha}+(\frac{x}{\alpha})^2+\cdots+(\frac{x}{\alpha})^n+\cdots]+ \frac{1}{\sqrt{5}}[1+\frac{x}{\beta}+(\frac{x}{\beta})^2+\cdots+(\frac{x}{\beta})^n+\cdots] $$

from this we can obtain the general term of $a_n$ easily through the definition of generating function.

My Main Question :

Where does $f(x)=\frac{1}{\sqrt{5}}\cdot\frac{\alpha}{x-\alpha}-\frac{1}{\sqrt{5}}\cdot\frac{\beta}{x-\beta}$ come from?

  1. How do we determine the values of $\alpha$ and $\beta$ ?
  2. Where does $\frac{1}{\sqrt{5}}$ come from ?
  3. How do we know we have to minus $\frac{1}{\sqrt{5}}\cdot\frac{\beta}{x-\beta}$ instead of plus ?

I've noticed that $\alpha$ and $\beta$ are the roots of $x^2+x-1$. However, I still don't know how the book transformed $f(x)$ into $\frac{1}{\sqrt{5}}\cdot\frac{\alpha}{x-\alpha}-\frac{1}{\sqrt{5}}\cdot\frac{\beta}{x-\beta}$. Therefore I think a clear explanation is needed to me. Thanks!

Perhaps this question is stupid to you guys, but I just can't get over it since I didn't get the textbook from school. I have to learn it by myself without a teacher.

In addition, if this tedious post violates the rules of MSE (such as multiple questions in one post is banned), please leave a comment and I'll try my best to fix it.

$\endgroup$
2

2 Answers 2

0
$\begingroup$

This is known as partial fraction decomposition. In short, the idea is to factorize the denominator (you can find the roots using the quadratic formula), then split it into a sum of two fractions corresponding to the roots.

For example, $$\frac1{(x-x_1)(x-x_2)} = \frac{A}{x-x_1} + \frac{B}{x-x_2}.$$

To find $A$ and $B$, multiply both sides by $(x-x_1)(x-x_2)$: $$1 = A(x-x_2) + B(x-x_1).$$ This has to hold for all values of $x$, so you can match coefficients, or start substituting values of $x$ (e.g., $x=x_1$) to solve for $A$ and $B$.

$\endgroup$
2
  • $\begingroup$ Thanks for the direct answer! I honestly didn't know about partial fraction decomposition before. I'll check it out later. $\endgroup$
    – user808951
    Sep 10, 2020 at 16:59
  • 1
    $\begingroup$ @Student1058 You're welcome. This is a simple (once you learn it) but very useful tool. $\endgroup$
    – Théophile
    Sep 10, 2020 at 17:02
0
$\begingroup$

This is know as partial fractions as mentioned by @Théophile.

Since $-(x^2+x-1)=-(x-(-\frac{1}{2}+\frac{\sqrt{5}}{2}))(x-(-\frac{1}{2}-\frac{\sqrt{5}}{2}))=-(x-\beta)(x-\alpha)$ we want to find $A$ and $B$ with:

$$-\frac{x}{(x-\alpha)(x-\beta)}=\frac{A}{x-\alpha}+\frac{B}{x-\beta}=\frac{A(x-\beta)+B(x-\alpha)}{(x-\alpha)(x-\beta)}.$$

Comparing numerators we have $-x=A(x-\beta)+B(x-\alpha).$ Now we substitute values of $x$ to find $A$ and $B$.

For $x=\alpha$ we have $-\alpha=A(\alpha-\beta)$ so $A=\frac{\alpha}{\beta-\alpha}$ and similarly we have $B=\frac{\beta}{\alpha-\beta}.$

Thus we have $$\frac{x}{1-x-x^2}=-\frac{x}{(x-\alpha)(x-\beta)}$$ $$=-\big(\frac{\alpha}{\beta-\alpha}\frac{1}{x-\alpha}+\frac{\beta}{\alpha-\beta}\frac{1}{x-\beta}\big)$$ $$=\frac{1}{\beta-\alpha}\frac{\alpha}{x-\alpha}+\frac{1}{\alpha-\beta}\frac{\beta}{x-\beta}.$$

Now since we let $\beta=-\frac{1}{2}+\frac{\sqrt{5}}{2}$ and $\alpha=-\frac{1}{2}-\frac{\sqrt{5}}{2}$, what are $\beta-\alpha$ and $\alpha-\beta$?

$\endgroup$

You must log in to answer this question.