Results 1 to 4 of 4

Thread: Fibonacci numbers

  1. #1
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571

    Fibonacci numbers

    We define the sequence: $\displaystyle
    f_n = \left\{ \begin{gathered}
    0{\text{ if }}n = 0 \hfill \\
    1{\text{ if }}n = 1 \hfill \\
    f_{n - 1} + f_{n - 2} {\text{ if }}n \geqslant 2 \hfill \\
    \end{gathered} \right.
    $

    Prove that: $\displaystyle
    \sum\limits_{j = 0}^n {\left( {f_j \cdot f_{n - j} } \right)} = \frac{{\left( {n + 1} \right) \cdot f_{n - 1} + \left( {n - 1} \right) \cdot f_{n + 1} }}
    {5}
    $

    A nice identity indeed , it turned out to be a bit of a surprise really

    Go ahead, it's your turn to prove it
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member girdav's Avatar
    Joined
    Jul 2009
    From
    Rouen, France
    Posts
    678
    Thanks
    32
    Let $\displaystyle S_n =\sum_{j=0}^nf_jf_{n-j}$
    We have $\displaystyle S_{n+2} = \sum_{j=0}^nf_j\left(f_{n+1-j}+f_{n-j}\right) +f_{n+1}f_1 +f_{n+2}f_0
    = \sum_{j=0}^nf_jf_{n+1-j} + \sum_{j=0}^nf_jf_{n-j} +f_{n+1}
    $ so
    $\displaystyle \boxed{S_{n+2} = S_{n+1}+S_n+f_{n+1}}$ and $\displaystyle S_0 =0$, $\displaystyle S_1=0$
    Now we can show the result by induction:
    $\displaystyle S_1 = f_0f_1+f_1f_0 =0+0=0$
    and $\displaystyle \dfrac{\left(1-1\right)f_1+1f_{1-1}}{5} =0$
    Assume that $\displaystyle S_n = \dfrac{\left(n-1\right)f_{n+1} + \left(n+1\right)f_{n-1}}5$
    $\displaystyle S_{n+1} = S_n+S_{n-1}+f_n\\
    = \frac 15 \left[\left(n-1\right)f_{n+1} + \left(n+1\right)f_{n-1} +
    \left(n-2\right)f_n + nf_{n-2}+5f_n\right]$
    $\displaystyle S_{n+1}= \frac 15 \left[ nf_{n-2}+\left(n+1\right)f_{n-1} +
    \left(n-3\right)f_n+\left(n-1\right)f_{n+1} \right]$
    $\displaystyle S_{n+1}= \frac 15 \left[ nf_n+f_{n-1} +
    \left(n-1\right)f_{n+2}+4f_n \right]$
    $\displaystyle S_{n+1}= \frac 15 \left[ \left(n+3\right)f_n+f_n+f_{n-1} +
    \left(n-1\right)f_{n+2} \right]$
    $\displaystyle S_{n+1}= \frac 15 \left[ \left(n+3\right)f_n+f_{n+1} +
    \left(n-1\right)f_{n+2} \right]$
    $\displaystyle S_{n+1}= \frac 15 \left[ \left(n+2\right)f_n+f_n+f_{n+1} +
    \left(n-1\right)f_{n+2} \right]$
    $\displaystyle S_{n+1}= \frac 15 \left[ \left(n+2\right)f_n +
    nf_{n+2} \right]$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    a result of this problem is this identity: $\displaystyle \sum_{j = \lfloor \frac{n+1}{2} \rfloor }^{n-1} \binom{j-1}{n-j-1}j = \frac{(n+1)f_{n-1} + (n-1)f_{n+1}}{5}, \ \ n \geq 2,$ because: $\displaystyle \sum_{n=0}^{\infty}c_nx^n=\frac{x^2}{(1-x-x^2)^2}=\left(\sum_{n=0}^{\infty}f_n x^n \right)^2=\sum_{n = 0}^{\infty} \left(\sum_{j=0}^n f_jf_{n-j} \right)x^n,$ where

    $\displaystyle c_0=c_1=0$ and $\displaystyle c_n = \sum_{j = \lfloor \frac{n+1}{2} \rfloor }^{n-1} \binom{j-1}{n-j-1}j, \ \ n \geq 2.$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    715
    I prefer to use this complicated ( depends on you ) method

    $\displaystyle \frac{x}{1-x-x^2} = \sum_{k=0}^{\infty}(f_k x^k)$

    and consider

    $\displaystyle 2 D[ \frac{x}{1-x-x^2}] = \frac{-2}{1-x-x^2} + \frac{4-2x}{(1-x-x^2)^2}$ and

    $\displaystyle D[\frac{1}{1-x-x^2}] = \frac{2x+1}{(1-x-x^2)^2}$

    $\displaystyle D$ is the differential operator

    sum of them :

    $\displaystyle \frac{5}{(1-x-x^2)^2} = 2D[ \frac{x}{1-x-x^2}] + D[\frac{1}{1-x-x^2}] + \frac{2}{1-x-x^2}$

    multiply $\displaystyle x^2 /5 $

    $\displaystyle \frac{x^2}{(1-x-x^2)^2} = \frac{1}{5} (2x^2D[ \frac{x}{1-x-x^2}] + x^2D[\frac{1}{1-x-x^2}] + x \frac{2x}{1-x-x^2}) $

    compare the coefficient of $\displaystyle x^n$

    from the left hand side : we obtain the series from your question
    from the right hand side :

    $\displaystyle = \frac{1}{5} [ 2(n-1)f_{n-1} +(n-1)f_{n} + 2f_{n-1}] $

    $\displaystyle = \frac{1}{5} [ f_{n-1} (2n-2+2-n+1 ) + f_{n+1}(n-1) ]$

    $\displaystyle = \frac{1}{5} [ f_{n-1} (n+1 ) + f_{n+1}(n-1) ]$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci numbers.
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Oct 26th 2010, 02:55 AM
  2. Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 8
    Last Post: Jun 10th 2010, 07:57 AM
  3. Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 30th 2010, 04:51 AM
  4. Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Mar 16th 2009, 09:46 AM
  5. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 18th 2008, 11:33 PM

Search Tags


/mathhelpforum @mathhelpforum