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
1
$\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$ Sep 10 '20 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 '20 at 17:02
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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