Fibonacci numbers

**PaulRS** · January 5th 2008, 02:53 AM

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

, it turned out to be a bit of a surprise really

Go ahead, it's your turn to prove it

**girdav** · August 31st 2009, 12:36 AM

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

**NonCommAlg** · August 31st 2009, 11:12 AM

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

**simplependulum** · September 1st 2009, 12:03 AM

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

Thread: Fibonacci numbers

LinkBack

Thread Tools

Display

Fibonacci numbers

Similar Math Help Forum Discussions

Fibonacci numbers.

Fibonacci Numbers

Fibonacci Numbers

Fibonacci Numbers

Proving Lucas Numbers and Fibonacci Numbers

Search Tags