Mfrhtyj

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.

This is an answer to cover the special case $x=y$. At first we adapt the indices somewhat for convenience only. Setting $n_0to N$ and $mto 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)^Nsum_{n=0}^Nsum_{k=0}^nbinom{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}^nbinom{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)^ntag{5}\
&=(1-x)^N[z^0](1+z)^Nsum_{n=0}^Nleft(z(1+z)right)^{-n}left(z+left(frac{x}{1-x}right)^{2}right)^n\
&=(1-x)^N[z^0](1+z)^Nfrac{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)^2right)^{N+1}-(z(1+z))^{N+1}}{left(z+left(frac{x}{1-x}right)^2right)-z(1+z)}\
&=(1-x)^N[z^N]frac{left(z+left(frac{x}{1-x}right)^2right)^{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}cdotfrac{1}{left(frac{x}{1-x}right)^2-z^2}tag{8}\
&=(1-x)^Nsum_{k=1}^{N+1}binom{N+1}{k}left(frac{x}{1-x}right)^{2k-2}[z^{k-1}]cdotfrac{1}{1-left(frac{1-x}{x}right)^2z^2}\
&=(1-x)^Nsum_{k=0}^{N}binom{N+1}{k+1}left(frac{x}{1-x}right)^{2k}[z^{k}]sum_{j=0}^inftyleft(frac{1-x}{x}right)^{2j}z^{2j}tag{9}\
&=(1-x)^Nsum_{k=0}^{lfloor (N+1)/2rfloor}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)/2rfloor}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*}