<s>[INST] Probabilistic interpretation. Prove that $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^n$ 
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?
 [/INST] 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}$
</s>