Determine the value of $\displaystyle \sum_{k=n}^{2n} \binom{k} {n} 2^{-k}$ for $n \geq 1$

My attempt: I have asked this question before in another math forum but it leads no solution. My friend suggested me to search for something like series-k. I also looked at my textbook in combinatoric section (which apparently leads to Binomial Theorem), but really I don't have any idea for this one. Could you help me?


Let's start with the famous identity known from Pascal's triangle, $$\binom{k}{n}=\binom{k-1}{n-1}+\binom{k-1}{n}.$$ It's valid for all $k$ and $n$, if we assume $\binom{k}{n}=0$ for $n>k$ or $n<0$. So we can define our sum as $$s_n=\sum_{k\le2n}\binom{k}{n}2^{-k}=\sum_{k\le2n}\binom{k-1}{n-1}2^{-k}+\sum_{k\le2n}\binom{k-1}{n}2^{-k}$$ Obviously, we can rewrite the RHS as $$\frac12\sum_{k\le2n}\binom{k-1}{n-1}2^{-k+1}+\frac12\sum_{k\le2n}\binom{k-1}{n}2^{-k+1},$$ and with a translation of the summation index, this becomes $$\frac12\sum_{k\le2n-1}\binom{k}{n-1}2^{-k}+\frac12\sum_{k\le2n-1}\binom{k}{n}2^{-k}.$$ The sums on the RHS can be expressed by $s_{n-1}$ and $s_n$, so we obtain $$\frac12\,s_{n-1}+\binom{2n-1}{n-1}2^{-2n}+\frac12\,s_n-\binom{2n}{n}2^{-2n-1}=\frac12\,s_{n-1}+\frac12\,s_n$$ because of $$\binom{2n}{n}=\binom{2n-1}{n-1}+\binom{2n-1}{n}=2\binom{2n-1}{n-1}.$$ But this implies $s_n=s_{n-1}$, and the final result is $$s_n=s_1=\binom{1}{1}2^{-1}+\binom{2}{1}2^{-2}=1.$$


This answer is based upon the Lagrange inversion formula. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^n]\frac{1}{1-2z}=[z^n]\sum_{j=0}^\infty 2^jz^j=2^n \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=n}^{2n}\binom{k}{n}2^{-k}} &=\sum_{k=0}^n\binom{n+k}{k}2^{-n-k}\tag{1}\\ &=\frac{1}{2^n}\sum_{k=0}^n\binom{-n-1}{k}\left(-\frac{1}{2}\right)^k\tag{2}\\ &=\frac{1}{2^n}[z^n]\frac{1}{\left(1-\frac{z}{2}\right)^{n+1}(1-z)}\tag{3}\\ &=\frac{1}{2^n}[z^n]\left.\left(\frac{1}{\left(1-\frac{w}{2}\right)(1-w)}\cdot\frac{1}{1-\frac{w}{2}\cdot\frac{1}{1-\frac{w}{2}}}\right)\right|_{w=\frac{z}{1-\frac{w}{2}}}\tag{4}\\ &=\frac{1}{2^n}[z^n]\left.\frac{1}{(1-w)^2}\right|_{w=1-\sqrt{1-2z}}\tag{5}\\ &=\frac{1}{2^n}[z^n]\frac{1}{1-2z}\\ &\color{blue}{=1} \end{align*}


  • In (1) we shift the index $k$ to start with $k=0$.

  • In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ and $\binom{p}{q}=\binom{p}{p-q}$.

  • In (3) we observe the sum is the coefficient of the convolution of two series \begin{align*} [z^n]\left(\sum_{k}a_kz^k\right)\left(\sum_{l}b_lz^l\right)=[z^n]\sum_{N}\left(\sum_{k=0}^Na_k b_{N-k}\right)z^N =\sum_{k=0}^na_k b_{n-k} \end{align*} Here with $a_k=\binom{-n-1}{k}\left(-\frac{1}{2}\right)^k$ and $b_k=1$.

  • In (4) we use the Lagrange Inversion Formula in the form G6 stated in R. Sprugnolis (etal) paper Lagrange Inversion: when and how.

\begin{align*} [z^n]F(z)\Phi(z)^n=[z^n]\left.\frac{F(w)}{1-z\Phi'(w)}\right|_{w=z\Phi(w)} \end{align*}

Here with $\Phi(z)=\frac{1}{1-\frac{z}{2}}$ and $F(z)=\frac{1}{\left(1-\frac{z}{2}\right)(1-z)}$. It follows since $w=z\Phi(w)$: \begin{align*} z\Phi^{\prime}(w)=\frac{z}{2}\cdot\frac{1}{\left(1-\frac{w}{2}\right)^2} =\frac{z}{2}\Phi^2(w)=\frac{w}{2}\Phi(w)=\frac{w}{2}\cdot\frac{1}{1-\frac{w}{2}} \end{align*}

  • In (5) we simplify the expression and we select the solution $w=w(z)$ from $w=\frac{z}{1-\frac{w}{2}}$ which can be expanded in a power series.

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.