Counting, Probability and Binomial Coefficients

Question

If $$P_{2n+2}=\sum_{k=n+2}^{2n+2}{2n+2 \choose k}p^kq^{2n+2-k}$$

and,

$$P_{2n}=\sum_{k=n+1}^{2n}{2n \choose k}p^kq^{2n-k}$$

where $0<p<q<1$ and $q=1-p$

Prove that

$$P_{2n+2}=P_{2n}+{2n \choose n}p^{n+2}q^n-{2n \choose {n+1}}p^{n+1}q^{n+1}$$

$\mathbf {Inspiration:}$ A and B play a series of games where the probability of winning $\mathit p$ for A is kept less than 0.5. However A gets to choose in advance the total no. of plays. To win the game one must score more than half the games . If the total no. of games is to be even, How many plays should A choose?

$\mathbf {Here}$ $P_{2n}$ and $P_{2n+2}$ represents the probability of A winning the play in $2n$ and $2n+2$ games where $2n$ is considered the optimum number of games

Answer 1

The equality reduces to $$ \binom{2 n}{n+1} p^{n+1} (1-p)^{n-1} \, _2F_1\left(1,1-n;n+2;\frac{p}{p-1}\right)+\binom{2 n}{n} p^{n+2} (1-p)^n-\binom{2 n}{n+1} p^{n+1} (1-p)^{n+1}=\binom{2 (n+1)}{n+2} (1-p)^{-n+2 (n+1)-2} p^{n+2} \, _2F_1\left(1,-n;n+3;\frac{p}{p-1}\right) $$ Let $w=p/(1-p)$, then the above is $$ \binom{2 n}{n+1} \left((w+1)^2 \, _2F_1(1,1-n;n+2;-w)-1\right)+w \binom{2 n}{n}=w \binom{2 (n+1)}{n+2} \, _2F_1(1,-n;n+3;-w) $$ We can then extract the coefficient for $w^m$ from both side for $m \in \{0,\dots,n\}$ to see that this equality holds.

Answer 2

We consider $(p+q)^2P_{2n}$ instead of $P_{2n}$ (because then our identity will be homogeneous). Then, we will simply compare coefficents of monomials $p^kq^{2n+2-k}$ in both sides of identity.

Note that (from equality $p+q=1$) $$ P_{2n}=\sum_{k=n+1}^{2n}{2n \choose k}p^kq^{2n-k}=\sum_{k=n+1}^{2n}{2n \choose k}p^kq^{2n-k} (p+q)^2, $$ which equals $$ \sum_{k=n+1}^{2n}{2n \choose k}p^kq^{2n-k} (p^2+2pq+q^2)= \\ \sum_{k=n+1}^{2n}{2n \choose k}p^{k+2}q^{2n-k}+\sum_{k=n+1}^{2n}2{2n \choose k}p^{k+1}q^{2n-k+1}+\sum_{k=n+1}^{2n}{2n \choose k}p^{k}q^{2n-k+2}= \\ \sum_{k=n+3}^{2n+2}{2n \choose k-2}p^{k}q^{2n+2-k}+\sum_{k=n+2}^{2n+1}2{2n \choose k-1}p^{k}q^{2n+2-k}+\sum_{k=n+1}^{2n}{2n \choose k}p^{k}q^{2n-k+2}. $$

Therefore, $P_{2n}$ equals $$ \sum_{k=n+2}^{2n+2}\left({2n \choose k}+2{2n \choose k-1}+{2n \choose k-2}\right)p^kq^{2n+2-k}-\left({2n \choose n}p^{n+2}q^{n}-{2n \choose n+1}p^{n+1}q^{n+1}\right). $$

We also know that $$ {2n \choose k}+2{2n \choose k-1}+{2n \choose k-2}=\left({2n \choose k}+{2n \choose k-1}\right)+\left({2n \choose k-1}+{2n \choose k-2}\right)= \\ {2n+1 \choose k}+{2n+1 \choose k-1}={2n+2 \choose k}, $$ so we obtain $$ P_{2n}=\sum_{k=n+2}^{2n+2}{2n+2 \choose k}p^kq^{2n+2-k}=P_{2n+2}-\left({2n \choose n}p^{n+2}q^{n}-{2n \choose n+1}p^{n+1}q^{n+1}\right). $$ Hence, $$ P_{2n+2}=P_{2n}+{2n \choose n}p^{n+2}q^{n}-{2n \choose n+1}p^{n+1}q^{n+1}, $$ as desired.

Answer 3

Forget the requirement that $0<p<q<1$; it is unnecessary. So let $p$ and $q$ be any reals satisfying $p+q=1$.

Also, let me extend the stage a little bit:

Definition. Let $m$ and $n$ be integers such that $n\geq m\geq0$. Then, we let \begin{equation} Q_{n,m}=\sum_{k=m}^{n}\dbinom{n}{k}p^{k}q^{n-k}. \end{equation}

