# Evaluating summations involving Fibonacci numbers in terms of Fibonacci numbers

There are many summations involving Fibonacci numbers which Mathematica 10.4 is able to evaluate directly in terms of Fibonacci numbers. For example, Mathematica evaluates the summation given below as $F_{2 (n+1)}$.

Sum[Fibonacci[2 i + 1], {i, 0, n}]


However, there are many summations involving Fibonacci numbers which Mathematica 10.4 can evaluate in closed-form, but which Mathematica apparently cannot directly evaluate in terms of Fibonacci numbers. For example, consider the following summation:

Sum[Fibonacci[i]*(-1)^i, {i, 0, n}]


Mathematica 10.4 provides the following evaluation of this expression:

$$\frac{(-2)^{-n} \left(1+\sqrt{5}\right)^{-n-1} \left(2 \left(1+\sqrt{5}\right)^{2 n}+\left(3+\sqrt{5}\right) (-4)^n-\left(5+\sqrt{5}\right) \left(-2-2 \sqrt{5}\right)^n\right)}{\sqrt{5}}$$

However, there is a very simple evaluation of the above alternating sum in terms of the Fibonacci sequence:

$$\sum _{i=0}^n (-1)^i F_i =(-1)^n F_{n-1}-1$$

Similarly, Mathematica 10.4 is not able to evaluate summations such as $\sum _{i=0}^n F_{3 i}$ in terms of Fibonacci numbers.

So it is natural to ask: are there any known algorithms or Mathematica packages for converting closed-form evaluations of sums involving Fibonacci numbers in terms of Fibonacci/Lucas numbers?

• This looks rather hard; note that Mathematica can't even simplify the result of Simplify[FunctionExpand[Fibonacci[n]], n ∈ Integers]. – J. M.'s technical difficulties Jul 1 '16 at 16:29
• I'm not sure how hard it is algorithmically, but I think Mathematica has to make similar choice in a number of areas e.g. whether to express the result in generic terms or use some special function, in this case Fibonacci. For most users, most of the time, the generic result is probably more useful. – mikado Jul 1 '16 at 22:06

There is probably no package or algorithm that can give you answer in all cases. However, I would like to suggest a semi-automatic solution. I will illustrate it with few examples. Notice, I do not know solutions in advance.

## Example 1

t[1] = Table[Sum[Fibonacci[3 i], {i, 0, k}], {k, 0, 10}]
*({0, 2, 10, 44, 188, 798, 3382, 14328, 60696, 257114, 1089154}*)


This sum is given in OP's question. We can analyse it with

at[1]=FindGeneratingFunction[t[1], x]
(*(2 x)/(1 - 5 x + 3 x^2 + x^3)*)


or

Apart[at[1]]
(*1/(2 (-1 + x)) + (-1 - x)/(2 (-1 + 4 x + x^2))*)


The first term results simplify in $-1/2$ sequence. For the first term we do not know much except that it should be expressible in terms of Fibonacci numbers. Therefore:

FindGeneratingFunction[Table[Fibonacci[3 k], {k, 0, 10}], x]
(*-((2 x)/(-1 + 4 x + x^2))*)
FindGeneratingFunction[Table[Fibonacci[3 k + 1], {k, 0, 10}], x]
(*(-1 + x)/(-1 + 4 x + x^2)*)
FindGeneratingFunction[Table[Fibonacci[3 k + 2], {k, 0, 10}], x]
(*(-1 - x)/(-1 + 4 x + x^2)*)
FindGeneratingFunction[Table[Fibonacci[3 k + 3], {k, 0, 10}], x]
(*-(2/(-1 + 4 x + x^2))*)


Simply by observing the results we conclude

t[1]=1/2 Fibonacci[3 k + 2]-1/2

Consider now another more complicated

## Example 2

t[2] = Table[Sum[Fibonacci[5 i] Fibonacci[3 i], {i, 0, k}], {k, 0, 10}]
at[2] = FindGeneratingFunction[t[2], x] // Apart
(*{0, 10, 450, 21190, 995350, 46760600, 2196751960, 103200583850, 4848230682890, 227763641527950, 10700042921088950}*)
(*(1 + x)/(5 (1 - 47 x + x^2)) + (-1 - x)/(5 (1 + 3 x + x^2))*)


Knowing generating functions we can express the sequence as:

t[2]=Fibonacci[8 k + 4]/15 - (-1)^k Fibonacci[1 + 2 k]/5

## Rather complicated example

t[3] = Table[
Sum[Fibonacci[4 i] Fibonacci[3 i] Fibonacci[2 i] Fibonacci[i], {i,
0, k}], {k, 0, 15}];
at[3] = FindGeneratingFunction[t[3], x] // Apart
(*1/(25 (1 + x)) + (1 + x)/(25 (1 - 123 x + x^2)) + (-1 - x)/(
25 (1 - 18 x + x^2)) + (-1 - x)/(25 (1 + 47 x + x^2))*)


Indicating that this sum of products can be expressed in terms of

Fibonacci[6k+a], Fibonacci[8k+b], Fibonacci[10k+c] and a constant.

One knows in principle what is the class of functions to search for. However, I would not dare to make this process fully automatic....

f1[n_] = Sum[Fibonacci[i]*(-1)^i, {i, 0, n}];


If you know or suspect the general form of the model

model = (-1)^n Fibonacci[b*n + c] + d;

data = Table[f1[n], {n, 10}] // Simplify;

f2[n_] = model /. (
NonlinearModelFit[data, model, {b, c, d}, n][
"BestFitParameters"] /.
x_?NumericQ /; (Abs[x - Round[x]] < 10^-10) :> Round[x])

(*  -1 + (-1)^n Fibonacci[-1 + n]  *)


Verifying equivalence for integer values of n

f1[n] == f2[n] // FunctionExpand //
Simplify[#, Element[n, Integers]] &

(*  True  *)


ParametricPlot[ReIm[f2[n]], {n, 0, 9.6},