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. 

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