With this definition, your $P_{2n}$ is $Q_{2n,n+1}$, while your $P_{2n+2}$ is $Q_{2n+2,n+2}$. Thus, your claim becomes:

Theorem 1. Let $n$ be a nonnegative integer. Then, \begin{equation} Q_{2n+2,n+2}=Q_{2n,n+1}+\dbinom{2n}{n}p^{n+2}q^{n}-\dbinom{2n}{n+1} p^{n+1}q^{n+1}. \end{equation}

I shall derive this from the following:

Lemma 2. Let $m$ and $n$ be integers such that $n\geq m\geq1$. Then, \begin{equation} Q_{n,m}=Q_{n-1,m-1}-\dbinom{n-1}{m-1}p^{m-1}q^{n-m+1}. \end{equation}

Proof of Lemma 2. From $n\geq m\geq1$, we obtain $n-1\geq m-1\geq0$. Now, the definition of $Q_{n-1,m-1}$ yields \begin{equation} Q_{n-1,m-1}=\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}p^{k}\underbrace{q^{n-1-k} }_{=q^{n-k-1}}=\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}p^{k}q^{n-k-1}. \label{darij1.pf.l2.0} \tag{1} \end{equation}

But the definition of $Q_{n,m}$ yields \begin{align} Q_{n,m} & =\sum_{k=m}^{n}\underbrace{\dbinom{n}{k}}_{\substack{=\dbinom {n-1}{k-1}+\dbinom{n-1}{k}\\\text{(by the recurrence of the binomial coefficients)}}}p^{k}q^{n-k}=\sum_{k=m}^{n}\left( \dbinom{n-1}{k-1} +\dbinom{n-1}{k}\right) p^{k}q^{n-k}\nonumber\\ & =\sum_{k=m}^{n}\dbinom{n-1}{k-1}p^{k}q^{n-k}+\sum_{k=m}^{n}\dbinom{n-1} {k}p^{k}q^{n-k}\nonumber\\ & =\sum_{k=m-1}^{n-1}\underbrace{\dbinom{n-1}{\left( k+1\right) -1} }_{=\dbinom{n-1}{k}}p^{k+1}\underbrace{q^{n-\left( k+1\right) }} _{=q^{n-k-1}}+\sum_{k=m}^{n}\dbinom{n-1}{k}p^{k}q^{n-k}\nonumber\\ & \qquad\left( \text{here, we have substituted }k+1\text{ for }k\text{ in the first sum}\right) \nonumber\\ & =\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}p^{k+1}q^{n-k-1}+\sum_{k=m}^{n} \dbinom{n-1}{k}p^{k}q^{n-k}. \label{darij1.pf.l2.1} \tag{2} \end{align}

But we have \begin{equation} \sum_{k=m-1}^{n}\dbinom{n-1}{k}p^{k}q^{n-k}=\sum_{k=m}^{n}\dbinom{n-1}{k} p^{k}q^{n-k}+\dbinom{n-1}{m-1}p^{m-1}q^{n-\left( m-1\right) } \end{equation} and \begin{align*} \sum_{k=m-1}^{n}\dbinom{n-1}{k}p^{k}q^{n-k} & =\sum_{k=m-1}^{n-1}\dbinom {n-1}{k}p^{k}q^{n-k}+\underbrace{\dbinom{n-1}{n}}_{\substack{=0\\\text{(since }n-1\geq0\text{ and }n-1<n\text{)}}}p^{n}q^{n-n}\\ & =\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}p^{k}q^{n-k}. \end{align*} Comparing these two equalities, we obtain \begin{equation} \sum_{k=m}^{n}\dbinom{n-1}{k}p^{k}q^{n-k}+\dbinom{n-1}{m-1}p^{m-1}q^{n-\left( m-1\right) }=\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}p^{k}q^{n-k}. \end{equation} Thus, \begin{equation} \sum_{k=m}^{n}\dbinom{n-1}{k}p^{k}q^{n-k}=\sum_{k=m-1}^{n-1}\dbinom{n-1} {k}p^{k}q^{n-k}-\dbinom{n-1}{m-1}p^{m-1}q^{n-\left( m-1\right) }. \end{equation} Hence, \eqref{darij1.pf.l2.1} becomes \begin{align*} Q_{n,m} & =\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}p^{k+1}q^{n-k-1}+\underbrace{\sum _{k=m}^{n}\dbinom{n-1}{k}p^{k}q^{n-k}}_{=\sum_{k=m-1}^{n-1}\dbinom{n-1} {k}p^{k}q^{n-k}-\dbinom{n-1}{m-1}p^{m-1}q^{n-\left( m-1\right) }}\\ & =\underbrace{\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}p^{k+1}q^{n-k-1}+\sum _{k=m-1}^{n-1}\dbinom{n-1}{k}p^{k}q^{n-k}}_{=\sum_{k=m-1}^{n-1}\dbinom{n-1} {k}\left( p^{k+1}q^{n-k-1}+p^{k}q^{n-k}\right) }-\dbinom{n-1}{m-1} p^{m-1}\underbrace{q^{n-\left( m-1\right) }}_{=q^{n-m+1}}\\ & =\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}\left( \underbrace{p^{k+1}}_{=pp^{k} }q^{n-k-1}+p^{k}\underbrace{q^{n-k}}_{=qq^{n-k-1}}\right) -\dbinom{n-1} {m-1}p^{m-1}q^{n-m+1}\\ & =\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}\underbrace{\left( pp^{k}q^{n-k-1} +p^{k}qq^{n-k-1}\right) }_{\substack{=\left( p+q\right) p^{k} q^{n-k-1}=p^{k}q^{n-k-1}\\\text{(since }p+q=1\text{)}}}-\dbinom{n-1} {m-1}p^{m-1}q^{n-m+1}\\ & =\underbrace{\sum_{k=m-1}^{n-1}\dbinom{n-1}{k}p^{k}q^{n-k-1}} _{\substack{=Q_{n-1,m-1}\\\text{(by \eqref{darij1.pf.l2.0})}}}-\dbinom {n-1}{m-1}p^{m-1}q^{n-m+1}\\ & =Q_{n-1,m-1}-\dbinom{n-1}{m-1}p^{m-1}q^{n-m+1}. \end{align*} This proves Lemma 2. $\blacksquare$

