2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.