Exercise in Donald Knuth's The Art of Computer Programming (3e) states the following property of a multi-indexed sum:

$$ \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_ia_ja_k = \frac{1}{3}S_3 + \frac{1}{2}S_1S_2 + \frac{1}{6}S_1^3, $$

where $S_r = \sum_{i=0}^n a_i^r$.

I tried to prove it and failed. What I found are the following identities:

$$ \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_ia_ja_k = \frac{1}{2} \sum_{i=0}^n a_i \left( \left( \sum_{j=0}^i a_j \right)^2 + \sum_{j=0}^i a_j^2 \right), $$

$$ S_1S_2 = \sum_{i=0}^n \sum_{j=0}^n a_i a_j^2, $$

$$ S_1^3 = \sum_{i=0}^n \sum_{j=0}^n \sum_{k=0}^n a_i a_j a_k. $$

Can anybody help in completing the proof?

Based on grand_chat's answer, the identity can be proven inductively.

$$ \begin{align} \sum_{i=0}^{n+1} \sum_{j=0}^i \sum_{k=0}^j a_ia_ja_k & = \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_ia_ja_k + a_{n+1} \sum_{i=0}^{n+1} \sum_{j=0}^i a_ia_j \\ & \stackrel{hyp}{=} \underbrace{\frac{1}{3}S_{n,3} + \frac{1}{2}S_{n,1}S_{n,2} + \frac{1}{6}S_{n,1}^3}_{=:S_n} + \frac{1}{2} a_{n+1} \left( \left( \sum_{i=0}^{n+1} a_i \right)^2 + \sum_{i=0}^{n+1} a_i^2 \right) \\ & = S_n + \frac{1}{2} a_{n+1} \left( \left( \sum_{i=0}^n a_i + a_{n+1} \right)^2 + \sum_{i=0}^n a_i^2 + a_{n+1}^2 \right) \\ & = S_n + \frac{1}{2} a_{n+1} \left( \left( \sum_{i=0}^n a_i \right)^2 + 2 \sum_{i=0}^n a_i a_{n+1} + a_{n+1}^2 + \sum_{i=0}^n a_i^2 + a_{n+1}^2 \right) \\ & = S_n + a_{n+1}^3 + \sum_{i=0}^n a_i a_{n+1}^2 + \frac{1}{2} \left( \sum_{i=0}^n a_i \right)^2 a_{n+1} + \frac{1}{2} \sum_{i=0}^n a_i^2 a_{n+1} \\ & = S_n + a_{n+1}^3 \left( \frac{1}{3} + \frac{1}{2} + \frac{1}{6} \right) + \sum_{i=0}^n a_i a_{n+1}^2 \left( \frac{1}{2} + \frac{3}{6} \right) + \frac{3}{6} \left( \sum_{i=0}^n a_i \right)^2 a_{n+1} + \frac{1}{2} \sum_{i=0}^n a_i^2 a_{n+1} \\ & = \frac{1}{3} \left( S_{n,3} + a_{n+1}^3 \right) + \frac{1}{2} \left( S_{n,1}S_{n,2} + \sum_{i=0}^n a_i a_{n+1}^2 + \sum_{i=0}^n a_i^2 a_{n+1} + a_{n+1}^3 \right) + \frac{1}{6} \left( S_{n,1}^3 + 3 \left( \sum_{i=0}^n a_i \right)^2 a_{n+1} + 3 \sum_{i=0}^n a_i a_{n+1}^2 + a_{n+1}^3 \right) \\ & = \frac{1}{3}S_{n+1,3} + \frac{1}{2}S_{n+1,1}S_{n+1,2} + \frac{1}{6}S_{n+1,1}^3. \end{align} $$

The problem here is that the hypothesis is taken from thin air.


