4
$\begingroup$

I've come across the following expression in my computer science work (as you can probably tell by the nature of the expression). Is it possible to simplify it into some nice polynomial expressom?

$$\sum_{i = 1}^{z-2} (z - 1) - i + \left ( \sum_{j = i+1}^{z-2} (z - 1) - j \ + \left ( \sum_{k = j+1}^{z-2} (z - 1) - k \ + \ ... \right ) \right) $$

For $z-1$ sigmas.

$\endgroup$
  • 2
    $\begingroup$ Are these nested sums? You might want to stick some parentheses in there to clarify. $\endgroup$ – Jair Taylor May 21 at 21:44
3
$\begingroup$

Let $n=z-1$ to simplify the notation and let's generalize the problem to finding the general sum

$$I_n = \sum_{i_1 = 1}^{n-1}\left(f(n-i_1) + \left ( \sum_{i_2 = i_1+1}^{n-1} f(n-i_2) \ + \ldots + \sum_{i_{n-1}=1+i_{n-2}}^{n-1}f(n-i_{n-1})\right ) \right)$$ In your case we have $f(x) = x$. Note that there will only be $n-1 = z-2$ sums as another sum would be empty (the smallest possible value for $i_k$ is $k$ which is greater than $n-1$ for $i_n$).

By a change of the summation indices $i_k \to n-i_k$ we can write the sum on the form $$I_n = \sum_{i_1 = 1}^{n-1}\left(f(i_1) + \left ( \sum_{i_2 = 1}^{i_1-1} f(i_2) \ + \left ( \sum_{i_3 = 1}^{i_2-1} f(i_3) + \ldots + \sum_{i_{n-1}=1}^{i_{n-2}-1}f(i_{n-1})\right ) \right) \right)$$ which has the nice property than we have removed the $n$ dependence on each sum but the first and which allows us to show that $I_n$ satisfy a simple recurrence relation.

Take the expression for $I_{n+1}$ and split the first sum into that over $i_1=1,2,\ldots,n-1$ and that over $i_1=n$. Notice that for the former case the innermost sum is always empty for the reason we said above so this is just $I_n$ and for the latter case we are just left with $f(n$) plus the same expression as for $I_n$ just with a different name for the summations labels $i_k\to i_{k+1}$. In formulas $$I_{n+1} = I_n + \left(f(n) + \left ( \sum_{i_2 = 1}^{n-1} f(i_2) \ + \left ( \sum_{i_3 = 1}^{i_2-1} f(i_3) + \ldots + \sum_{i_{n}=1}^{i_{n-1}-1}f(i_{n})\right ) \right) \right) \\= I_n + (f(n)+I_n)$$

Thus the complicated looking sum satisfy the simple relation

$$I_{n+1} = 2I_n + f(n)$$

For your special case of $f(x) = x$ the solution is $I_n = 2^n - n - 1 = 2^{z-1} - z$ which is the first Eulerian number (which suggest there likely is some simple combinatorical proof of the identity). As a double check this agrees with a direct numerical computation for $z=3,4,5,\ldots$ which gives $1,4,11,26,\ldots$.

Other simple cases for $f$ are also solveable. For example if $f(n) = 1$ then $I_{n} = 2^{n-1}-1$ and in general if $g$ is a polynomial of degree $n$ then $I_n = c2^n + g(n)$ where $c$ is a constant and $g$ is a polynomial of degree $n$.

$\endgroup$
  • $\begingroup$ interesting the generalization, well done $\endgroup$ – G Cab May 29 at 23:08
4
$\begingroup$

Write $$\sum_{i=1}^{z-2}{ (z - 1) - i}+\sum_{j = i+1}^{z-2} {(z - 1) - j} + \sum_{k = j+1}^{z-2} {(z - 1) - k} + \cdots = \sum_{i =1}^{z-2} {(z - 1)} - \sum_{i = 1}^{z-2} {i}+\left(\sum_{j =1}^{z-2} {(z - 1) - j} - \sum_{j =1}^{i} {(z - 1) - j} \right)+ \left(\sum_{k =1}^{z-2}{ (z - 1) - k} -\sum_{k =1}^{j}{ (z - 1) - k}\right) + \cdots,$$ then use the facts that $$\sum_1^n =n, \,\,\sum_1^n i = \frac{n(n+1)}{2}$$ repeatedly.

$\endgroup$
  • 1
    $\begingroup$ I'm sorry, $\sum_{j=1}^j$? $\endgroup$ – J.G. May 21 at 20:47
  • $\begingroup$ @J.G. Oops, that should be $i.$ Editing. $\endgroup$ – Allawonder May 21 at 20:49
  • 1
    $\begingroup$ that is not the case for nested parenthesis ! $\endgroup$ – G Cab May 23 at 9:47
  • $\begingroup$ @GCab Oh, OP must have changed that question later. I wasn't aware. $\endgroup$ – Allawonder May 29 at 19:55
0
$\begingroup$

Note that we can write $$ \left( {z - 1} \right) - k = \left( \matrix{ \left( {z - 1} \right) - k \cr 1 \cr} \right) = \left( \matrix{ \left( {z - 1} \right) - k \cr \left( {z - 2} \right) - k \cr} \right)\quad \left| {\;z \in \mathbb Z} \right. $$ and that $$ \left( \matrix{ \left( {z - 1} \right) - k \cr \left( {z - 2} \right) - k \cr} \right) = 0\quad \left| {\;z - 2 < k} \right. $$

Then consider that $$ \left( \matrix{ k - \left( {j + 1} \right) \cr k - \left( {j + 1} \right) \cr} \right) = \left\{ {\matrix{ 1 & {j + 1 \le k} \cr 0 & {k < j + 1} \cr } } \right. $$ and finally let's remind that the "Double Convolution" for Binomial gives $$ \sum\limits_{\left( {b\, \le } \right)\,k\,\left( { \le \,d} \right)} {\left( \matrix{ k - r \cr k - b \cr} \right)\left( \matrix{ s - k \cr d - k \cr} \right)} = \left( \matrix{ s - r + 1 \cr d - b \cr} \right)\quad \;\left| {\;d,b \in \mathbb Z} \right. $$ where the bounds on $k$ are indicated in brackets and can be omitted because implicit in the binomial

That premised, we have that the inner sum becomes $$ \eqalign{ & \sum\limits_{j + 1\, \le \,k\, \le \,z - 2} {\left( {z - 1} \right) - k} = \sum\limits_{\left( {j + 1\, \le } \right)\,k\,\left( { \le \,z - 2} \right)} {\left( \matrix{ k - \left( {j + 1} \right) \cr k - \left( {j + 1} \right) \cr} \right)\left( \matrix{ \left( {z - 1} \right) - k \cr \left( {z - 2} \right) - k \cr} \right)} = \cr & = \left( \matrix{ z - \left( {j + 1} \right) \cr \left( {z - 2} \right) - \left( {j + 1} \right) \cr} \right) = \left( \matrix{ z - 1 - j \cr \left( {z - 3} \right) - j \cr} \right) \cr} $$ and from here I think that tou can continue the chain up by yourself.

$\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.