## A SMALL FIBONACCI SUM

13 05 2010

If $F_{n}$ is the nth Fibonacci Number then:

$\displaystyle \sum_{i=0}^{n}{i \cdot F_{2i}} = n \cdot F_{2n+1} - F_{2n}$

This identity can be easily proved using the method of induction with the basic recurrence relation of Fibonacci Numbers.

How can we find methods for constructing new identities like this one?

References:

[1]-Wikipedia – Fibonacci number
[2]-Chandra, Pravin and Weisstein, Eric W. “Fibonacci Number.” From MathWorld–A Wolfram Web Resource – http://mathworld.wolfram.com/FibonacciNumber.html

## EUCLINACCI – [1]

1 02 2009

Maybe the roughest lesson, someone can ever receive, is this:

$1+1=2$

The implications related to that simple line, can fill a whole library: One of them, is the, so called, Fibonacci sequence:

$\{0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...\}$

Defined as:

$\displaystyle f_{n} = \left\{ \begin{array}{lcr} f_{0}=0;\\ f_{1}=1;\\ f_{n}=f_{n-1}+f_{n-2}; n \ge 2 \end{array} \right\}$

Tabulating the ratio between two consecutive terms of the sequence, appear on insight, two properties:

1) This ratio has a finite limit.
2) Two consecutive Fibonacci numbers are
relatively prime.

$\displaystyle \begin{array}{|r|r|c|} \hline {n} & f_n & f_n/f_{n-1} \\ \hline 0 & 0 & -\\ 1 & 1 & -\\ 2 & 1 & 1.0000 \\ 3 & 2 & 2.0000 \\ 4 & 3 & 1.5000 \\ 5 & 5 & 1.6667 \\ 6 & 8 & 1.6000 \\ 7 & 13 & 1.6250 \\ 8 & 21 & 1.6154 \\ 9 & 34 & 1.6190 \\ 10 & 55 & 1.6176 \\ 11 & 89 & 1.6182 \\ 12 & 144 & 1.6180 \\ 13 & 233 & 1.6181 \\ 14 & 377 & 1.6180 \\ 15 & 610 & 1.6180 \\ 16 & 987 & 1.6180 \\ \hline \end{array}$

To prove the first property, we have:
$\displaystyle I = \lim_{x \to +\infty} \frac{f_n}{f_{n-1}} = \lim_{x \to +\infty} \frac{f_{n-1}+f_{n-2}}{f_{n-1}} = \\ 1 + \lim_{x \to +\infty} \frac{f_{n-2}}{f_{n-1}} = 1 + \lim_{x \to +\infty} \frac{f_{n-1}}{f_n};\\ I=1+\frac{1}{I} \Rightarrow I=1+\frac{1}{I}$

With positive solution, equal to the golden ratio.

$\displaystyle I=\frac{1+\sqrt{5}}{2}=\Phi$

The proof, of this second property, used to be by induction or contradiction [2], but this can also be proved using the oldest procedure designed to calculate de greatest common divisor, GCD, of two integers, known as The Euclidean Algorithm
The Euclidean method constructs a decreasing sequence of integers who share the same GCD.

$(a,b)=(r_0,r_1)=(r_2,r_3)=...=(r_{n-1},r_n)=r_n$

$\left\{\begin{array}{l} a=r_0; \\ b=r_1; \\ r_{i+1}=r_{i-1}-r_i*\bigg \lfloor\frac{r_{i-1}}{r_i}\bigg\rfloor;\\ \end{array}\right\}$

if $r_{i+1}=0$ then $(a,b)=r_i$

Where the function $\displaystyle \lfloor x \rfloor$ is the Floor Function, see [3].

Proof:

$\displaystyle (f_{n},f_{n-1})=(r_0,r_1)$

$\displaystyle r_2=r_0-r_1*\bigg\lfloor\frac{r_0}{r_1}\bigg\rfloor$

$\displaystyle r_2=f_n-f_{n-1}*\bigg\lfloor\frac{f_n}{f_{n-1}}\bigg\rfloor=f_n-f_{n-1}*\bigg\lfloor\frac{f_{n-1}+f_{n-2}}{f_{n-1}} \bigg\rfloor$

$\displaystyle r_2=f_n-f_{n-1}*\bigg\lfloor 1+\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor =f_n-f_{n-1}*\bigg(1+\bigg\lfloor\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor\bigg)$

$\displaystyle f_{n-2}\le f_{n-1} \implies \bigg\lfloor\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor=0$

$\displaystyle r_2=f_n-f_{n-1}=f_{n-2}$

$\displaystyle(f_{n},f_{n-1})=(r_0,r_1)=(r_1,r_2)=(f_{n-1},f_{n-2})=...=(2,1)=1$

The Euclidean Algorithm reproduces all Fibonacci´s sequence and proves that two consecutive terms are relatively prime.

References:

[1]-Fundamentals of Number Theory William J. LeVeque – Courier Dover Publications, 1996 – ISBN 0486689069, 9780486689067
[2]-Consecutive Fibonacci Numbers Relatively Prime – The Math Forum@Drexel
[3] Weisstein, Eric W. “Floor Function.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/FloorFunction.html