Proof by induction for Stirling Numbers I am asked this:

For any real number x and positive integer k, define the notation
  [x,k] by the recursion [x,k+1] = (x-k) [x,k] and [x,1] = x.
If n is any positive integer, one can now express the monomial x^n as
  a polynomial in [x,1], [x,2], . . . , [x,n]. Find a general formula
  that accomplishes this, and prove that your formula is correct.

I was able to figure out using stirling numbers that the formula is:
$$X^n=\sum^{n}_{k=1} {n\choose k}(X_k)$$
where $[x,k]$ is a decreasing factorial $X_k = x(x-1)...(x-k+1)$
How can I prove the formula above by using induction?
 A: I prefer the notation $x^{\underline k}$ for the falling power, so I’ll use that. You don’t want binomial coefficients in your expression: you want Stirling numbers of the second kind, denoted by $\left\{n\atop k\right\}$, and you want to show by induction on $n$ that
$$x^n=\sum_{k=1}^n\left\{n\atop k\right\}x^{\underline k}\tag{1}$$
for any $n\in\Bbb Z^+$. (The formula $(1)$ becomes valid for $n=0$ as well if you start the summation at $k=0$.)
The base case $n=1$ is clear, since $x^{\underline 1}=x$, and $\left\{n\atop k\right\}=1$. For the induction step you’ll the Pascal-like recurrence relation satisfied by the Stirling numbers of the second kind:
$$\left\{{n+1}\atop k\right\}=k\left\{n\atop k\right\}+\left\{n\atop{k-1}\right\}\;.$$ (If you’re not familiar with it, you’ll find a combinatorial proof here.) It’s also useful to note that $x^{\underline{k+1}}=x^{\underline k}(x-k)$, so $x\cdot x^{\underline k}=x^{\underline{k+1}}+kx^{\underline k}$.
Now assume $(1)$ for $n$, and try to prove that
$$x^{n+1}=\sum_{k=1}^{n+1}\left\{{n+1}\atop k\right\}x^{\underline k}\;.$$
Start out in the usual way:
$$\begin{align*}
x^{n+1}&=x\cdot x^n\\
&=x\sum_{k=1}^n\left\{n\atop k\right\}x^{\underline k}\\
&=\sum_{k=1}^n\left\{n\atop k\right\}x\cdot x^{\underline k}\\
&=\sum_{k=1}^n\left\{n\atop k\right\}\left(x^{\underline{k+1}}+kx^{\underline k}\right)\\
&=\sum_{k=1}^n\left\{n\atop k\right\}x^{\underline{k+1}}+\sum_{k=1}^n\left\{n\atop k\right\}kx^{\underline k}\\
&=\sum_{k=2}^{n+1}\left\{n\atop{k-1}\right\}x^{\underline k}+\sum_{k=1}^n\left\{n\atop k\right\}kx^{\underline k}&&\left(\text{shift index in first sum}\right)\\
&=\sum_{k=1}^{n+1}\left\{n\atop{k-1}\right\}x^{\underline k}+\sum_{k=1}^{n+1}\left\{n\atop k\right\}kx^{\underline k}&&\left(\text{since }\left\{n\atop0\right\}=0=\left\{n\atop{n+1}\right\}\right)\;.\\
\end{align*}$$
At this point you’re almost done; I’ll leave to you the little that remains.
