# Fibonacci numbers

• Jan 5th 2008, 03:53 AM
PaulRS
Fibonacci numbers
We define the sequence: $
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: $
\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 :D , it turned out to be a bit of a surprise really :eek:

Go ahead, it's your turn to prove it
• Aug 31st 2009, 01:36 AM
girdav
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
= \sum_{j=0}^nf_jf_{n+1-j} + \sum_{j=0}^nf_jf_{n-j} +f_{n+1}
$
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\\
= \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]$

$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]$

$S_{n+1}= \frac 15 \left[ nf_n+f_{n-1} +
\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} +
\left(n-1\right)f_{n+2} \right]$

$S_{n+1}= \frac 15 \left[ \left(n+3\right)f_n+f_{n+1} +
\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} +
\left(n-1\right)f_{n+2} \right]$

$S_{n+1}= \frac 15 \left[ \left(n+2\right)f_n +
nf_{n+2} \right]$
• Aug 31st 2009, 12:12 PM
NonCommAlg
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.$
• Sep 1st 2009, 01:03 AM
simplependulum
I prefer to use this complicated ( depends on you ) method (Happy)

$\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) ]$