Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Check out: math.stackexchange.com/questions/255743/…. –  ashley Dec 10 '12 at 20:39

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.