Evaluating summations involving Fibonacci numbers in terms of Fibonacci numbers

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

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