Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to proove the following equality containing rising factorials


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|cite|improve this question
up vote 6 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|cite|improve this answer

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|cite|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|cite|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
@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

Your Answer


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.