# What is wrong with my use of Summation?

I want to compute $r$ according to the following code:

  int r = 0;
for (int i = 1; i <= n; ++i)
for (int j = i+1; j <= n; ++j)
for (int k = i+j-1; k <= n; ++k)
r = r + 1;
return r;


Mathematically, $$r = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=i+j-1}^{n} 1.$$ Using MMA, we get

Sum[1, {i, 1, n}, {j, i + 1, n}, {k, i + j - 1, n}]


1/2 (-n + n^2)

Table[1/2 (-n + n^2), {n, 1, 20}]


{0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190}

However, it does not fit the data obtained by running the algorithm:

{0, 1, 3, 7, 13, 22, 34, 50, 70, 95, 125, 161, 203, 252, 308, 372, 444, 525, 615, 715}

What is wrong with my calculations? And how should I get the closed form of that summation using MMA?

I have also computed $$r = \sum_{i=1}^{n} \sum_{j=i+1}^{n} 1$$ using mma and it gives the same result.

Sum[1, {i, 1, n}, {j, i + 1, n}]


1/2 (-n + n^2)

This is correct for the following code with only two nested loops:

  int r = 0;
for (int i = 1; i <= n; ++i)
for (int j = i+1; j <= n; ++j)
r = r + 1;
return r;


Just do this,

f[n_] := Sum[1, {i, 1, n}, {j, i + 1, n}, {k, i + j - 1, n}]

Table[f[n], {n, 1, 20}]


{0, 1, 3, 7, 13, 22, 34, 50, 70, 95, 125, 161, 203, 252, 308, 372, 444, 525, 615, 715}

Edit

For a closed form, you can use @BobHanlon suggestion,

f2[n_] = FindSequenceFunction[f /@ Range[10], n] // FullSimplify


1/48 (3 (-1 + (-1)^n) + 2 n (2 + n) (-1 + 2 n))

Checking,

(f /@ Range[20]) === (f2 /@ Range[20])


True

Alternatively, using FindLinearRecurrence and RSolve

Clear[f3]

eqns = {f3[n] ==
FindLinearRecurrence[f /@ Range[11]].(f3[n - #] & /@ Range[5]),
Thread[(f3 /@ Range[5]) == (f /@ Range[5])]} // Flatten


{f3[n] == -f3[-5 + n] + 3 f3[-4 + n] - 2 f3[-3 + n] - 2 f3[-2 + n] + 3 f3[-1 + n], f3[1] == 0, f3[2] == 1, f3[3] == 3, f3[4] == 7, f3[5] == 13}

f3[n_] = f3[n] /. RSolve[eqns, f3[n], n][[1]] // FullSimplify


1/48 (3 (-1 + (-1)^n) + 2 n (2 + n) (-1 + 2 n))

f3[n] == f2[n]


True

• How should I get the closed form of that summation using mma? Apr 15 '18 at 12:22
• @BobHanlon Maybe you can post your comment as an answer. Apr 17 '18 at 1:18
• @BobHanlon Thx dear
– zhk
Apr 17 '18 at 1:30

The problem is that the intermediate symbolic sums depend on conditions that are discarded. For instance, the following is true only when n >= i + j - 1; other wise the sum should be 0:

Sum[1, {k, i + j - 1, n}]
(*  2 - i - j + n  *)


Likewise, the following needs the same condition, plus n >= i + 1:

Sum[1, {j, i + 1, n}, {k, i + j - 1, n}]


One way to impose the restriction is through Piecewise:

s = Sum[Piecewise[{{1, n >= i + 1 && n >= i + j - 1}}],
{i, 1, n}, {j, i + 1, n}, {k, i + j - 1, n}];
Table[s, {n, 20}]
(*
{0, 1, 3, 7, 13, 22, 34, 50, 70, 95, 125, 161, 203, 252, 308, 372, 444, 525, 615, 715}
*)