Fast way to compute a truncated series using Fold

Question

I'm looking at an efficient and fast way to compute the results of a finite summation

$$\sum_{i=0}^Mf_ig_i\,. $$

I noticed that simply applying

Expand/@Sum[f[i]Expand/@g[i],{i,0,M}]

is not very efficient time-wise. The function f is generated recursively for any integer argument. I already use memoization when computing the functions recursively. They look like this

g[0] = 1;
g[n_] := g[n] = Expand@Sum[2^s, {s, 0, n - 1}];

Where do you think is the most consuming part?

f[0] = 1;
f[1] = Sum[Gamma[n] \[Alpha]^n, {n, 1, M}] + O[\[Alpha]]^(M + 1);
f[n_] := f[n] = (f[n - 1] + O[\[Alpha]]^M) (f[1] + O[\[Alpha]]^M) 

• The evaluation of the functions f and g? Is there a way to save the value is an efficient way? A noticed that writing the values into a list (creating "fList" and "gList") using Table is also very timeconsuming.
• Using the function Sum? Would using Fold and pure functions be more efficient? (I tried but I didn't manage to write this sum using pure functions into the Fold function....)

Answer 1

The definition of f[1] uses Set instead of SetDelayed, which means that f[1] evaluates using whatever the current value of M is. If M is not defined, you will get a DifferenceRoot object:

Clear[M]
f[1] = Sum[Gamma[n] α^n, {n, 1, M}] + O[α]^(M + 1)

(*
α^(1 + M) SeriesData[α, 0, {}, 0, 0, 1] + 
 DifferenceRoot[
   Function[{\[FormalY], \[FormalN]}, {\[FormalN] α \[FormalY][\
\[FormalN]] + (-1 - \[FormalN] α) \[FormalY][
         1 + \[FormalN]] + \[FormalY][2 + \[FormalN]] == 0, \[FormalY][1] == 
      0, \[FormalY][2] == α}]][1 + M]
*)

Having f[1] defined as a DifferenceRoot object will slow things down.

Now, if you want to evaluate the sum for different values of M, you will want to clear the memoized values. I think the easiest way to do this is to use the Internal`InheritedBlock the function, so that all memoized values are automatically erased when the Block finishes. You will also want to Block M to the desired value first. First, here is your definition of g and a revised definition of f:

g[0] = 1;
g[n_] := g[n] = Expand@Sum[2^s,{s,0,n-1}];

f[0] = 1;
f[1] := Sum[Gamma[n] α^n, {n,1,M}] + O[α]^(M+1);
f[n_] := f[n] = (f[n-1]+O[α]^M) (f[1]+O[α]^M)

Then, your desired computation:

res[m_] := Internal`InheritedBlock[{M = m, f, g},
    Sum[g[i] f[i], {i, M}]
]

Test:

res[5] //TeXForm

$\alpha +4 \alpha ^2+15 \alpha ^3+57 \alpha ^4+226 \alpha ^5+O\left(\alpha ^6\right)$

res[100]; //AbsoluteTiming

{0.025141, Null}