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 want to proove the following equality containing rising factorials

$$(x+y)^\overline{n}\overset{(*)}{=}\sum_{k=0}^n\binom{n}{k}x^\overline{k}y^\overline{n-k}.$$

For $n=1$ this equality is obviously correct. Now I tried to create the transition $n-1\rightarrow n$ this way

$$(x+y)^\overline{n}=(x+y)^\overline{n-1}+\underbrace{\binom{n}{n}x^\overline{n}y^\overline{n-n}}_{x^\overline{n}}$$ $$(x+y)^\overline{n}=\sum_{k=0}^{n-1}\binom{n-1}{k}x^\overline{k}y^\overline{n-k-1}+x^\overline{n}.$$

As I am not that familiar with binomials and such sums, can anyone explain me how transform this equality to achieve a representation like in $(*)$?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

The notation is a little neater if we do the induction step from $n$ to $n+1$ instead of from $n-1$ to $n$. My induction hypothesis is that for all $x$ and $y$, $$(x+y)^{\overline n} = \sum\limits_{k=0}^n \binom{n}{k}x^{\overline k}y^{\overline{n-k}}.$$

I want to show that for all $x$ and $y$, $$(x+y)^{\overline {n+1}} = \sum\limits_{k=0}^{n+1}\binom{n+1}{k}x^{\overline k}y^{\overline{n+1-k}}.$$

I’ll be using the fact that $u^{\overline {m+1}} = u(u+1)^{\overline m}$.

$$\begin{align*} \sum\limits_{k=0}^{n+1}\binom{n+1}{k}x^{\overline k}y^{\overline{n+1-k}} &= \sum\limits_{k=0}^n\binom{n+1}{k}x^{\overline k}y^{\overline{n+1-k}}+x^{\overline{n+1}}\tag{1}\\ &= \sum\limits_{k=0}^n \left(\binom{n}{k-1}+\binom{n}{k}\right)x^{\overline k}y^{\overline{n+1-k}}+x^{\overline{n+1}}\tag{2}\\ &= \sum\limits_{k=0}^n \binom{n}{k-1}x^{\overline k}y^{\overline{n+1-k}} + \sum\limits_{k=0}^n \binom{n}{k}x^{\overline k}y^{\overline{n+1-k}} + x^{\overline{n+1}}\\ &= \sum\limits_{k=0}^{n-1} \binom{n}{k}x^{\overline {k+1}}y^{\overline{n-k}} + \sum\limits_{k=0}^n \binom{n}{k}x^{\overline k}y^{\overline{n+1-k}} + x^{\overline{n+1}}\tag{3}\\ &= \sum\limits_{k=0}^n \binom{n}{k}x^{\overline {k+1}}y^{\overline{n-k}} + \sum\limits_{k=0}^n \binom{n}{k}x^{\overline k}y^{\overline{n+1-k}}\tag{4}\\ &= x \sum\limits_{k=0}^n \binom{n}{k} (x+1)^{\overline k}y^{\overline{n-k}} + y \sum\limits_{k=0}^n \binom{n}{k} x^{\overline k} (y+1)^{\overline {n-k}}\tag{5}\\ &= x(x+1+y)^{\overline n} + y(x+y+1)^{\overline n}\tag{6}\\ &= (x+y)(x+y+1)^{\overline n}\\ &= (x+y)^{\overline{n+1}} \end{align*}$$

At step $(1)$ I split off the last term of the sum. At step $(2)$ I used the basic binomial recursion. At step $(3)$ I did an index shift on the first sum: the $k=0$ term is $0$, so $k$ might as well run from $1$ to $n$ and can then be replaced by $k-1$, which runs from $0$ to $n-1$. At step $(4)$ I combined the separated term from step $(1)$ with the first summation. At step $(5)$ I used the fact mentioned just before the computation, and at step $(6)$ I applied the induction hypothesis. The rest is just algebra and again the fact mentioned before the computation.

share|improve this answer

For anyone who's interested, here's a way to prove the identity that doesn't use induction.

$$\sum_{k=0}^n\binom{n}{k}x^\overline{k}y^\overline{n-k} = n! \sum_{k=0}^n \frac{(-1)^k (-x)^{\underline{k}}}{k!} \frac{(-1)^{n-k}(-y)^{\underline{n-k}}}{(n-k)!}$$ $$= n! (-1)^n\sum_{k=0}^n \binom{-x}{k} \binom{-y}{n-k}$$ $$= n! (-1)^n\binom{-x-y}{n}$$ $$= n! (-1)^n\frac{(-x-y)^{\underline{n}}}{n!}$$ $$= (x+y)^{\overline{n}}$$ The first step converts rising powers to falling powers, the second uses the definition of the binomial coefficients for real-valued upper indexes, the third is the Chu-Vandermonde identity, and the rest is converting back to rising powers.

share|improve this answer
    
Interesting way of prooving this, however i have to do this via induction. Still thanks for sharing the idea. –  Christian Ivicevic Sep 17 '11 at 9:35
1  
@Christian: I knew you had to use induction. Sometimes other people reading the question are interested in different ways to prove the result, though, and I posted this proof for them as well. –  Mike Spivey Sep 17 '11 at 12:53

The raising factorial $x^\overline{n}$ can be obtained as $ \left. \left(- \frac{\mathrm{d}}{\mathrm{d} t} \right)^n t^{-x} \right|_{t=1}$.

Now, use $ \left(- \frac{\mathrm{d}}{\mathrm{d} t} \right)^n \left( f(t) g(t) \right) = \sum_{k=0}^n \binom{n}{k} \left[ \left(- \frac{\mathrm{d}}{\mathrm{d} t} \right)^k f(t) \right] \times \left[ \left(- \frac{\mathrm{d}}{\mathrm{d} t} \right)^{n-k} g(t) \right] $ and use it for $f(t) = t^{-x}$ and $g(t) = t^{-y}$.

share|improve this answer

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.