1. ## 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

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

3. 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.$

4. 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) ]$