0
$\begingroup$

Numerical analysis shows that the following identity is true for $k \geq 0$. $$\sum_{n=k}^{\infty} {n\choose k}\frac{1}{2^n} = 2. $$

However, I cannot seem to find a proof of this well-known result.

$\endgroup$
3
  • $\begingroup$ Have you searched on approach0.xyz ? $\endgroup$
    – Martin R
    Jul 12, 2019 at 10:37
  • $\begingroup$ @MartinR I've never used it before, but I was able to find a proof! Thanks! I would still appreciate a source with a list of identities that contains this particular one just for reference, if you happen to know of any. $\endgroup$
    – ignoramus
    Jul 12, 2019 at 10:44
  • $\begingroup$ Also: math.stackexchange.com/q/2832668/42969. $\endgroup$
    – Martin R
    Jul 12, 2019 at 11:02

2 Answers 2

5
$\begingroup$

Under the convention that $\binom{n}{k}=0$ if $k\notin\left\{ 0,1,\dots,n\right\} $ we find by means of the triangle of Pascal:

$$\begin{aligned}\sum_{n=k+1}^{\infty}\binom{n}{k+1}\frac{1}{2^{n}} & =\sum_{n=k+1}^{\infty}\binom{n-1}{k}\frac{1}{2^{n}}+\sum_{n=k+1}^{\infty}\binom{n-1}{k+1}\frac{1}{2^{n}}\\ & =\frac{1}{2}\sum_{n=k}^{\infty}\binom{n}{k}\frac{1}{2^{n}}+\frac{1}{2}\sum_{n=k+1}^{\infty}\binom{n}{k+1}\frac{1}{2^{n}} \end{aligned} $$

Implying that: $$\sum_{n=k+1}^{\infty}\binom{n}{k+1}\frac{1}{2^{n}}=\sum_{n=k}^{\infty}\binom{n}{k}\frac{1}{2^{n}}$$

This makes it easy to prove by induction on $k$ that: $$\sum_{n=k}^{\infty}\binom{n}{k}\frac{1}{2^{n}}=\sum_{n=0}^{\infty}\binom{n}{0}\frac{1}{2^{n}}=\sum_{n=0}^{\infty}\frac{1}{2^{n}}=2$$

$\endgroup$
2
  • $\begingroup$ Very slick, thanks! Would you also happen to know of any reference that contains this particular identity? $\endgroup$
    – ignoramus
    Jul 12, 2019 at 10:49
  • 1
    $\begingroup$ No, sorry. On that point I am "ignoramus" ;-) $\endgroup$
    – drhab
    Jul 12, 2019 at 10:51
1
$\begingroup$

Another proof:

Let us use $${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$$ Let $$f_k=\sum_{n=k}^{\infty} {n \choose k} \frac{1}{2^n}= \sum_{n=k}^{\infty} {n-1 \choose k}\frac{1}{2^n}+\sum_{n=k}^{\infty} {n-1 \choose k-1} \frac{1}{2^n}.$$ Let $n-1=p$, then $$\Rightarrow f_k=\sum_{p=k-1}^{\infty} {p\choose k} \frac{1}{2^{p+1}}+\sum_{p=k-1} {p\choose k-1}\frac{1}{2^{p+1}}$$ $$\Rightarrow f_k=\left(\sum_{p=k}^{\infty} {p\choose k} \frac{1}{2^{p+1}} + {k-1 \choose k}\frac{1}{2^{k}}\right)+\frac{f_{k-1}}{2}$$ $$f_k=\frac{1}{2}(f_k+f_{k-1}] \Rightarrow f_k=f_{k-1} $$ This means that $f_k$ is a constant independent of $k$. So $$f_k=f_0=\sum_{n=0}^{\infty}\frac{1}{2^n}=2.$$

$\endgroup$

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