Here is a rather elementary approach based upon two aspects:

  • Iterative calculation

    We look at first at the simpler double sum \begin{align*} A_2&:=\sum_{i=0}^n\sum_{j=0}^ia_ia_j=\sum_{0\leq j\leq i\leq n}a_ia_j\\ &=\sum_{0\leq i\leq j\leq n}a_ia_j \end{align*} and obtain an expression in $S_1=\sum_{i=0}^na_i$ and $S_2=\sum_{i=0}^n a_i^2$. The result will then be used for calculating the triple sum.

  • Manipulation of index range

    We can represent the sum using a more compact index range notation and obtain after renaming the variables \begin{align*} A_3&:=\sum_{i=0}^n\sum_{j=0}^i\sum_{k=0}^ja_ia_ja_k =\sum_{0\leq k\leq j\leq i\leq n}a_ia_ja_k\\ &=\sum_{0\leq i\leq j\leq k\leq n}a_ia_ja_k\\ \end{align*}

    We will often rearrange the index range for our needs.

$$ $$

We obtain \begin{align*} A_2 &= \sum_{0\leq i\leq j\leq n}a_ia_j\\ &=\sum_{0\leq i,j\leq n}a_ia_j-\sum_{0\leq j<i\leq n}a_ia_j\tag{1}\\ &=\left(\sum_{0\leq i\leq n}a_i\right)\left(\sum_{0\leq j\leq n}a_j\right) -\left(\sum_{0\leq j\leq i\leq n}a_ia_j-\sum_{0\leq j=i\leq n}a_ia_j\right)\\ &=S_1^2-\left(A_2-\sum_{i=0}^na_i^2\right)\\ &=S_1^2-A_2+S_2\\ \end{align*}

We conclude the double sum $A_2$ can be represented as \begin{align*} A_2&=\frac{1}{2}S_1^2+\frac{1}{2}S_2\tag{2} \end{align*}

In (1) we represent the upper triangle range $0\leq i\leq j\leq n$ as square $0\leq i,j\leq n$ minus lower triangle $0\leq j< i\leq n$. In the following line we do some more rearrangements of the index range from which we can easily derive the representation in $S_1$ and $S_2$.

And now the triple sum. We show

the following is valid \begin{align*} A_3:=\sum_{i=0}^n\sum_{j=0}^i\sum_{k=0}^ja_ia_ja_k=\frac{1}{3}S_3+\frac{1}{2}S_1S_2+\frac{1}{6}S_1^3\tag{3} \end{align*}

We start with the RHS \begin{align*} \frac{1}{3}S_3&+\frac{1}{2}S_1S_2+\frac{1}{6}S_1^3\\ &=\frac{1}{3}S_3+\frac{1}{2}S_1S_2+\frac{1}{6}S_1S_1^2\\ &=\frac{1}{3}S_3+\frac{1}{2}S_1S_2+\frac{1}{6}S_1\left(2A_2-S_2\right))\tag{4}\\ &=\frac{1}{3}\left(S_3+S_1S_2+S_1A_2\right)\\ &=\frac{1}{3}\left(\sum_{i=0}a_i^3+\sum_{i=0}^na_i\sum_{j=0}^na_j^2 +\sum_{i=0}^na_i\sum_{0\leq j\leq k\leq n} a_ja_k\right)\\ &=\frac{1}{3}\left(\sum_{0\leq i= j=k\leq n} a_ia_ja_k +\sum_{0\leq i\leq n}\sum_{0\leq j=k\leq n}a_ia_ja_k +\sum_{0\leq i\leq n}\sum_{0\leq j\leq k\leq n}a_ia_ja_k\right)\tag{5} \end{align*}

In (4) we use the double sum representation (2). We show the last expression in brackets is equal to $3A_3$. At first we split the right-most triple sum.

  • Right-most sum

    Since $i$ in $0\leq i\leq n$ is either less or equal $j$ or greater $j$ and less or equal $k$ or greater $k$ we obtain three sums.

    \begin{align*} \sum_{0\leq i\leq n}\sum_{0\leq j\leq k\leq n}a_ia_ja_k &=\sum_{0\leq i \leq j\leq k\leq n}a_ia_ja_k +\sum_{0\leq j<i\leq k\leq n}a_ia_ja_k +\sum_{0\leq j\leq k<i\leq n}a_ia_ja_k\\ &=A_3 +\sum_{0\leq j<i\leq k\leq n}a_ia_ja_k +\sum_{0\leq j\leq k<i\leq n}a_ia_ja_k\\ &=A_3 +\sum_{0\leq i<j\leq k\leq n}a_ia_ja_k +\sum_{0\leq i\leq j<k\leq n}a_ia_ja_k \end{align*}

