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}.

Advertisements

7 comments

  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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: