Evaluating summations involving Fibonacci numbers in terms of Fibonacci numbers

Question

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?

Answer 1

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

Answer 2

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  *)

EDIT: Added plot

ParametricPlot[ReIm[f2[n]], {n, 0, 9.6},
 PlotRange -> All,
 Epilog -> {Red, AbsolutePointSize[4],
   Tooltip[Point[{#[[2]], 0}], #] & /@
    Table[{n, f1[n] // Simplify}, {n, 9}]}]