Inductive proof for the Binomial Theorem for rising factorials

Question

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 $(*)$?

Answer 1

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.

Answer 2

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}$.

Answer 3

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.