# How to rewrite and possibly speed up a recursive sum?

I have the following for-loop calculating a multiple nested sum

J = 12;
summed = Sum[(k + 4) k (k + 1), {k, 1, m}];
For[j = 1, j <= J, j++,
summed = Sum[(m + 4 - j) (m - j) (m - j + 1) summed, {m, j + 1, k}];
summed = summed /. k -> m];


I don't think this is the right way to calculate recursive sums in Mathematica but a bigger problem is that for J>200 it becomes slow (several hours on a laptop). I am not sure why it is slow -- every loop increases the polynomial degree by 4 so there is no exponential explosion of terms to sum over.

How to rewrite it and mainly, how to make it fast? Can I hope for J~10000 ?

• Please edit your example so that it is a working piece of code. Jan 20, 2015 at 2:10
• Sorry, it is fixed now. Jan 20, 2015 at 2:17

I rewrote the summation using Nest as follows.

J = 12; j = 0;
Nest[
(j += 1;
Sum[(m + 4 - j) (m - j) (m - j + 1) (# /. k -> m), {m, j + 1, k}]) &,
m (1 + m) (2 + m) (17 + 3 m)/12,
J]


However, your For formulation is just as fast as this Nest.

• Are high-degree polynomials the reason why it slows down or does Sum try to further simplify it? I realize that it must be slowing down as $j$ increases, I just don't understand why it is so for relatively small values of $J$. Jan 20, 2015 at 12:18
• When Sum is given a range with an undefined upper limit, k in your case, it tries to find the analytic solution, which takes time. The argument to Sum gets more and more complicated, so I assume this is where the slowdown arises. Jan 20, 2015 at 18:51
• But the analytic formula for Sum[m^p, {m, j + 1, k}] is HurwitzZeta[-p, 1 + j] - HurwitzZeta[-p, 1 + k] and if I expand it by FunctionExpand[% /. p -> 3000] (to be able to multiply it and sum in the next round of the for-loop) it can do pretty fast. Jan 20, 2015 at 19:04