Proof of Theorem 1. We have $\left( 1-q-pq\right) -p^{2}=-\left( p+1\right) \underbrace{\left( p+q-1\right) }_{\substack{=0\\\text{(since }p+q=1\text{)}}}=0$, thus $1-q-pq=p^{2}$.

Lemma 2 (applied to $2n+2$ and $n+2$ instead of $n$ and $m$) yields \begin{align} Q_{2n+2,n+2} & =\underbrace{Q_{2n+1,n+1}}_{\substack{=Q_{2n,n}-\dbinom{2n} {n}p^{n}q^{\left( 2n+1\right) -\left( n+1\right) +1}\\\text{(by Lemma 2, applied to }2n+1\text{ and }n+1\\\text{instead of }n\text{ and }m\text{)} }}-\underbrace{\dbinom{2n+1}{n+1}}_{\substack{=\dbinom{2n}{n}+\dbinom{2n} {n+1}\\\text{(by the recurrence of the binomial coefficients)}}}p^{n+1} \underbrace{q^{\left( 2n+2\right) -\left( n+2\right) +1}}_{=q^{n+1} }\nonumber\\ & =Q_{2n,n}-\dbinom{2n}{n}p^{n}\underbrace{q^{\left( 2n+1\right) -\left( n+1\right) +1}}_{=q^{n+1}}-\underbrace{\left( \dbinom{2n}{n}+\dbinom {2n}{n+1}\right) p^{n+1}q^{n+1}}_{=\dbinom{2n}{n}p^{n+1}q^{n+1}+\dbinom {2n}{n+1}p^{n+1}q^{n+1}}\nonumber\\ & =Q_{2n,n}-\dbinom{2n}{n}p^{n}q^{n+1}-\left( \dbinom{2n}{n}p^{n+1} q^{n+1}+\dbinom{2n}{n+1}p^{n+1}q^{n+1}\right) \nonumber\\ & =Q_{2n,n}-\dbinom{2n}{n}p^{n}q^{n+1}-\dbinom{2n}{n}p^{n+1}q^{n+1} -\dbinom{2n}{n+1}p^{n+1}q^{n+1}. \label{darij1.pf.t1.1} \tag{3} \end{align} But the definition of $Q_{2n,n+1}$ yields $Q_{2n,n+1}=\sum_{k=n+1}^{2n} \dbinom{2n}{k}p^{k}q^{2n-k}$. Meanwhile, the definition of $Q_{2n,n}$ yields \begin{align*} Q_{2n,n} & =\sum_{k=n}^{2n}\dbinom{2n}{k}p^{k}q^{2n-k}=\underbrace{\sum _{k=n+1}^{2n}\dbinom{2n}{k}p^{k}q^{2n-k}}_{=Q_{2n,n+1}}+\dbinom{2n}{n} p^{n}\underbrace{q^{2n-n}}_{=q^{n}}\\ & =Q_{2n,n+1}+\dbinom{2n}{n}p^{n}q^{n}. \end{align*} Thus, \eqref{darij1.pf.t1.1} becomes \begin{align*} Q_{2n+2,n+2} & =\underbrace{Q_{2n,n}}_{=Q_{2n,n+1}+\dbinom{2n}{n}p^{n}q^{n} }-\dbinom{2n}{n}p^{n}q^{n+1}-\dbinom{2n}{n}p^{n+1}q^{n+1}-\dbinom{2n} {n+1}p^{n+1}q^{n+1}\\ & =Q_{2n,n+1}+\dbinom{2n}{n}p^{n}q^{n}-\dbinom{2n}{n}p^{n}q^{n+1}-\dbinom {2n}{n}p^{n+1}q^{n+1}-\dbinom{2n}{n+1}p^{n+1}q^{n+1}\\ & =Q_{2n,n+1}+\dbinom{2n}{n}\underbrace{\left( p^{n}q^{n}-p^{n} q^{n+1}-p^{n+1}q^{n+1}\right) }_{=\left( 1-q-pq\right) p^{n}q^{n}} -\dbinom{2n}{n+1}p^{n+1}q^{n+1}\\ & =Q_{2n,n+1}+\dbinom{2n}{n}\underbrace{\left( 1-q-pq\right) }_{=p^{2}} p^{n}q^{n}-\dbinom{2n}{n+1}p^{n+1}q^{n+1}\\ & =Q_{2n,n+1}+\dbinom{2n}{n}\underbrace{p^{2}p^{n}}_{=p^{n+2}}q^{n} -\dbinom{2n}{n+1}p^{n+1}q^{n+1}\\ & =Q_{2n,n+1}+\dbinom{2n}{n}p^{n+2}q^{n}-\dbinom{2n}{n+1}p^{n+1}q^{n+1}. \end{align*} This proves Theorem 1. $\blacksquare$

