I am trying to come up with an expression for $(x+y)^{\underline{n}}$ in terms of $x^{\underline{r}}$ and $y^{\underline{r}}$. I tried for $n=2$ and $n=3$ and it looks like binomial expansion holds, but would like to prove it (preferably, not by induction).
Progress: $$(x+y)^{\underline{n}} = \sum_{k=0}^{n}\left[{n \atop k}\right](-1)^{n-k}(x+y)^k = \sum_{k=0}^{n}\left[{n \atop k}\right](-1)^{n-k}\sum_{j=0}^k\binom{k}{j}x^jy^{k-j}$$ $$=\sum_{k=0}^{n}\left[{n \atop k}\right](-1)^{n-k}\sum_{j=0}^k\binom{k}{j}[\sum_{i=0}^{j}\left\{{j \atop i}\right\}x^{\underline{i}}][\sum_{r=0}^{k-j}\left\{{k-j \atop r}\right\}y^{\underline{r}}]$$ Which is not more than plugging in well known identities; could you please give me a hint?
I think the answer can be found in the wiki page http://en.wikipedia.org/wiki/Vandermonde%27s_identity#Combinatorial_proof