# On Lecture 1

In today’s lecture I left two computations for you to carry out. Anyone? (If you know how to do both, please show us one, and let someone else do the other one.)

1. Compute the constants $A, B, \alpha, \beta$ such that $\frac{x}{1-x-x^2} = \frac{A}{1- \alpha x} + \frac{B}{1 - \beta x}$.

2.Today I proved this formula for the Fibonacci numbers: $f_n = {n \choose 0} + {n-1 \choose 1} + {n-2 \choose 2} + \cdots.$ Derive this formula directly from the generating function $F(x) = \frac{x}{1-x-x^2}$.

1. andresfelipehiguera

Problem 1:

$\frac{x}{1-x-x^2} =$latex \frac{A}{1- \alpha x} + \frac{B}{1- \beta x}$= $\frac{A+B-(\alpha B + \beta A)x}{1-(\alpha \beta)x + \alpha \beta x}$ Now, we make equal the coefficients: (a) $A+B=0$ (b) $-(\alpha B + \beta A) =1$ (c) $\alpha + \beta =1$ (d)$- \alpha \beta =1$(c) and (d) implies that $(\alpha)^2 - \alpha -1=0$, so $\alpha = \frac{1 \pm \sqrt{5}{2}$ and $\beta = \frac{1 \mp \sqrt{5}{2}$. so if we take $\alpha = \frac{1 + \sqrt{5}{2}$ we get $\beta = \frac{1 - \sqrt{5}{2}$ (a) and (b) implies that $A= \frac{1}{\alpha - \beta}$ Notice that $\alpha - \beta = \sqrt{5}$, so $A= \frac{1}{\sqrt{5}}$ and because of (a) $B= - \frac{1}{\sqrt{5}}$ Andrés F. Higuera andresfelipehiguera.wix.com/economia University of the Andes Department of Economics 2. andresfelipehiguera Problem 1: $\frac{x}{1-x-x^2} =$latex \frac{A}{1- \alpha x}$ + $\frac{B}{1- \beta x}$ = $\frac{A+B-( \alpha B + \beta A)x}{1-(\alpha \beta)x + \alpha \beta x}$

Now, we make equal the coefficients:

(a) $A+B=0$
(b) $-(\alpha B + \beta A) =1$
(c) $\alpha + \beta =1$
(d) $- \alpha \beta =1$

(c) and (d) implies that $(\alpha)^2 - \alpha -1=0$, so $\alpha$ = $\frac{1 \pm \sqrt{5}{2}$ and $\beta = \frac{1 \mp \sqrt{5}{2}$.

so if we take $\alpha$ = $\frac{1 + \sqrt{5}{2}$ we get $\beta = \frac{1 - \sqrt{5}{2}$

(a) and (b) implies that $A= \frac{1}{\alpha - \beta}$

Notice that $\alpha - \beta = \sqrt{5}$, so $A= \frac{1}{\sqrt{5}}$ and because of (a) $B= - \frac{1}{\sqrt{5}}$

Andrés F. Higuera
andresfelipehiguera.wix.com/economia
University of the Andes
Department of Economics

3. hwinkler55

Well, I was able to work out the first one, computing the constants $A, B, \alpha, \beta$, but I made a bit of an assumption I’m not sure was okay.

• hwinkler55

Oops that comment wasn’t complete. Here goes:

We have $\frac{x}{1-x-x^2} = \frac{A}{1-\alpha x} + \frac{B}{1-\beta x}$. I combined the fractions on the right to get $\frac{x}{1-x-x^2} = \frac{A-A\beta x + B - B\alpha x}{(1-\alpha x)(1-\beta x)} \implies \frac{x}{1-x-x^2} = \frac{A-A\beta x + B - B\alpha x}{1-(\alpha+\beta)x-(-\alpha\beta)x^2}$. So then I assumed that the denominators needed to be the same, meaning $\alpha+\beta = 1$ and $-\alpha\beta=1$. I solved for $\alpha$ in the first equation, and substituted it into the second, giving $-(1-\beta)(\beta)=1 \implies \beta^2-\beta-1=0$. Then I solved for $\beta$ and got $\beta = \frac{1+\sqrt{5}}{2}$. So then I substituted this answer back into $\alpha + \beta = 1$ and got $\alpha = \frac{1-\sqrt{5}}{2}$.

Now I went back to my original equation, $\frac{x}{1-x-x^2} = \frac{A-A\beta x + B - B\alpha x}{1-(\alpha+\beta)x-(-\alpha\beta)x^2}$ and got rid of my denominators be multiplying both sides by each denominator. So I got $x - (\beta + \alpha) x^2 + \alpha\beta x^3 = (A+B) + (-A-A\beta - B - B\alpha)x + (-A+A\beta -B + B\alpha)x^2 + (A\beta + B\alpha)x^3$.

(I think I wrote that correct…) So from this we know that coefficients have to be the same, and in particular, I used that $\alpha\beta = A\beta + B\alpha$ and $A+B=0 \implies A=-B$. Since $-\alpha\beta = 1$, I got $-1 = A\beta - A\alpha$ and then substituted in $\alpha, \beta$ and got that $A = \frac{-1}{\sqrt{5}}, B = \frac{1}{\sqrt{5}}$.

I would love input on this! Thanks.

• Your assumption is correct, that’s what partial fractions is about. However, the solution of $\beta^2 - \beta -1=0$ Is $\beta = \frac{1 \pm sqrt{5}}{2}$ .
In particular Federico took $\beta = \frac{1 - sqrt{5}}{2}$ .That’s the reason why your expressions have a diferent sing in comparison to federico’s solution.

4. Yes, I just chose differently and realized that’s which my signs where switched for my $A, \alpha$ and $B, \beta$ pairs. Thanks!

5. Brian Cruz

Lemme take a stab at the second question. The series can be expanded as

$\frac{x}{1-\left(x+x^{2}\right)}=F\left(x\right)=x+x\left(x+x^{2}\right)+x\left(x+x^{2}\right)^{2}+x\left(x+x^{2}\right)^{3}+\cdots.$

I think that Federico meant this expression for the nth Fibonacci
number:

$f_{n}={n-1 \choose 0}+{n-2 \choose 1}+{n-3 \choose 2}+\cdots.$

To obtain this from the series, consider the coefficient of the term
$x^{n}$ when $F\left(x\right)$ is fully expanded. The last term
from the partial expansion shown above that contributes to this coefficient
is $x\left(x+x^{2}\right)^{n-1}$ (why?), which by using binomial
expansion we see becomes

$x\left({n-1 \choose 0}x^{n-1}+{n-1 \choose 1}x^{n-2}x^{2}+{n-1 \choose 2}x^{n-3}x^{4}+\cdots\right).$

The only part of this which contributes to the coefficient of $x^{n}$
is the first term on the inside of the parentheses multiplied by the
$x$ on the outside, or

$x\left({n-1 \choose 0}x^{n-1}\right)={n-1 \choose 0}x^{n}.$

Combinatorially, we can think of the binomial coefficients as the
number of ways to choose a certain number of left terms and right
terms from each of the factors. That is, since

$\left(x+x^{2}\right)^{n-1}=\underbrace{\left(x+x^{2}\right)\cdots\left(x+x^{2}\right)}_{n-1\text{ factors}}.$

then the number of ways of choosing $n-1$ left terms ($x$) and $0$
right terms ($x^{2}$) to get $x^{n-1}$ is

${n-1 \choose n-1}$

or equally

${n-1 \choose 0}$

where the number on the top is the total number of factors.

Okay, so we’ve established the first term of $f_{n}$: ${n-1 \choose 0}$.
Where does the second term ${n-2 \choose 1}$ come from? It comes
from the coefficient of $x^{n}$ when $x\left(x+x^{2}\right)^{n-2}$
is expanded fully. In this case we have $n-2$ factors to choose terms
from, and 1 of those terms must be a $x^{2}$ term. Thus, the contribution
is ${n-2 \choose 1}$.

Continuing in this fashion, we see that indeed
$f_{n}={n-1 \choose 0}+{n-2 \choose 1}+\cdots.$