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