Probabilistic interpretation. Prove that $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^n$

Question

Prove that $\sum_{k=0}^{n} \binom{n+k}{k} \frac{1}{2^k} = 2^n$

Well, the solution given on the book is as follows:

We will solve this counting problem by a powerful and elegant interpretation of the result. First we divide the identity by $2^n$, getting $$ \sum_{k=0}^{n} \binom{n+k}{k} \frac{1}{2^{n+k}} = \sum_{k=0}^{n} p_k = 1. $$ This is the sum of probabilities $p_k = \binom{n+k}{k} \frac{1}{2^{n+k}}$. Now, $$ p_k = \frac{1}{2}\binom{n+k}{k} \frac{1}{2^{n+k}} + \frac{1}{2}\binom{n+k}{k} \frac{1}{2^{n+k}} = \mathbb{P}(A_k) + \mathbb{P}(B_k),$$ with the events \begin{align*} A_k &= \{\text{$(n+1)$ times head and $k$ times tail}\}, \\ B_k &= \{\text{$(n+1)$ times tail and $k$ times head}\}. \end{align*}

However, I am not getting the way to calculate the probabilities of $A_k$ and $B_k$. I mean, how did we arrive at the conclusion that $\mathbb{P}(A_k) = \frac{1}{2}\binom{n+k}{k} \frac{1}{2^{n+k}}$ and $\mathbb{P}(B_k) = \frac{1}{2}\binom{n+k}{k} \frac{1}{2^{n+k}}$. I mean, how to calculate those probabilities?

Answer 1

I'm not sure why splitting this into two events is necessary. One can say $p_k = P(A_k)$ where $A_k$ is the event of flipping a fair coin $n+k$ times and getting exactly $k$ tails. Then if we imagine a sequence of $H$s and $T$s as the outcomes of the flips then we want $k$ spots of the $n+k$ spots as $T$. This occurs in $\binom{n+k}{k}$ ways. And each outcome has probability $1/2$ so $p_k = \binom{n+k}{k}(1/2^{n+k})$.

This also tells us that the $A_k$ and $B_k$ defined in the solution have probability $\binom{n+k+1}{k}(1/2^{n+k+1})$ which is off by a factor of $n+k+1$ from what we need.

Answer 2

In fact, it's necessary to split it into two events.

I reference the original solution in page97 https://mathematicalolympiads.files.wordpress.com/2012/08/75427434-problem-books-in-mathematics-problem-solving-strategies.pdf

What inspired me is Fig.5.12 in the original solution.

See Fig. 5.12, which shows the corresponding $2n + 2$ paths starting in O and ending up in one of the $2n+2$ endpoints, $n+1$ vertical and $n+1$ horizontal ones. Here, we used the standard interpretation: heads → one step upward, tails → one step to the right.

Imaging we start from $(0,0)$, and end up in one of the $2n+2$ points.

The key is: the sum of probability of end up in the $2n+2$ points is pbviously $1$.

In fact $A_k$=we finally reach the k-th(from left to right) points in the top of the image.

And similarly $B_k$=we finally reach the k-th(from down to up) points in the right of the image.

Now I explain why $P(A_k)=\frac{1}{2}\tbinom{n+k}{k}\frac{1}{2^{n+k}}$

How can we get $A_k$? It needs two steps.

Step1: we must reach point$(k,n)$. Step2: the last move must be upward.

the probability of step1 is $\tbinom{n+k}{k}\frac{1}{2^{n+k}}$, and the probability of step2 is $\frac{1}{2}$

Thus $P(A_k)=\frac{1}{2}\tbinom{n+k}{k}\frac{1}{2^{n+k}}$

The similar analysis for $B_k$.

So I think the defination of $A_k$ and$B_k$ should be changed into:

$A_k$={$n$ times head and $k$ times tail and the last flip must be head.}

$B_k$={$k$ times head and $n$ times tail and the last flip must be tail.}

Answer 3

We toss a fair coin until we get a total of $n+1$ heads or $n+1$ tails, whichever comes first. Say we get $n+1$ heads first, but along the way we also get $k$ tails ($k\leq n$) so the total number of tosses is $n+k+1$. The last toss must be head since we stop tossing after the $n+1$-th head. So we only need to figure out the number of possibility to get $k$ tails from the first $n+k$ tosses, which is $\binom{n+k}{k}$. Divide by the number of all possible outcomes from $n+k+1$ tosses, which is $2^{n+k+1}$ to obtain the probability $\frac{1}{2^{n+k+1}}\binom{n+k}{k}$