3
$\begingroup$

I'm looking for a combinatorial/probabilistic proof of this identity involving binomial coefficients :

$$ \displaystyle\sum_{k=n}^{2n} \binom{k}{n} \times \dfrac{1}{2^k} = 1 $$

My try : Multiplying both sides by $2^{2n}$ would render the identity as

$$ \displaystyle\sum_{i=0}^n \binom{n+i}{n}\times 2^{n-i} = 2^{2n}$$

That led me to trying to count the number of maps from a set consisting of $2n$ elements to a set of two elements in two ways but I haven't succeeded yet.

Could you please give it a try.

$\endgroup$
3
$\begingroup$

$$\binom{k}n\frac1{2^{k+1}}$$ is the probability that in a sequence of coin tosses, the $(n+1)$-th head is achieved on the $(k+1)$-th toss. Then $$\sum_{k=n}^{2n}\binom{k}n\frac1{2^{k+1}}$$ is the probability that at least $n+1$ heads occur in a sequence of $2n+1$ tosses, etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.