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. 


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.

