Fibonacci

Calculation methods (part 1)

We start with a sequence of numbers a1,a2,a2,... . Is it possible to simplify the expression: (a1-a2) + (a2-a3) + (a3-a4) + ... + (an-1-an)? Of course, the answer is yes. This problem is not difficult, for we inmediately notice that all terms but two (the first and the last) cancel each other out. So, the expression equals a1 - an. A sum like this is called a telescopic sum or an accordion sum.


Lets regard an example in which the telescopic property is well camouflaged:
Compute the sum 1/(1x2) + 1/(2x3) + 1/(3x4) + ... + 1/((n-1)xn).
Our task now is to turn this sum into a telescopic sum.
Note that 1/(1x2) = 1/1 - 1/2 and 1/(2x3) = 1/2 - 1/3 and in general 1/((r-1)xr) = 1/(r-1) - 1/r.
Now we replace termwise each term by a difference. This yields:
(1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + ... + (1/(n-1) - 1/n).
Now most terms cancel each other out. The result is 1 - 1/n.



Another example: Calculate 1 + 3 + 5 + 7 + ... + (2n+1). You may wonder how to apply the telescopic property in this case. How do you replace each term by a difference? Well, 2k+1 = - k2 + (k+1)2, thus 1 + 3 + 5 + 7 + ... + (2n+1) = (-02 + 12) + (-12 + 22) + (-22 + 32) + ... + (-n2 + (n+1)2) = (n+1)2. Every time, the greastest problem is, how to replace a term by a difference. The telescopic property can often be used in sums with Fibonacci numbers.



Compute the sum F₁ + F₂ + F₃ + ... + F_n
It is not difficult to replace each term by a usefull difference, for F_n-1 + F_n = F_n+1 or F_n = -F_n-1 + F_n+1.
F₁ + F₂ + F₃ + ... + F_n = (-F₀ + F₂) + (-F₁ + F₃) + (-F₂ + F₄) + (-F₃ + F₅) + ... + (-F_n-1 + F_n+1)
The pairs of numbers with odd index take turn with the pairs of numbers with even index. Let us seperately regard the terms with odd or with even indices. All terms cancel each other out except the first, third, last and the last but two term. Thus the expression equals -F₀-F₁+F_n+1+F_n and this equals -1 + F_n+2.
We could have used the expression F_n = F_n+1 - F_n-1 instead of F_n = -F_n-1 + F_n+1 The result is the same, but it is more difficult to see which terms cancel each other out.

Another example. Calculate F₁² + F₂² + F₃² + ... + F_n².
Again, we make use of the formula F_k = -F_k-1 + F_k+1
F_k² = F_k*(-F_k-1 + F_k+1) = -F_k-1F_k + F_kF_k+1, and so:
F₁² + F₂² + F₃² + ... + F_n² =
(-F₀F₁ + F₁F₂) + (-F₁F₂ + F₂F₃) + (-F₂F₃ + F₃F₄) + ... (-F_n-1F_n + F_nF_n+1) = F_nF_n+1.

A last example. Calculate F₁F₂ + F₂F₃ + F₃F₄ + ... + F_2nF_2n+1.
Notice that the last term is not F_nF_n+1, but F_2nF_2n+1. The number of term appear to be even. That is so, because now we do not replace each term individually by a difference, but pairs of terms. How can F_k-1F_k + F_kF_k+1 be written as a difference of squares?

We have obtained an expression for sums of powers of Fibonacci numbers, namely for
g_1,n = F₁ + F₂ + F₃ + ... + F_n and
g_2,n = F₁² + F₂² + F₃² + ... + F_n²
It becomes difficult to apply the telescope strategy for larger powers like
g_3,n = F₁³ + F₂³ + F₃³ + ... + F_n³