Expression for power of a natural number in terms of binomial coefficients Is there a general expression for the pth power of a natural number k in terms of binomial coefficients? 
I found this identity in a high-school text, which was obtained by simply equating coefficients:
$k^3 = 6 \binom{k}{3} + 6 \binom{k}{2} + \binom{k}{1}$
I would like to know the general expression for $k^p$ in terms of binomial coefficients. 
I would also appreciate it if someone could tell me the names of texts which might cover such expressions, and what they can be used for.
 A: The coefficients $6,6$ and $1$ in that expansion are closely related to Stirling numbers of the second kind. There is an identity
$$x^n=\sum_k{n\brace k}x^{\underline k}=\sum_k{n\brace k}x(x-1)(x-2)\dots(x-k+1)\;,$$
which in the case $x=m\in\Bbb N$ becomes
$$m^n=\sum_k{n\brace k}\frac{m!}{(m-k)!}=\sum_k{n\brace k}k!\binom{m}k\;,$$
so that the coefficients are the numbers $\displaystyle k!{n\brace k}$. I didn’t bother to specify the range of $k$, because it’s implicitly determined by the Stirling numbers themselves: for $n>0$, the only values of $k$ for which $\displaystyle{n\brace k}\ne0$ are $k=1,\dots,n$.
A good place to learn about such things is the excellent book Concrete Mathematics, by Graham, Knuth, & Patashnik.
A: See the Wikipedia under Binomial coefficients as a basis for the space of polynomials.
In your particular case, and using the notation of the Wikipedia article, from which I am quoting formulas,
$$
t^{d} = \sum_{k=0}^d a_k \binom{t}{k}, 
$$
where
$$
a_k = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} i^d.
$$
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
Also, from Knuth CM-book:
$$
\left\{\begin{array}{rcll}
\ds{n^{\underline{1}}} & \ds{=} & \ds{n,} &  \ds{n = n^{\underline{1}}}
\\
\ds{n^{\underline{2}}} & \ds{=} & \ds{n\pars{n - 1},} & \ds{n^{2} = n^{\underline{1}} + n^{\underline{2}}}
\\
\ds{n^{\underline{3}}} & \ds{=} & \ds{n\pars{n - 1}\pars{n - 2},} & \ds{n^{3} = n^{\underline{1}} + 3n^{\underline{2}} +
n^{\underline{3}}}
\\
\ds{\vdots} & \ds{\vdots} & \ds{\vdots} & \ds{\vdots} 
\end{array}\right.
$$
For instance $\ds{\pars{~sum\ \mbox{looks like an}\ integration~}}$:
\begin{align}
&\bbox[5px,#ffd]{\sum_{n = 1}^{N}k^{2}} =
\sum_{k = 1}^{N}\pars{k^{\underline{1}} + k^{\underline{2}}} =
\pars{{1 \over 2}\,k^{\underline{2}} +
{1 \over 3}k^{\underline{3}}}_{1}^{N + 1}
\\[5mm] = &\
\bracks{{1 \over 2}\,\pars{N + 1}^{\underline{2}} +
{1 \over 3}\pars{N + 1}^{\underline{3}}}\ -\
\underbrace{\pars{{1 \over 2}\,1^{\underline{2}} +
{1 \over 3}1^{\underline{3}}}}_{\ds{= 0}}
\\ = &\
{1 \over 2}\pars{N + 1}N +
{1 \over 3}\pars{N + 1}N\pars{N - 1}
\\[5mm] = &\
\pars{N + 1}N\bracks{{1 \over 2} +
{1 \over 3}\pars{N - 1}}
\\[5mm] = &\
\bbx{N\pars{N + 1}\pars{2N + 1} \over 6} \\ &
\end{align}
