Multi-index sum property Exercise 1.2.3.29 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. 
 A: 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.$$
A: 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).
A: 
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.

