In a math book the following equation is used (without proof). Assuming it is correct (at least for n=1,2,3 it seems to be), how can I prove it? $$\prod_{i=1}^n \sum_{k=1}^n a_k^i = \sum_{k_1,\dots,k_n=1}^n \prod_{i=1}^n a_{k_i}^i$$ I assume the proof has to be done with induction. But I find it extremely complicated to prove the induction step from n to n+1. I regularly get lost somewhere in the middle of the conversion process. Can someone give a hint for a good strategy or for how to find a good strategy? (I cannot find a proof anywhere in a book or in the net. Does anyone know any?)
Note: The i denotes a superscript of a, not a power of a. Sorry, this was a bit misleading. I should have used 2 subscripts.
There $n^n$ terms on both sides. It will not be easy to link $(n+1)^{n+1}$ back to $n^n$. So Induction would be difficult.
The LHS is \begin{eqnarray*} (a_1+a_2+ \cdots +a_n)(a_1^2+a_2^2+ \cdots +a_n^2) \cdots (a_1^i+a_2^i+ \cdots +a_n^i)\cdots (a_1^n+a_2^n+ \cdots +a_n^n) \end{eqnarray*} A general term when you expand this is \begin{eqnarray*} a_{k_1}a_{k_2} \cdots a_{k_i}^i\cdots a_{k_n}^{n} = \prod_{i=1}^{n} a_{k_i}^i \end{eqnarray*} where each $k_i$ will range over $1$ to $n$. So we just need to put in these summations & we have \begin{eqnarray*} \sum_{k_1=1}^{n} \sum_{k_2=1}^{n} \cdots\sum_{k_i=1}^{n} \cdots\sum_{k_n=1}^{n} \prod_{i=1}^{n} a_{k_i}^i \end{eqnarray*}