Next we focus on the middle sum and split the range conveniently

  • Middle sum

    We see the index $0\leq i\leq n$ in the middle sum is either less or equal $j(=k)$ or greater $j(=k)$ and we obtain two sums.

    \begin{align*} \sum_{0\leq i\leq n}\sum_{0\leq j=k\leq n}a_ia_ja_k &=\sum_{0\leq i\leq j=k\leq n}a_ia_ja_k+\sum_{0\leq j=k<i\leq n}a_ia_ja_k\\ &=\sum_{0\leq i\leq j=k\leq n}a_ia_ja_k+\sum_{0\leq i=j<k\leq n}a_ia_ja_k \end{align*}

We can now combine the left-most sum with the middle sum and the result with the right-most part.

  • Combining sums

    The colors $\color{red}{\text{red}}$, $\color{blue}{\text{blue}}$ and $\color{green}{\text{green}}$ indicate combined sums.

\begin{align*} \sum_{0\leq i= \color{red}{j=k}\leq n}& a_ia_ja_k + \left(\sum_{0\leq i\leq j=k\leq n}a_ia_ja_k+\sum_{0\leq i=\color{red}{j<k}\leq n}a_ia_ja_k\right)\\ &\qquad +\left(A_3 +\sum_{0\leq i<j\leq k\leq n}a_ia_ja_k +\sum_{0\leq i\leq j<k\leq n}a_ia_ja_k\right)\\ &=\sum_{0\leq i\leq \color{blue}{j=k}\leq n}a_ia_ja_k+\sum_{0\color{green}{\leq i=}\color{red}{j\leq k}\leq n}a_ia_ja_k\\ &\qquad +\left(A_3 +\sum_{0\leq \color{green}{i<j}\leq k\leq n}a_ia_ja_k +\sum_{0\leq i\leq \color{blue}{j<k}\leq n}a_ia_ja_k\right)\\ &=A_3 +\sum_{0\leq \color{green}{i\leq j}\leq k\leq n}a_ia_ja_k +\sum_{0\leq i\leq \color{blue}{j\leq k}\leq n}a_ia_ja_k\\ &=3A_3\tag{6} \end{align*}

Finally we obtain from (5) and (6)

\begin{align*} \frac{1}{3}S_3&+\frac{1}{2}S_1S_2+\frac{1}{6}S_1^3\\ &=\frac{1}{3}\left(\sum_{0\leq i= j=k\leq n} a_ia_ja_k +\sum_{0\leq i\leq n}\sum_{0\leq j=k\leq n}a_ia_ja_k +\sum_{0\leq i\leq n}\sum_{0\leq j\leq k\leq n}a_ia_ja_k\right)\\ &=\frac{1}{3}\left(3A_3\right)\\ &=A_3 \end{align*} and the claim follows.

| cite | improve this answer | |
  • $\begingroup$ Is $A_3 := \sum_{i=0}^n \sum_{j=i}^n \sum_{k=j}^n a_ia_ja_k$ the same as $\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_ia_ja_k$? $\endgroup$ – Max Herrmann Aug 24 '16 at 7:23
  • 1
    $\begingroup$ @MaxHerrmann: Yes, it's the same due to symmetry. If you consider your triple sum we have $0\leq i\leq n$ and $0\leq j\leq i$ giving $0\leq j\leq i\leq n$. With the third index $0\leq k\leq j$ we get $0\leq k\leq j\leq i\leq n$. Due to symmetry we can exchange the variable names and get $0\leq i\leq j\leq k\leq n$. But this was not my intention, sorry. I've started erroneously the other way round. Maybe, you could do it in the right order? :-; $\endgroup$ – Markus Scheuer Aug 24 '16 at 7:56
  • $\begingroup$ @MaxHerrmann: I've updated my answer accordingly. Regards, $\endgroup$ – Markus Scheuer Aug 24 '16 at 11:46
  • $\begingroup$ This really is a brillantly dedicated precise answer. $\endgroup$ – Max Herrmann Aug 24 '16 at 12:43
  • 1
    $\begingroup$ @MaxHerrmann: Your representation is not admissible. When looking at your left-most triple sum note that $j$ is written as the upper limit of the outer sum although $j$ has scope of range starting from the middle sum to the innermost sum. In other words, you are not allowed to use the bound index $j$ outside of it's scope. But, don't panic, the correct representation of the first part is $\sum_{0\leq i\leq j\leq k\leq n}a_ia_ja_k=\sum_{k=0}^n\sum_{j=0}^k\sum_{i=0}^ja_ia_ja_k=\sum_{k=0}^na_k\sum_{j=0}^ka_j\sum_{i=0}^ja_i$ and analogously the other triple sums. Ok? $\endgroup$ – Markus Scheuer Aug 25 '16 at 8:23

