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. 

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