Proving $\sum_{k=0}^{m}\binom{n+k}{k}(1-x)^kx^{n+1}=1-\sum_{k=0}^{n}\binom{m+k}{k}x^k(1-x)^{m+1}$ without calculus

Question

How would you prove this without calculus?

$$\forall m,n\in\Bbb N,\ \forall x\in\Bbb R,\ \sum_{k=0}^{m}\binom{n+k}{k}(1-x)^kx^{n+1}=1-\sum_{k=0}^{n}\binom{m+k}{k}x^k(1-x)^{m+1}$$

In this post it is proved with calculus, and I was wondering if there was an easier way to prove it. I tried proving it with induction, by holding $n$ constant, however I didn't seem to get anywhere.

Answer 1

We can give a probabilistic proof. First, assume that $0\le x\le 1$. Imagine that Alice and Bob repeatedly play games of chess. Each time, Alice wins with probability $x$, and Bob wins with probability $1-x$, independently of previous rounds. The pair stop playing as soon as Alice accumulates $n+1$ wins, or when Bob accumulates $m+1$ wins.

The probability that the series ends with Alice having $n+1$ wins, and Bob having $k$ wins for some $k\in \{0,\dots,m\}$, is $\binom{n+k}k x^{n+1}(1-x)^k$.

The factor of $\binom{n+k}{k}$ accounts for all ways to arrange Bob's $k$ wins among the first $n+k$ outcomes.

Similarly, the probability the series ends with $m+1$ wins for Bob and $k$ wins for Alice is $\binom{m+k}{k}(1-x)^{m+1}x^k$. Since we have exhausted all possible outcomes, the probabilities must add up to one. We have shown

$$ \sum_{k=0}^n\binom{n+k}k x^{n+1}(1-x)^k + \sum_{k=0}^m\binom{m+k}k(1-x)^{m+1}x^k=1 $$ completing the proof. Note that the LHS is a polynomial with degree at most $m+n+1$, so the fact that it is equal to $1$ for all $x$ in the interval $[0,1]$ implies it equals $1$ for all $x\in \mathbb C$.

Answer 2

Induction works.

Let

$$a(n,m)=x^{n+1}\sum_{k=0}^{m}\binom{n+k}{k}(1-x)^k$$ $$b(n,m)=(1-x)^{m+1}\sum_{k=0}^{n}\binom{m+k}{k}x^k$$ $$f(n,m)=a(n,m)+b(n,m)$$

So we have to prove $f(n,m)=1$ for all $n,m\ge0$.

Let's prove this by induction on $m$.

First, $f(n,0)=1$ for all $n\ge0$, as $a(n,0)=x^{n+1}$ and $b(n,0)=(1-x)\sum_{k=0}^nx^k=1-x^{n+1}$.

Below, $n\ge0$ is fixed.

Let's assume $f(n,m)=1$ for some $m\ge0$. Then:

$$a(n,m+1)=a(n,m)+x^{n+1}\binom{n+m+1}{m+1}(1-x)^{m+1}$$ $$b(n,m+1)=(1-x)^{m+2}\sum_{k=0}^n\binom{m+k+1}{k}x^k=(1-x)^{m+2}\left\{\sum_{k=0}^n\binom{m+k}{k}x^k+\sum_{k=1}^n\binom{m+k}{k-1}x^k\right\}\\=(1-x)(1-x)^{m+1}\sum_{k=0}^n\binom{m+k}{k}x^k+(1-x)^{m+2}\sum_{k=1}^n\binom{m+k}{k-1}x^k\\=(1-x)b(n,m)+(1-x)^{m+2}\sum_{k=0}^{n-1}\binom{m+k+1}{k}x^{k+1}$$

Therefore

$$f(n,m+1)=f(n,m)+(1-x)^{m+1}\left\{\binom{n+m+1}{m+1}x^{n+1}-x\sum_{k=0}^n\binom{m+k}{k}x^k+(1-x)\sum_{k=0}^{n-1}\binom{m+k+1}{k}x^{k+1}\right\}$$

We want to prove that the expression inside the curly brackets is zero:

$$\binom{n+m+1}{m+1}x^{n+1}-x\sum_{k=0}^n\binom{m+k}{k}x^k+(1-x)\sum_{k=0}^{n-1}\binom{m+k+1}{k}x^{k+1}\\=\sum_{k=0}^n\binom{m+k+1}{k}x^{k+1}-x\sum_{k=0}^n\binom{m+k}{k}x^k-x\sum_{k=0}^{n-1}\binom{m+k+1}{k}x^{k+1}\\ =\sum_{k=0}^n\binom{m+k+1}{k}x^{k+1}-x\sum_{k=0}^n\binom{m+k}{k}x^k-x\sum_{k=1}^{n}\binom{m+k}{k-1}x^{k}\\ =\sum_{k=0}^n\binom{m+k+1}{k}x^{k+1}-\sum_{k=0}^n\binom{m+k}{k}x^{k+1}-\sum_{k=1}^{n}\binom{m+k}{k-1}x^{k+1}\\ =x-x+\sum_{k=1}^n\left\{\binom{m+k+1}{k}-\binom{m+k}{k}-\binom{m+k}{k-1}\right\}x^{k+1}\\=0$$

Where the $x-x$ in the last line comes from the index $k=0$ in the first two sums of the preceding line.

Therefore the induction step is proved: if $f(n,m)=1$, then $f(n,m+1)=1$. And by induction, the equality is true for all $m\ge0$. Since this is proved for any $n\ge0$, the equality $f(n,m)=1$ is true for all $n,m\ge0$.