# Proof by induction for Stirling Numbers

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?

-
Check out: math.stackexchange.com/questions/255743/…. –  ashley Dec 10 '12 at 20:39

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.

-
Is it: $$x^{n+1}=\sum_{k=1}^{n+1}\left\{n+1\atop{k}\right\}x^{\underline k}$$ –  Nick Dec 13 '12 at 21:25
@Nick: Yes, the last step is to use the Stirling recurrence to combine the sums, getting the one that we wanted. That was why the previous step was an index shift: it gave the same falling power of $x$ in each summation, so that they could be combined. –  Brian M. Scott Dec 13 '12 at 21:34
Thanks! You're answer was very helpful! –  Nick Dec 13 '12 at 22:13
@Nick: Glad to hear it; you’re very welcome. –  Brian M. Scott Dec 13 '12 at 22:14