Results 1 to 4 of 4

Math Help - Fibonacci numbers

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

    Fibonacci numbers

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

    Prove that: <br />
\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} }}<br />
{5}<br />

    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 S_n =\sum_{j=0}^nf_jf_{n-j}
    We have  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<br />
= \sum_{j=0}^nf_jf_{n+1-j} + \sum_{j=0}^nf_jf_{n-j} +f_{n+1}<br />
so
    \boxed{S_{n+2} = S_{n+1}+S_n+f_{n+1}} and S_0 =0, S_1=0
    Now we can show the result by induction:
    S_1 = f_0f_1+f_1f_0 =0+0=0
    and \dfrac{\left(1-1\right)f_1+1f_{1-1}}{5} =0
    Assume that S_n = \dfrac{\left(n-1\right)f_{n+1} + \left(n+1\right)f_{n-1}}5
    S_{n+1} = S_n+S_{n-1}+f_n\\<br />
= \frac 15 \left[\left(n-1\right)f_{n+1} + \left(n+1\right)f_{n-1} +<br />
\left(n-2\right)f_n + nf_{n-2}+5f_n\right]
    S_{n+1}= \frac 15 \left[ nf_{n-2}+\left(n+1\right)f_{n-1} +<br />
\left(n-3\right)f_n+\left(n-1\right)f_{n+1}   \right]
    S_{n+1}= \frac 15 \left[ nf_n+f_{n-1} +<br />
\left(n-1\right)f_{n+2}+4f_n   \right]
    S_{n+1}= \frac 15 \left[ \left(n+3\right)f_n+f_n+f_{n-1} +<br />
\left(n-1\right)f_{n+2}   \right]
    S_{n+1}= \frac 15 \left[ \left(n+3\right)f_n+f_{n+1} +<br />
\left(n-1\right)f_{n+2}   \right]
    S_{n+1}= \frac 15 \left[ \left(n+2\right)f_n+f_n+f_{n+1} +<br />
 \left(n-1\right)f_{n+2}   \right]
    S_{n+1}= \frac 15 \left[ \left(n+2\right)f_n +<br />
  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: \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: \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

    c_0=c_1=0 and 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

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

    and consider

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

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

     D is the differential operator

    sum of them :

     \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  x^2 /5

     \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  x^n

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

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

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

     = \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: October 26th 2010, 03:55 AM
  2. Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 8
    Last Post: June 10th 2010, 08:57 AM
  3. Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 30th 2010, 05:51 AM
  4. Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 16th 2009, 10:46 AM
  5. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 19th 2008, 12:33 AM

Search Tags


/mathhelpforum @mathhelpforum