Answer 4

We have for the first sum

$$S = \sum_{k=0}^n {2n+2\choose k+n+2} p^{k+n+2} q^{n-k}$$

and for the second one

$$T = \sum_{k=0}^{n-1} {2n\choose k+n+1} p^{k+n+1} q^{n-1-k}$$

and seek to show

$$S-T = {2n\choose n} p^{n+2} q^n - {2n\choose n+1} p^{n+1} q^{n+1}$$

where $p+q=1.$ We see that with

$$Q_n = \sum_{k=0}^n {2n+2\choose k+n+2} p^{k+n+2} q^{n-k}$$

the claim becomes

$$Q_n - Q_{n-1} = {2n\choose n} p^{n+2} q^n - {2n\choose n+1} p^{n+1} q^{n+1}.$$

Now

$$Q_n = p^{n+2} q^n \sum_{k=0}^n {2n+2\choose k+n+2} p^{k} q^{-k} = p^{n+2} q^n \sum_{k=0}^n {2n+2\choose n-k} p^{k} q^{-k} \\ = p^{n+2} q^n \sum_{k=0}^n p^{k} q^{-k} [z^{n-k}] (1+z)^{2n+2} = p^{n+2} q^n [z^n] (1+z)^{2n+2} \sum_{k=0}^n p^{k} q^{-k} z^k.$$

We may extend $k$ beyond $n$ owing to the coefficient extrator $[z^n]$ in front:

$$p^{n+2} q^n [z^n] (1+z)^{2n+2} \sum_{k\ge 0} p^{k} q^{-k} z^k = p^{n+2} q^n [z^n] (1+z)^{2n+2} \frac{1}{1-pz/q} \\ = p^2 [z^n] (1+pqz)^{2n+2} \frac{1}{1-p^2z}.$$

We thus have

$$Q_{n-1} = p^2 [z^{n-1}] (1+pqz)^{2n} \frac{1}{1-p^2z} \\ = p^2 [z^n] z (1+pqz)^{2n} \frac{1}{1-p^2z}.$$

Subtracting we find

$$Q_n - Q_{n-1} = p^2 [z^n] ((1+pqz)^2-z) (1+pqz)^{2n} \frac{1}{1-p^2z} \\ = p^2 [z^n] (1-p^2 z) (1-q^2 z) (1+pqz)^{2n} \frac{1}{1-p^2z} \\ = p^2 [z^n] (1-q^2 z) (1+pqz)^{2n} \\ = p^2 [z^n] (1+pqz)^{2n} - p^2 [z^n] q^2 z (1+pqz)^{2n} \\ = p^2 p^n q^n {2n\choose n} - p^2 q^2 [z^{n-1}] (1+pqz)^{2n} \\ = p^{n+2} q^n {2n\choose n} - p^2 q^2 p^{n-1} q^{n-1} {2n\choose n-1}.$$

This is indeed

$$\bbox[5px,border:2px solid #00A000]{ p^{n+2} q^n {2n\choose n} - p^{n+1} q^{n+1} {2n\choose n+1}}$$

as claimed.

Remark. It might be simpler not to merge the $p^n q^n$ into the coefficient extractor. Further commentary TBA.