Proof of a Binomial expression summation

Question

Let $x,y$ be probabilities and $n$ is some integer. Show that:

$\displaystyle \sum_{n_0=1}^n \sum_{m=0}^{min(n_0-1,n-n_0-1)} \binom{n_0-1}{m}\binom{n-n_0-1}{m}x^m(1-x)^{n_0-m-1}y^m(1-y)^{n-n_0-m-1} = \frac{1-(1-x-y)^{n-1}}{x+y} $

I reached this statement from some Markov chain related arguments, but am wondering if there is a mathematical way using binomial properties to prove this. There seems to be some nice symmetry and structure to this expression and I feel that this can be exploited.

Answer 1

This is an answer to cover the special case $x=y$. At first we adapt the indices somewhat for convenience only. Setting $n_0\to N$ and $m\to k$ OPs claim is \begin{align*} &\sum_{n=1}^{N-1}\sum_{k=0}^{n-1}\binom{n-1}{k}\binom{N-n-1}{k}x^k(1-x)^{n-k-1}y^k(1-y)^{N-n-k-1}=\frac{1-(1-(x+y))^{N-1}}{x+y} \end{align*} where we set the upper limit of the leftmost sum to $N-1$ since the summand with $n=N$ is zero. We shift the index $n$ to start with $n=0$ and we substitute $N$ with $N+2$ which results in \begin{align*} \sum_{n=0}^{N}\sum_{k=0}^{n}\binom{n}{k}\binom{N-n}{k}x^k(1-x)^{n-k}y^k(1-y)^{N-n-k}=\frac{1-(1-(x+y))^{N+1}}{x+y}\tag{1} \end{align*}

We show the special case $x=y$ of (1) is valid and prove \begin{align*} \color{blue}{\sum_{n=0}^{N}\sum_{k=0}^{n}\binom{n}{k}\binom{N-n}{k}x^{2k}(1-x)^{N-2k}=\frac{1-(1-2x)^{N+1}}{2x}}\tag{2} \end{align*}

We use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write for instance \begin{align*} [x^k](1+x)^N=\binom{N}{k} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{n=0}^{N}}&\color{blue}{\sum_{k=0}^{n}\binom{n}{k}\binom{N-n}{k}x^{2k}(1-x)^{N-2k}}\\ &=(1-x)^N\sum_{n=0}^N\sum_{k=0}^n\binom{n}{k}[z^k](1+z)^{N-n}\left(\frac{x}{1-x}\right)^{2k}\tag{3}\\ &=(1-x)^N[z^0]\sum_{n=0}^N(1+z)^{N-n}\sum_{k=0}^n\binom{n}{k}\left(\frac{x}{1-x}\right)^{2k}\frac{1}{z^k}\tag{4}\\ &=(1-x)^N[z^0]\sum_{n=0}^N(1+z)^{N-n}\left(1+\left(\frac{x}{1-x}\right)^{2}\frac{1}{z}\right)^n\tag{5}\\ &=(1-x)^N[z^0](1+z)^N\sum_{n=0}^N\left(z(1+z)\right)^{-n}\left(z+\left(\frac{x}{1-x}\right)^{2}\right)^n\\ &=(1-x)^N[z^0](1+z)^N\frac{\left(\frac{z+\left(\frac{x}{1-x}\right)^2}{z(1+z)}\right)^{N+1}-1}{\frac{z+\left(\frac{x}{1-x}\right)^2}{z(1+z)}-1}\tag{6}\\ &=(1-x)^N[z^N]\frac{\left(z+\left(\frac{x}{1-x}\right)^2\right)^{N+1}-(z(1+z))^{N+1}}{\left(z+\left(\frac{x}{1-x}\right)^2\right)-z(1+z)}\\ &=(1-x)^N[z^N]\frac{\left(z+\left(\frac{x}{1-x}\right)^2\right)^{N+1}}{\left(\frac{x}{1-x}\right)^2-z^2}\tag{7}\\ &=(1-x)^N[z^N]\sum_{k=0}^{N+1}\binom{N+1}{k}\left(\frac{x}{1-x}\right)^{2k}z^{N+1-k}\cdot\frac{1}{\left(\frac{x}{1-x}\right)^2-z^2}\tag{8}\\ &=(1-x)^N\sum_{k=1}^{N+1}\binom{N+1}{k}\left(\frac{x}{1-x}\right)^{2k-2}[z^{k-1}]\cdot\frac{1}{1-\left(\frac{1-x}{x}\right)^2z^2}\\ &=(1-x)^N\sum_{k=0}^{N}\binom{N+1}{k+1}\left(\frac{x}{1-x}\right)^{2k}[z^{k}]\sum_{j=0}^\infty\left(\frac{1-x}{x}\right)^{2j}z^{2j}\tag{9}\\ &=(1-x)^N\sum_{k=0}^{\lfloor (N+1)/2\rfloor}\binom{N+1}{2k+1}\left(\frac{x}{1-x}\right)^{2k}\tag{10}\\ &=\frac{(1-x)^{N+1}}{x}\sum_{k=1}^{\lfloor (N+1)/2\rfloor}\binom{N+1}{2k+1}\left(\frac{x}{1-x}\right)^{2k+1}\\ &=\frac{(1-x)^{N+1}}{2x}\sum_{k=0}^{N+1}\binom{N+1}{k}\left(\frac{x}{1-x}\right)^{k}(1-(-1)^k)\\ &=\frac{(1-x)^{N+1}}{2x}\left(\left(1+\frac{x}{1-x}\right)^{N+1}-\left(1-\frac{x}{1-x}\right)^{N+1}\right)\tag{11}\\ &\,\,\color{blue}{=\frac{1-(1-2x)^{N+1}}{2x}} \end{align*} and the claim (2) follows.

Comment:

• In (3) we apply the coefficient of operator to $\binom{N-n}{k}$.

• In (4) we use the linearity of the coefficient of operator and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

• In (5) we apply the binomial theorem.

• In (6) we use the geometric series expansion.

• In (7) we skip the term $(z(1+z))^{N+1}$ which does not contribute to $[z^N]$.

• In (8) we apply the binomial theorem again.

• In (9) we shift the index $k$ by one and do a geometric series expansion.

• In (10) we have to select the coefficient of $z^k$ and since we have even powers $x^{2j}$ we replace $k$ with $2k$.

• In (11) after applying the binomial theorem a third time we see the nice identities \begin{align*} (1-x)\left(1+\frac{x}{1-x}\right)&=1\\ (1-x)\left(1-\frac{x}{1-x}\right)&=1-2x \end{align*}