# An elementary counting argument

At first when I read about this problem from a certain Indonesian olympiad, I was puzzled as to how would one solve it. It was a pretty nice revelation of strength of proof methods after I solved it.

Find a closed form for $\sum x_1x_2\dots x_k$ where $x_1+x_2+\dots +x_k=n$. The summmation runs over every possible non negative solution of the equation.

First, I observed that a particular product form in the summation like $x_1x_2\dots x_n$ meant selecting one element out of every block created by the composition. This was a clear invitation to a bijection, I just had to find another way of doing it. We can separate $n$ with $2k-1$ slashes where the alternating slashes could mean selecting an element out of a block and closure of a block. Some more tinkering lead to a neat closed form.