Post History

If Alice must've have classes on at least 2 days, why do you need the intersection of 3 $A_i^C$'s?

Please de-mystify André Nicolas's story proof of $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1$?

1. What spurred or goaded this change of variable? From starting at $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1$, I would've never prognosticated letting $k = n - i$! 



>[[Source](https://math.stackexchange.com/a/508962/949072)] 
 Things may be more clear if we let $k=n-i$. Then our sum (reversed) is
$$\sum_{i=0}^n \frac{\binom{n+i}{n}}{2^{n+i}}.$$

2. Again, I'm unschooled at algebra with Capital-Sigma Notation. $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}} \overset{\color{red}{k = n - i}}{\equiv} \sum_{\color{red}{i = n}}^{\color{red}{k+i}} \frac{\binom{\color{red}{n + i}}{n}}{2^{n+i}}  $. My bounds of summation don't match!

>Imagine tossing a fair coin until we get $n+1$ heads or $n+1$ tails.

3. How'd you concoct this story? What in $\sum_{i=0}^n \frac{\binom{n+i}{n}}{2^{n+i}}$ would galvanize you to "imagine tossing a fair coin until we get $n + 1$ heads or $n + 1$ tails"? Particularly because $n + 1$ never appears in the summation above!

>The number of tosses is $n+i+1$ if (i) we get exactly $n$ heads in the first $n+i$ tosses, and then a head, or (ii) we get $n$ tails in the first $n+i$ tosses and then a tail.

>The probability of (i) is $\frac{\binom{n+i}{n}}{2^{n+i}}\cdot \frac{1}{2}$, and the probability of (ii) is the same. **For sure the number of tosses will be one of $n+1$ to $2n+1$. [Boldface mine]**

4. I don't understand the last sentence in bold. How does it conclude the proof?