Generalizing a series of summations

Question

I have $E(x)$, where $x$ goes from $0$ to $A$. For the sake of brevity, let $0 = E(0)$, $1 = E(1)$, $2 = E(2)$, etc...

I want to sum the combinations of these to a depth of $B$, such that if $A=2$ I get:
$B = 1: 0 + 1 + 2$
$B = 2: 00 + 01 + 02 + 11 + 12 + 22$
$B = 3: 000 + 001 + 002 + 011 + 012 + 022 + 111 + 112 + 122 + 222$
and so on.

The most general equation I can manage to describe this is (in the case that $B = 2$, and with general $A$):
$Result = \sum\limits_{i=0}^{A}(E(i)\cdot\sum\limits_{j=i}^{A}(E(j)\cdot\sum\limits_{k=j}^{A}(E(k)\cdot)))$

I ideally want to formulate this such that $B$ is a parameter. I'm not sufficiently well-versed in Mathematics to manage this myself (I'm an experimental physicist...). My question is thus: is there a convenient mathematical notation for nesting summations, or can my sequence be rewritten in an easily writable manner?

Thank you in advance for your time.

Answer 1

Firstly, I'm going to simplify the notation by using $u_i$ instead of $E(i)$, and getting rid of all those unnecessary brackets. The expression is then $$\sum_{0 \leq a_1 \leq a_2 \leq \ldots \leq a_b \leq A} u_{a_1} \ldots u_{a_b}.$$ The simplest way to find an explicit form for this, I think, is to expand different powers of the basic sum, i.e.$$\left( \sum_{0 \leq a \leq A} u_a \right)^b$$ for different powers of $b$, and then doing lots of rearranging. Here I'll show the working for $b=2$.$$\left( \sum_{0\leq a \leq A} u_a \right)^2 = \sum_{0\leq a_1,a_2 \leq A} u_{a_1} u_{a_2} = \sum_{0 \leq a \leq A} u_a^2 + 2 \sum_{0 \leq a_1 < a_2 \leq A} u_{a_1} u_{a_2},$$ $$\sum_{0 \leq a_1 < a_2 \leq A} u_{a_1} u_{a_2} = \frac{1}{2} \left( \sum_{0\leq a \leq A} u_a \right)^2 - \frac{1}{2} \sum_{0 \leq a \leq A} u_a^2,$$and the left hand side is what you were looking for.

This gets more long winded for higher powers of $b.$ For this I'd recommend using the notation introduced in the book "Concrete Mathematics" by Knuth et.al. Let $[A]$ equal $1$ if $A$ is true, $0$ if not. Then, for example, $$\begin{split}\sum_{0\leq a_1,a_2 \leq A} u_{a_1} u_{a_2} &= \sum_{0\leq a_1,a_2 \leq A} ([a_1=a_2] + [a_1<a_2] + [a_1>a_2]) u_{a_1} u_{a_2}\\ &= \sum_{0\leq a_1,a_2 \leq A} ([a_1=a_2] + 2[a_1<a_2]) u_{a_1} u_{a_2} \quad \textrm{by swapping indices for third term} \\ &= \sum_{0 \leq a \leq A} u_a^2 + 2 \sum_{0 \leq a_1 < a_2 \leq A} u_{a_1} u_{a_2}.\end{split}$$ Higher values of $b$ involves multiplying groups of these square condition terms together: first one deals with $a_1$ and $a_2$, next one deals with $a_2$ and $a_3$, and so on.

The point is that the result can be calculated as a sum of several terms, where each terms is a simpler expression to calculate. Implementation-wise, memoization's probably a good idea if you can use it.

Answer 2

You could try the following:

$Result = \sum\limits_{a_1=0}^{A}(E(a_1)\cdot\sum\limits_{a_2=a_1}^{A}(E(a_2)\cdot \cdots\sum\limits_{a_B=a_{B-1}}^{A}(E(a_B)) \cdots ))$