For future reference this is the sum over all multisets of size three chosen from the variables $A_0$ to $A_n$ and evaluated at $a_q.$ Therefore by the Polya Enumeration Theorem it is given by

$$\left.Z(S_3)\left(\sum_{q=0}^n A_q\right)\right|_{A_q=a_q}$$

where $Z(S_3)$ is the cycle index of the symmetric group $Z(S_3).$ Now the permutations are $(1)(2)(3)$, $(12)(3)$, $(13)(2)$, $(23)(1)$ and $(123)$ and $(132).$ Therefore the cycle index is given by

$$Z(S_3)= \frac{1}{6} (s_1^3 + 3 s_1 s_2 + 2 s_3) = \frac{1}{6} s_1^3 + \frac{1}{2} s_1 s_2 + \frac{1}{3} s_3.$$

This gives for the sum

$$ \left.\frac{1}{6} s_1^3 + \frac{1}{2} s_1 s_2 + \frac{1}{3} s_3 \right|_{s_r=S_r} = \frac{1}{6} S_1^3 + \frac{1}{2} S_1 S_2 + \frac{1}{3} S_3$$

where we have used the standard cycle index substitution

$$s_r = \left.\sum_{q=0}^n A_q^r\right|_{A_q=a_q} = S_r.$$

| cite | improve this answer | |
  • $\begingroup$ "Therefore by the Polya Enumeration Theorem..." But that probably beats the purpose of the exercise. =/ $\endgroup$ – Pedro Tamaroff Aug 22 '16 at 23:41
  • $\begingroup$ That's why I posted it for future reference. I believe seeing small cycle indices being computed manually helps the reader understand that the mechanics of applying PET are really very simple. $\endgroup$ – Marko Riedel Aug 22 '16 at 23:42
  • $\begingroup$ I agree. Missed the first words there, my bad. $\endgroup$ – Pedro Tamaroff Aug 22 '16 at 23:47
  • $\begingroup$ PET without notational barriers is easily accessible to a freshman combinatorics student. $\endgroup$ – Marko Riedel Aug 22 '16 at 23:48
  • $\begingroup$ This answer helped me understand that it's a combinatorics problem. In my case, it's definitely a future reference. $\endgroup$ – Max Herrmann Aug 23 '16 at 5:09

You can use induction to prove this. Check that the base case $n=0$ holds.

For the inductive step, use a double subscript: $$S_{n,r}:=\sum_{i=0}^n a_i^r$$ to make the dependence on $n$ explicit. It is clear that $$S_{n+1,r} = S_{n,r} + a_{n+1}^r\quad\text{for}\quad r=1,2,3.\tag1$$ Write $M_n$ as an abbreviation for $\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_ia_ja_k$. Then we have $$M_{n+1}=M_n+a_{n+1}\sum_{j=0}^{n+1} a_j\sum_{k=0}^ja_k=M_n+a_{n+1}\left(\sum_{j=0}^na_j\sum_{k=0}^ja_k + a_{n+1}\sum_{k=0}^{n+1}a_k\right).\tag2 $$ OTOH, you know what the final result needs to be: $$M_{n+1}=\frac13S_{n+1,3} +\frac12S_{n+1,1}S_{n+1,2}+\frac16S_{n+1,1}^3.\tag3 $$ It remains to show that (2) equals (3). You can achieve this with the help of (1).

| cite | improve this answer | |

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.