binomial expression of a powered term One answer to a previous question of mine asserted that $$k^2=\binom k2+\binom {k+1}2.$$ 
I checked that the formula is true. However, it intrigued me. Is there a similar expression for $k^3$? How would I find a binomial for $k^n$? This is not a duplicate question to the best of my knowledge.
 A: I looked this up on OEIS A008292 and 
Wikipedia.
Apparently
$$k^m = \sum_{q=0}^{m-1} {k+q\choose m} 
\langle {m\atop q}\rangle$$
with  $\langle  {m\atop  q}\rangle$  the Eulerian  numbers  that  have
generating function
$$\frac{t-1}{t-\exp((t-1)z)}.$$
We now prove this summation formula.
We have the following exponential generating function
$$G_k(z) = \sum_{m\ge 0} k^m \frac{z^m}{m!} = \exp(kz).$$
On the other hand the sum formula gives the EGF
$$H_k(z) = \sum_{m\ge 0} 
\frac{z^m}{m!} \sum_{q=0}^{m-1} {k+q\choose m} 
\langle {m\atop q}\rangle.$$
We can extend this to $q=m$ because the Eulerian number 
$\langle {m\atop m}\rangle$ is zero to get
$$\sum_{m\ge 0} 
\frac{z^m}{m!} \sum_{q=0}^{m} {k+q\choose m} 
\langle {m\atop q}\rangle
\\ = \sum_{q\ge 0} \sum_{m\ge q} 
{k+q\choose m} \frac{z^m}{m!}
\langle {m\atop q}\rangle.$$
Now introduce
$${k+q\choose m}
= \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{(1+w)^{k+q}}{w^{m+1}} \; dw.$$
Substitute this into the sum to get
$$\frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\sum_{q\ge 0} \frac{(1+w)^{k+q}}{w}
\sum_{m\ge q} \frac{1}{w^m} \frac{z^m}{m!}
\langle {m\atop q}\rangle \; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{(1+w)^{k}}{w}
\sum_{q\ge 0} (1+w)^q
\sum_{m\ge q} \frac{1}{w^m} \frac{z^m}{m!}
\langle {m\atop q}\rangle \; dw.$$
Now what we have here is a double
annihilated coefficient extractor
which we now collapse:
$$\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{(1+w)^{k}}{w}
\sum_{q\ge 0} (1+w)^q
[t^q] \frac{t-1}{t-\exp((t-1)z/w)} \; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{(1+w)^{k}}{w}
\frac{w}{1+w-\exp(z)} \; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{(1+w)^{k}}{1+w-\exp(z)} \; dw.$$
The contribution  from the  pole at $w=\exp(z)-1$  which is  simple is
precisely
$$(1+(\exp(z)-1))^k = \exp(kz) = G_k(z),$$
QED.
There is another annihilated coefficient extractor at this
MSE link I and at this
MSE link II and also here at this MSE link III.
The Maple code for the initial lookup at the OEIS was as follows:

Q :=
proc(m)
    local s, sys, sol;

    s := expand(add(a[q]*binomial(k+q,m), q=0..m-1));

    sys := [coeff(s, k, m)=1];
    sys :=
    [op(sys), seq(coeff(s, k, q)=0, q=0..m-1)];

    sol := solve(sys, [seq(a[q], q=0..m-1)]);
    subs(sol[1], [seq(a[q], q=0..m-1)]);
end;

A: I'm not sure if there's a good way to do this in the general case, but just playing around with $k^3$, you know you need something with $\binom{k}{3}$ to get the cubic term. So:
$$\begin{split}
\binom{k}{3} &= \frac{k(k-1)(k-2)}6 = \frac{k^3-3k^2+2k}6 \\
\binom{k+1}{3} &= \frac{k(k+1)(k-1)}6 = \frac{k^3-k}6 \\
\binom{k+2}{3} &= \frac{k(k+2)(k+1)}6 = \frac{k^3+3k^2+2k}6
\end{split}$$
Adding the first and third lines lets you get rid of the $k^2$ term:
$$\binom{k}{3} + \binom{k+2}{3} = \frac{2k^3 + 4k}6$$
And then adding in 4 times the second line lets you get rid of the $k$ term:
$$\binom{k}{3} + 4\binom{k+1}{3} + \binom{k+2}{3} = k^3$$
Through similar fiddling, I can come up with:
$$k^4 = \binom{k}{4} + 11\binom{k+1}{4} + 11\binom{k+2}{4} + \binom{k+3}{4}$$
Though I do not know what the pattern is here. 
A: By counting you have this:
$n^3$ is the ways to color $3$ objects with $n$ colors. So you can either color them with $1$ color in $n$ ways, or with $2$ colors, so you must choose the colors in $\binom{n}{2}$ ways and you choose which elements you want to color in $\binom{3}{2}2$, or in three colors in $\binom{n}{3}3!$ ways. By sum principle and applying a lot Pascal recurrence, you get
$$n^3=n+2\binom{3}{2}\binom{n}{2}+3!\binom{n}{3}=n+3!(\binom{n}{3}+\binom{n}{2})=\binom{n}{1}+\binom{n}{2}+5\binom{n}{2}+6\binom{n}{3}=\binom{n+1}{2}+5(\binom{n}{2}+\binom{n}{3})+\binom{n}{3}=\binom{n}{3}+5\binom{n+1}{3}+\binom{n+1}{2}=\binom{n}{3}+4\binom{n+1}{3}+\binom{n+2}{3}$$ 
Edit:(partial guess to generalize) It has something to do with Stirling numbers of the second kind. I used them in my counting, indeed $k^n=\sum _{i=1}^n\binom{k}{i}S_{n,i}i!$. and using that $i!S_{n,i}=\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}i^n$ and somehow use Pascal recurrence over it.
