1
$\begingroup$

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?

  • 0
    C$h$eck out: http://math.stackexchange.com/questions/255743/need-help-with-simple-proof-by-mathematical-induction/255758#255758.2012-12-10

1 Answers 1

2

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.

  • 0
    @Nick: Glad to hear it; you’re very welcome.2012-12-13