8
$\begingroup$

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;
| improve this question | | | | |
$\endgroup$
4
$\begingroup$

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

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

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}
*)
| improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.