18
$\begingroup$

How does one show that $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$$ for each nonnegative integer $n$?

I tried using the Snake oil technique but I guess I am applying it incorrectly. With the snake oil technique we have $$F(x)= \sum_{n=0}^{\infty}\left\{\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}\right\}x^{n}.$$ I think I have to interchage the summation and do something. But I am not quite comfortable in interchanging the summation. Like after interchaging the summation will $$F(x)=\sum_{k=0}^{n}\sum_{n=0}^{\infty}\binom{n+k}{k}\frac{1}{2^k}x^{n}?$$ Even if I continue with this I am unable to get the correct answer.

  • How does one prove this using the Snake oil technique?

  • A combinatorial proof is also welcome, as are other kinds of proofs.

$\endgroup$
18
  • 1
    $\begingroup$ I'm convinced that the sum can somehow be interpreted as a (strange) counting of the number of downward paths from the top of the Pascal triangle to the $n$'th row. I just can't quite see it. $\endgroup$
    – Arthur
    Jul 29 '16 at 11:33
  • 1
    $\begingroup$ When you exchange the order of summation, you have to change the limits accordingly. The outer sum should have absolute limits, while the inner sum can have limits depending on the outer index. $\endgroup$
    – Shagnik
    Jul 29 '16 at 12:14
  • 1
    $\begingroup$ You didn’t reverse the order of summation correctly. As $n$ ranges over the non-negative integers, so do the possible values of $k$. Thus, $\sum_{n\ge 0}\sum_{k=0}^n$ turns into $\sum_{k\ge 0}\sum_{n\ge k}$. You’re summing over all pairs $\langle n,k\rangle$ such that $0\le k\le n$. $\endgroup$ Jul 29 '16 at 12:34
  • 1
    $\begingroup$ I don't know whether this will help, but the problem is equivalent to showing that the coefficient of $x^n$ in $$(1-x)^{-n-1}\,(1-2x)^{-1}$$ is $2^{2n}$. Some complex analyst may be able to solve this using contour integration. $\endgroup$ Jul 29 '16 at 12:56
  • 1
    $\begingroup$ this is what i get using your method,Let $A_n=\sum_{k=0}^n \binom{n+k}{k}\frac{1}{2^k}$ and $f(x)=\sum_{n=0}^\infty A_n x^n$ then \begin{eqnarray} f(x)&=&\sum_{n=0}^\infty A_n x^n\\ &=&\sum_{n=0}^\infty \left(\sum_{k=0}^n \binom{n+k}{k}\frac{1}{2^k}\right) x^n\\ &=& \sum_{k=0}^\infty \left(\sum_{n=0}^\infty \binom{n+k}{k}x^n\right)\frac{1}{2^k} \\ &=& \sum_{k=0}^\infty \frac{1}{2^k} \frac{1}{(1-x)^{k+1}}\\ &=& \frac{2}{1-2x}\\ &=& \sum_{n=0}^\infty 2^{n+1} x^n\\ \end{eqnarray} Where is the problem here ???? $\endgroup$
    – Hamza
    Jul 29 '16 at 18:21

16 Answers 16

19
$\begingroup$

A proof by induction is possible, if a bit messy. For $n\in\Bbb N$ let $$s_n=\sum_{k=0}^n\binom{n+k}k\frac1{2^k}\;.$$ Clearly $s_0=1=2^0$. Suppose that $s_n=2^n$ for some $n\in\Bbb N$. Then

$$\begin{align*} s_{n+1}&=\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\left(\binom{n+k}k+\binom{n+k}{k-1}\right)\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k-1}\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=1}^n\binom{n+k}{k-1}\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+s_n+\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^{k+1}}\\\\ &=s_n+\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\left(\binom{2n+1}{n+1}+\binom{2n+1}n\right)\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\binom{2n+1}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\ &\overset{(*)}=2^n+\frac12\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\frac12\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\frac12s_{n+1}\;, \end{align*}$$

where the step $(*)$ follows from the fact that

$$\binom{2n+2}{n+1}=\binom{2n+1}{n+1}+\binom{2n+1}n=2\binom{2n+1}{n+1}\;.$$

Thus, $\frac12s_{n+1}=2^n$, and $s_{n+1}=2^{n+1}$, as desired.

Added: I just came up with a combinatorial argument as well. Flip a fair coin until either $n+1$ heads or $n+1$ tails have appeared. Let $k$ be the number of times the other face of the coin has appeared; clearly $0\le k\le n$. The last flip must result in the $(n+1)$-st instance of the majority face, but the other $n$ instances of that face and $k$ of the other can appear in any order.

Now imagine that after achieving the desired outcome we continue to flip the coin until we’ve flipped it $2n+1$ times. There are altogether

$$\binom{n+k}k2^{(2n+1)-(n+k)}=\binom{n+k}k2^{n+1-k}$$

sequences of $2n+1$ flips that decide the outcome at the $(n+k+1)$-st toss, so

$$\sum_{k=0}^n\binom{n+k}k2^{n+1-k}=2^{2n+1}\;,$$

and

$$\sum_{k=0}^n\binom{n+k}k\frac1{2^k}=2^n\;.$$

$\endgroup$
2
  • $\begingroup$ Now that I read your answer a bit closer, I note that my answer seems to be along the same lines. If you think they are too close, I will delete mine. $\endgroup$
    – robjohn
    Jan 31 '15 at 23:03
  • $\begingroup$ @robjohn: It’s essentially the same as my induction argument, but the annotations might help someone. $\endgroup$ Jan 31 '15 at 23:08
14
$\begingroup$

Let $S_n:=\sum\limits_{k=0}^n\,\binom{n+k}{k}\,\frac{1}{2^k}$ for every $n=0,1,2,\ldots$. Then, $$S_{n+1}=\sum_{k=0}^{n+1}\,\binom{(n+1)+k}{k}\,\frac{1}{2^k}=\sum_{k=0}^{n+1}\,\Biggl(\binom{n+k}{k}+\binom{n+k}{k-1}\Biggr)\,\frac{1}{2^k}\,.$$ Hence, $$S_{n+1}=\left(S_n+\binom{2n+1}{n+1}\frac{1}{2^{n+1}}\right)+\sum_{k=0}^n\,\binom{(n+1)+k}{k}\,\frac{1}{2^{k+1}}\,.$$ That is, $$S_{n+1}=S_n+\frac{S_{n+1}}{2}+\frac{1}{2^{n+2}}\,\Biggl(2\,\binom{2n+1}{n+1}-\binom{2n+2}{n+1}\Biggr)\,.$$ As $$\binom{2n+2}{n+1}=\frac{2n+2}{n+1}\,\binom{2n+1}{n}=2\,\binom{2n+1}{n+1}\,,$$ we deduce that $S_{n+1}=S_n+\frac{S_{n+1}}{2}$, or $$S_{n+1}=2\,S_{n}$$ for all $n=0,1,2,\ldots$. Because $S_0=1$, the claim follows.


Combinatorial Argument

The number of binary strings of length $2n+1$ with at least $n+1$ ones is clearly $2^{2n}$. For $k=0,1,2,\ldots,n$, the number of such strings whose $(n+1)$-st one is at the $(n+k+1)$-st position is $\binom{n+k}{k}\,2^{n-k}$. The claim is now evident.

$\endgroup$
8
  • 1
    $\begingroup$ This is definitely a non-snake oil method. $\endgroup$
    – Zack Ni
    Jul 29 '16 at 12:28
  • 2
    $\begingroup$ the op said "I tried using the Snake oil technique but I guess I am applying it incorrectly." $\endgroup$
    – Zack Ni
    Jul 29 '16 at 12:31
  • 1
    $\begingroup$ Yes but he added it in his comment. $\endgroup$
    – Zack Ni
    Jul 29 '16 at 12:33
  • 5
    $\begingroup$ Then, he's better add that in his question. In addition, he should explain why he wants this method as a solution. If it is an exercise for this method, then it makes sense. But if it is some random request without basis, I see no reason why it's certain that the method will work. $\endgroup$ Jul 29 '16 at 12:33
  • 1
    $\begingroup$ Yes he is not a good op :-) $\endgroup$
    – Zack Ni
    Jul 29 '16 at 12:35
11
$\begingroup$

Here is a variation based upon the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series. We can write e.g. \begin{align*} [x^k](1+x)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \sum_{k=0}^n\binom{n+k}{k}\frac{1}{2^k}&=\sum_{k=0}^n[x^k](1+x)^{n+k}\frac{1}{2^k}\tag{1}\\ &=[x^0](1+x)^n\sum_{k=0}^n\left(\frac{1+x}{2x}\right)^k\tag{2}\\ &=[x^0](1+x)^n\frac{1-\left(\frac{1+x}{2x}\right)^{n+1}}{1-\frac{1+x}{2x}}\tag{3}\\ &=[x^0](1+x)^n\frac{1}{(2x)^n}\frac{(2x)^{n+1}-(1+x)^{n+1}}{x-1}\tag{4}\\ &=\frac{1}{2^n}[x^n]\frac{(1+x)^{2n+1}}{1-x}\tag{5}\\ &=\frac{1}{2^n}[x^n]\sum_{k=0}^{2n+1}\binom{2n+1}{k}x^k\frac{1}{1-x}\tag{6}\\ &=\frac{1}{2^n}\sum_{k=0}^{n}\binom{2n+1}{k}[x^{n-k}]\frac{1}{1-x}\tag{7}\\ &=\frac{1}{2^n}\sum_{k=0}^{n}\binom{2n+1}{k}\tag{8}\\ &=\frac{1}{2^n}\cdot\frac{1}{2}2^{2n+1}\tag{9}\\ &=2^n \end{align*} and the claim follows.

Comment:

  • In (1) we apply the coefficient of operator.

  • In (2) we use the linearity of the coefficient of operator and the rule $$[x^{p+q}]A(x)=[x^p]x^{-q}A(x)$$

  • In (3) we use the finite geometric series formula.

  • In (4) we do some simplifications.

  • In (5) we use again the rule stated in comment (2) and note that the term $(2x)^{n+1}$ can be ignored, since it does not contribute to the coefficient of $x^n$.

  • In (6) we apply the binomial sum formula.

  • In (7) we note that only index up to $k=n$ contributes to the coefficient of $x^n$.

  • In (8) we recall the geometric series is $$\frac{1}{1-x}=1+x+x^2+\cdots$$ so that the contribution to the coefficient is always $1$.

  • In (9) we use the symmetry of the binomial sum formula.

$\endgroup$
6
  • $\begingroup$ what is called this kind of methods please, and where i can get more about it ? $\endgroup$
    – Hamza
    Jul 30 '16 at 1:39
  • 1
    $\begingroup$ @Hamza: This method is based upon G.P. Egorychev's classic. The method is sometimes denoted according to the operator coefficient of method or coefficient extractor method. This answer or this one provides some more aspects. $\endgroup$
    – epi163sqrt
    Jul 30 '16 at 5:54
  • $\begingroup$ (+1) I used a generating function approach, but I like this approach, too! $\endgroup$
    – robjohn
    Sep 18 '16 at 2:21
  • $\begingroup$ @robjohn: Thanks for your nice comment. Besides your nice answer (+1) I appreciate your high skills in manipulating expressions involving binomials with elementary means. It's a valuable source to improve my own skills! :-) $\endgroup$
    – epi163sqrt
    Sep 18 '16 at 7:08
  • $\begingroup$ I missed this one when it first appeared, Good work! (+1) (verified). $\endgroup$ Nov 5 '16 at 21:04
10
$\begingroup$

Since $$ \binom{2n-1}{n}+\binom{2n-1}{n-1}=\binom{2n}{n}\quad\text{and}\quad\binom{2n-1}{n}=\binom{2n-1}{n-1}\tag{1} $$ we have $$ \binom{2n-1}{n}=\frac12\binom{2n}{n}\tag{2} $$ Therefore, if we define $$ \begin{align} A_n &=\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}\tag{3a}\\ &=\sum_{k=0}^n\left[\binom{n+k-1}{k}+\binom{n+k-1}{k-1}\right]\frac1{2^k}\tag{3b}\\ &=\sum_{k=0}^n\binom{n+k-1}{k}\frac1{2^k}\\ &+\sum_{k=0}^{n-1}\binom{n+k}{k}\frac1{2^{k+1}}\tag{3c}\\ &=\sum_{k=0}^{n-1}\binom{n+k-1}{k}\frac1{2^k}+\binom{2n-1}{n}\frac1{2^n}\\ &+\sum_{k=0}^n\binom{n+k}{k}\frac1{2^{k+1}}-\binom{2n}{n}\frac1{2^{n+1}}\tag{3d}\\ &=\sum_{k=0}^{n-1}\binom{n+k-1}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k}\frac1{2^{k+1}}\tag{3e}\\ &=A_{n-1}+\frac12A_n\tag{3f} \end{align} $$ Explanation:
$\text{(3a)}$: define $A_n$
$\text{(3b)}$: use Pascal's Triangle
$\text{(3c)}$: substitute $k\mapsto k+1$ in the second sum
$\text{(3d)}$: add and subtract the last term in each sum
$\text{(3e)}$: use $(2)$ to cancel the terms separated in $\text{(3d)}$
$\text{(3f)}$: use the definition of $A_n$

Thus, $\text{(3f)}$ implies that $$ A_n=2A_{n-1}\tag{4} $$ Since $A_0=1$, we get that $$ A_n=2^n\tag{5} $$

$\endgroup$
2
  • $\begingroup$ +1. Clever answer. At the beginning I didn't notice it was a finite sum. $\endgroup$ Feb 1 '15 at 21:33
  • $\begingroup$ @FelixMarin: yeah, the finiteness is a hitch. However, I have not yet succeeded in getting this identity without induction. $\endgroup$
    – robjohn
    Feb 1 '15 at 21:43
9
$\begingroup$

Here is a probabilistic proof of your equality, which I will write as $$ \sum_{k=0}^n\binom{n+k}{k}2^{-(n+k)}=1 $$ Consider a rectangular lattice of $(n+2)^2$ points, where the lower left point is $(0,0)$ and the upper right is $(n+1,n+1)$. An ant starts at $(0,0)$, and once per second, randomly chooses to take a step upwards or to the right. Furthermore, imagine the topmost row $\{(x,n+1):0\le x\le n\}$ and rightmost column $\{(n+1,y):0\le y\le n\}$ are covered in glue, so the ant stops moving once it reaches one of these points.

Eventually, the ant will get stuck. You can show that the probability the ant gets stuck at $(k,n+1)$ is equal to $\binom{n+k}{k}2^{-(n+k)}\cdot\frac12$ by considering all the possible paths that bring it to that point. Therefore, the probability the ant gets stuck at either $(k,n+1)$ or $(n+1,k)$ is equal to $$ \binom{n+k}{k}2^{-(n+k)} $$ Since the ant gets stuck at exactly one of these point, the sum of these probabilities must equal $1$.

$\endgroup$
1
  • $\begingroup$ Brilliant. However it was just a translation of the combinatorial argument, but it was an elegant one. I like it... $\endgroup$
    – MR_BD
    Jun 6 '19 at 14:15
7
$\begingroup$

This one can also be done using complex variables.

Suppose we seek to show that $$\sum_{k=0}^{n} {n+k \choose k} \frac{1}{2^k} = 2^n.$$ Introduce the integral repesentation $${n+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+k}}{z^{k+1}} \; dz.$$

This gives for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \sum_{k=0}^n \frac{(1+z)^k}{(2z)^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \frac{(1+z)^{n+1}/(2z)^{n+1}-1}{(1+z)/(2z)-1} \; dz \\ = \frac{2}{2\pi i} \int_{|z|=\epsilon} (1+z)^n \frac{(1+z)^{n+1}/(2z)^{n+1}-1}{(1+z)-2z} \; dz \\ = \frac{2}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{1-z} \left((1+z)^{n+1}/(2z)^{n+1}-1\right) \; dz.$$

The second component makes no contribution inside the contour, leaving just $$\frac{2^{-n}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{(1+z)^{2n+1}}{1-z} \; dz.$$ Extracting coefficients we get $$2^{-n} [z^n] \frac{(1+z)^{2n+1}}{1-z} = 2^{-n} \sum_{q=0}^n {2n+1\choose q} = 2^{-n}\times \frac{1}{2} \times 2^{2n+1} = 2^n.$$

$\endgroup$
4
$\begingroup$

Binomial coefficient is just $\binom{-(n-1)}{k} = (-1)^k \binom{n+k}{k}$ and take $x= -\frac{1}{2}$so you get $\sum_{k=0}^{\infty} \binom{-(n-1)}{k} x^k = \frac{1}{(1-x)^{n-1}}$

$\endgroup$
3
  • 2
    $\begingroup$ How does that solve the problem? The sum in question is finite. $\endgroup$ Jan 31 '15 at 21:13
  • $\begingroup$ Two corrections: $\binom{\color{red}{-n-1}}{k}=(-1)^k\binom{n+k}{k}$, and $\sum_{k=0}^\infty\binom{\color{red}{-n-1}}k x^k=\frac1{(1\color{red}{+}x)^{\color{red}{-n-1}}}$. Your method proves that $\sum_{k=0}^\infty \binom{n+k}{k}2^{-k}=2^{n+1}$, which is interesting, but not what was asked. $\endgroup$ Apr 26 '18 at 18:14
  • $\begingroup$ @MikeEarnest I would assume $\sum_{k=0}^\infty\binom {-n-1}kx^k=(1+x)^{-n-1}$. $\endgroup$
    – user
    Jun 11 '19 at 21:14
4
$\begingroup$

While this answer is basically the same as the one by Mike Earnest, and as the added interpretation in the answer by Brian Scott, let me phrase it slightly differently, as this comes close to a game already considered by Blaise Pascal (before probability theory even existed). Also I believe there is an essential invocation of symmetry here, which I could not find clearly stated in those answers.

Let two players play "best of $2n+1$" for repeatedly (fairly) tossing a fair coin: the first who gets $n+1$ favourable outcomes wins. By symmetry each has $\frac12$ chance of winning. On the other hand, let us count the winning possibilities for the player A, out of the $2^{2n+1}$ possible sequences (I imagine the coin to be tossed $2n+1$ times, even if the winner is determined earlier). The toss that wins for A (if it happens) has precisely $n$ outcomes favourable for A coming before it, and some number $k$ of unfavourable outcomes, with $0\leq k\leq n$; there then remain $n-k$ tosses after A has already won. For a given $k$ the number of possibilities is $\binom{n+k}k\times2^{n-k}$, the first factor counting the possibilities before the decisive toss and the second factor those after it. All in all we should get half of all $2^{2n+1}$ possibilities, so $$ \sum_{k=0}^n\binom{n+k}k\times2^{n-k}=2^{2n} $$ from which the stated identity follows after division by $2^n$.

To add a bit about the Pascal reference, what he really considers is the question of how to fairly split the stakes (taking into account their chances to eventually win) when prematurely ending such a game when players A and B need a different number of favourable outcomes to the finish line. If A still has $a$ wins to go and B needs $b$ wins, he establishes the that the stakes should be divided as the proportion of the sum of the first $b$ to the sum of the remaining $a$ entries in the line of Pascal's triangle that has length $a+b$ (to Pascal that was the "base" with "exposant $a+b$" of the triangle; to us it is line $a+b-1$). The case considered here is the easy one with $a=b$, so the proportion clearly becomes $1:1$. In the general case, counting as done above leads to the interesting identity $$ \sum_{k=0}^{b-1}\binom{a+b-1}k = \sum_{k=0}^{b-1}\binom{a-1+k}k\times2^{b-1-k}, $$ or putting $n=b-1$: $$ \sum_{k=0}^n\binom{a+n}k = \sum_{k=0}^n\binom{a-1+k}k\times2^{n-k}, $$ This is fairly easy to prove by induction on $n$. Note that taking (also) $a=n+1$ one gets the formula of this question, as the LHS then gives $2^{2n+1}/2=2^{2n}$.

$\endgroup$
3
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mrm}[1]{\,\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \mrm{f}_{n}\pars{x} & \equiv \sum_{k = 0}^{n}{n + k \choose k}x^{k} = \color{#f00}{{1 \over n!}\sum_{k = 0}^{n}{\pars{n + k}! \over k!}x^{k}} = \pars{n + 1} + {1 \over n!}\sum_{k = 1}^{n} {n + k \over k}{\pars{n + k - 1}! \over \pars{k - 1}!}x^{k} \\[5mm] & = n + 1 + {1 \over n!}\sum_{k = 0}^{n - 1} {n + k + 1 \over k + 1}{\pars{n + k}! \over k!}x^{k + 1} \\[5mm] & = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + {n \over n!}\,x\sum_{k = 0}^{n} {1 \over k + 1}{\pars{n + k}! \over k!}x^{k} + x\color{#f00}{{1 \over n!}\sum_{k = 0}^{n} {\pars{n + k}! \over k!}x^{k}} \\[5mm] & = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + {n \over n!}\,x\sum_{k = 0}^{n}x^{k} {\pars{n + k}! \over k!}\int_{0}^{1}y^{k}\,\dd y + x\mrm{f}_{n}\pars{x} \\[5mm] & = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + nx\int_{0}^{1}\color{#f00}{{1 \over n!}\sum_{k = 0}^{n} {\pars{n + k}! \over k!}\pars{xy}^{k}}\,\dd y + x\mrm{f}_{n}\pars{x} \\[5mm] & = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + n\int_{0}^{1}\mrm{f}_{n}\pars{xy}\,x\,\dd y + x\mrm{f}_{n}\pars{x} \end{align}


$$ \imp\quad \begin{array}{|c|}\hline\mbox{}\\ \ds{\quad\mrm{f}_{n}\pars{x} = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + n\int_{0}^{x}\mrm{f}_{n}\pars{y}\,\dd y + x\mrm{f}_{n}\pars{x} \quad} \\ \mbox{}\\ \hline \end{array} $$
Then, \begin{align} \mrm{f}_{n}'\pars{x} & = -\pars{2n + 1}{2n \choose n}x^{n} + n\mrm{f}_{n}\pars{x} + \mrm{f}_{n}\pars{x} + x\mrm{f}_{n}'\pars{x} \,,\quad\mrm{f}_{n}\pars{0} = 1 \end{align}
$$ \mrm{f}_{n}'\pars{x} - {n + 1 \over 1 - x}\,\mrm{f}_{n}\pars{x} = -\pars{2n + 1}{2n \choose n}{x^{n} \over 1 - x} $$
$$ \totald{\bracks{\pars{1 - x}^{n + 1}\mrm{f}_{n}\pars{x}}}{x} = -\pars{2n + 1}{2n \choose n}x^{n}\pars{1 - x}^{n} $$
$$ 2^{-n - 1}\,\,\mrm{f}_{n}\pars{\half} - 1 = -\pars{2n + 1}{2n \choose n}\int_{0}^{1/2}x^{n}\pars{1 - x}^{n}\,\dd x $$
\begin{align} \color{#f00}{\sum_{k = 0}^{n}{n + k \choose k}x^{k}} & = \mrm{f}_{n}\pars{\half} = 2^{n + 1}\ -\ \overbrace{% 2^{n + 1}\pars{2n + 1}{2n \choose n} \int_{0}^{1/2}\bracks{{1 \over 4} - \pars{x - \half}^{2}}^{n}\,\dd x} ^{\ds{2^{n}}} \\[5mm] & = \color{#f00}{2^{n}} \end{align}

Note that $$ \int_{0}^{1/2}\bracks{{1 \over 4} - \pars{x - \half}^{2}}^{n}\,\dd x = \half\,\ \overbrace{{\Gamma\pars{n + 1}\Gamma\pars{n + 1} \over \Gamma\pars{2n + 2}}} ^{\ds{\mrm{B}\pars{n + 1,n + 1}}}\ =\ {1 \over 2\pars{2n + 1}{2n \choose n}} $$ $\ds{\Gamma}$: Gamma Function. B: Beta Function.

$\endgroup$
2
  • $\begingroup$ Long way to go. Congratulations on getting there. $\endgroup$ Jul 31 '16 at 1:47
  • $\begingroup$ @martycohen Thanks for your remark. I tried a few approaches until I remembered I evaluated something similar ( math.stackexchange.com/a/1837721/85343 ) and the only way was to find a differential equation. $\texttt{@Marko Riedel}$ answer already mentioned that it's somehow different because there isn't an upper bound. $\endgroup$ Jul 31 '16 at 2:11
3
$\begingroup$

$$\begin{align} \sum_{k=0}^n \binom {n+k}k\frac 1{2^k} &=\frac 1{2^n}\sum_{k=0}^n \color{blue}{2^{n-k}}\binom {n+k}n\\ &=\frac 1{2^n}\sum_{k=0}^n\color{blue}{\sum_{r=0}^{n-k}\binom {n-k}r}\binom{n+k}r\\ &=\frac 1{2^n}\sum_{s=0}^n\sum_{r=0}^s\binom sr\binom {2n-s}n &&\scriptsize (\text{Putting } s=n-k)\\ &=\frac 1{2^n}\sum_{r=0}^n\sum_{s=r}^n \binom s{s-r}\binom{2n-s}{n-s}\\ &=\frac 1{2^n}\sum_{r=0}^n\sum_{s=r}^n(-1)^{s-r}\binom {-r-1}{s-r}(-1)^{n-s}\binom {-n-1}{n-s} &&\scriptsize(\text{Upper Negation})\\ &=\frac 1{2^n}\sum_{r=0}^n(-1)^{n-r} \color{magenta}{\sum_{s=r}^n\binom {-r-1}{s-r}\binom{-n-1}{n-s}}\\ &=\frac 1{2^n}\sum_{r=0}^n(-1)^{n-r}\color{magenta}{\binom {-n-r-2}{n-r}}&&\scriptsize(\text{Vandermonde})\\ &=\frac 1{2^n}\sum_{r=0}^n(-1)^{n-r}(-1)^{n-r}\binom {2n+1}{n-r}&&\scriptsize(\text{Upper Negation})\\ &=\frac 1{2^n}\sum_{r=0}^n\binom{2n+1}{n-r}\\ &=\frac 1{2^n}\cdot \frac 12 \sum_{r=0}^n \binom {2n+1}{n-r}+\binom {2n+1}{n+r+1} &&\scriptsize(\text{both summands are equal})\\ &=\frac 1{2^{n+1}}\sum_{r=0}^{2n+1}\binom {2n+1}r\\ &=\frac 1{2^{n+1}}\cdot 2^{2n+1}\\\\ &=2^n\qquad \blacksquare \end{align}$$

$\endgroup$
2
$\begingroup$

Let $$ S_n:=\sum_{k=0}^n\frac{\binom{n+k}{k}}{2^{n+k}} $$ Obviously $S_0=1$. Assume that equality $$S_{n-1}=1\tag1$$ is valid for some $n$. Then it is valid for $n+1$ as well: $$ \begin{align} S_n &=\sum_{k=0}^n\frac{\binom{n+k}{k}}{2^{n+k}}\\ &=\sum_{k=0}^n\frac{\binom{n+k-1}{k-1}+\binom{n-1+k}{k}}{2^{n+k}}\\ &=\frac12\sum_{k=0}^{n-1}\frac{\binom{n+k}{k}}{2^{n+k}}+\frac12\sum_{k=0}^n\frac{\binom{n-1+k}{k}}{2^{n-1+k}}\\ &=\frac12S_n-\frac{\binom{2n}{n}}{2^{2n+1}}+\frac12S_{n-1}+\frac{\binom{2n-1}{n}}{2^{2n}}\\ &=\frac12S_n+\frac12S_{n-1}\implies S_n=S_{n-1}\stackrel{I.H.}=1. \end{align} $$

Thus, by induction the equality $(1)$ is valid for all integer $n\ge0$.

$\endgroup$
2
$\begingroup$

This is a nice case where induction loading (the technique of deliberately strengthening what is to be proved for the purpose of making proofs by induction easier) is handy. For motivation see my other answer. Generalise the statement to the claim $$ \sum_{k=0}^n\binom{m+n+1}k =\sum_{k=0}^n\binom{m+k}k\times2^{n-k}, \tag1 $$ knowing that for $m=n$ the first sum gives $\sum_{k=0}^{n}\binom{2n+1}k=\frac12\sum_{k=0}^{2n+1}\binom{2n+1}k=2^{2n}$, and one can divide both sides by $2^n$.

Proof of $(1)$ by induction on $n$. For $n=0$ one gets $\binom {m+1}0=1=\binom m0$, so this is fine. So suppose $n>0$ and the result established for $n-1$. We can write $\binom{m+n+1}k=\binom{m+n}k+\binom{m+n}{k-1}$ by Pascal's recurrence (with the convention $\binom a{-1}=0$ for any $a$) so the left hand side is $$ \sum_{k=0}^n\left(\binom{m+n}k+\binom{m+n}{k-1}\right) =\sum_{k=0}^n\binom{m+n}k+\sum_{l=-1}^{n-1}\binom{m+n}l \\ =2\sum_{k=0}^{n-1}\binom{m+n}k+\binom{m+n}n. $$ Now we can apply the induction hypothesis to the summation, and get $$ 2\sum_{k=0}^{n-1}\binom{m+k}k\times2^{n-1-k}+\binom{m+n}n =\sum_{k=0}^n\binom{m+k}k\times2^{n-k} $$ as desired.

$\endgroup$
2
$\begingroup$

Another probabilistic interpretation/proof

Consider the following problem: Flip a fair coin for $2n+1$ times sequentially, along the way, how many times do we have exactly $n+1$ heads or tails occur in the sequence on expectation?

Clearly, the solution is only 1 time (by just a little bit logically reasoning.

On the other hand, the expression $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^{n+k}}$ is the expectation as well (by using expectation definition).

These two answers must be equal, so, the equality is proved.

$\endgroup$
2
$\begingroup$

Content of this answer is not new—it's similar to Mike Earnest's answer and others—but explanation is a bit more visual.

A walker starts at a point and, with equal probability, takes a unit step either in the southwest or the southeast direction. The probability that the walker passes through a given point on the grid is given by the table below. $$ \begin{array}{ccccccccccccccc} & & & & & & & 1 & & & & &\\ & & & & & & \frac{1}{2} & & \frac{1}{2} & & & &\\ & & & & & \frac{1}{4} & & \frac{2}{4} & & \frac{1}{4} & & &\\ & & & &\frac{1}{8} & & \frac{3}{8} & & \frac{3}{8} & & \frac{1}{8} & &\\ & & &\frac{1}{16} & & \frac{4}{16} & & \frac{6}{16} & & \frac{4}{16} & & \frac{1}{16} &\\ & & \frac{1}{32} & & \frac{5}{32} & & \frac{10}{32} & & \frac{10}{32} & & \frac{5}{32} & & \frac{1}{32}\\ & \frac{1}{64} & & \frac{6}{64} & & \frac{15}{64} & & \frac{20}{64} & & \frac{15}{64} & & \frac{6}{64} & & \frac{1}{64}\\ \frac{1}{128} & & \frac{7}{128} & & \frac{21}{128} & & \frac{35}{128} & & \frac{35}{128} & & \frac{21}{64} & & \frac{7}{64} & & \frac{1}{128}\\ \end{array} $$

Now introduce an absorption process.

  • Some grid points remain as before: the walker moves either southwest or southeast from the point with equal probability.
  • Some grid points become half absorbing: one of the exit directions is blocked, and the walker either moves in the unblocked direction or gets absorbed with equal probability.
  • Finally, some grid points become fully absorbing: the walker gets absorbed with probability $1$ and does not move on.

The probability of absorption is obtained by summing, over all accessible grid points, the probability of reaching the given point multiplied by the probability of being absorbed at that point. This means multiplying the reaching probability by $0$ for non-absorbing points, by $\frac{1}{2}$ for half absorbing points, and by $1$ for full absorbing points.

In the example below, an absorbing boundary is indicated in boldface. The walker in this example gets absorbed with probability $1$. $$ \begin{array}{ccccccccccccccc} & & & & & & & 1 & & & & &\\ & & & & & & \frac{1}{2} & & \mathbf{\frac{1}{2}} & & & &\\ & & & & & \mathbf{\frac{1}{4}} & & \mathbf{\frac{2}{4}} & & \mathbf{\frac{1}{4}} & & &\\ & & & & & & \mathbf{\frac{3}{8}} & & & & & &\\ \end{array} $$ Indeed, summing along the boundary, since points not on the boundary have absorption probability $0$, gives $$ \frac{1}{2}\cdot\frac{1}{4}+1\cdot\frac{3}{8}+\frac{1}{2}\cdot\frac{2}{4}+0\cdot\frac{1}{2}+1\cdot\frac{1}{4}=1. $$ A larger example. $$ \begin{array}{ccccccccccccccc} & & & & & & & 1 & & & & &\\ & & & & & & \frac{1}{2} & & \frac{1}{2} & & & &\\ & & & & & \frac{1}{4} & & \frac{2}{4} & & \frac{1}{4} & & &\\ & & & &\frac{1}{8} & & \frac{3}{8} & & \mathbf{\frac{3}{8}} & & \frac{1}{8} & &\\ & & &\frac{1}{16} & & \frac{4}{16} & & \mathbf{\frac{6}{16}} & & \mathbf{\frac{4}{16}} & & \mathbf{\frac{1}{16}} &\\ & & \mathbf{\frac{1}{32}} & & \frac{5}{32} & & \mathbf{\frac{10}{32}} & & & & \mathbf{\frac{5}{32}} & &\\ & & & \mathbf{\frac{6}{64}} & & \mathbf{\frac{15}{64}} & & & & & & & & \\ & & & & \mathbf{\frac{21}{128}} & & & & & & & & & & \\ \end{array} $$ Again, the walker always gets absorbed, and, indeed, $$ \frac{1}{2}\cdot\frac{1}{32}+\frac{1}{2}\cdot\frac{6}{64}+1\cdot\frac{21}{128}+\frac{1}{2}\cdot\frac{15}{64}+\frac{1}{2}\cdot\frac{10}{32}+\frac{1}{2}\cdot\frac{6}{16}+0\cdot\frac{3}{8}+\frac{1}{2}\cdot\frac{4}{16}+1\cdot\frac{5}{32}+\frac{1}{2}\cdot\frac{1}{16} $$ equals $1$.

The familiar property that the $n^\text{th}$ row of Pascal's triangle sums to $2^n$, or equivalently, that the $n^\text{th}$ row divided by $2^n$ sums to $1$ can be seen by considering a boundary like the following. $$ \begin{array}{ccccccccccccccc} & & & & & & & 1 & & & & &\\ & & & & & & \frac{1}{2} & & \frac{1}{2} & & & &\\ & & & & & \frac{1}{4} & & \frac{2}{4} & & \frac{1}{4} & & &\\ & & & & \mathbf{\frac{1}{8}} & & \mathbf{\frac{3}{8}} & & \mathbf{\frac{3}{8}} & & \mathbf{\frac{1}{8}} & &\\ & & & \mathbf{\frac{1}{16}} & & \mathbf{\frac{4}{16}} & & \mathbf{\frac{6}{16}} & & \mathbf{\frac{4}{16}} & & \mathbf{\frac{1}{16}} &\\ \end{array} $$

Finally, the identity in this problem follows from considering a boundary like the one below. $$ \begin{array}{ccccccccccccccc} & & & & & & & 1 & & & & &\\ & & & & & & \frac{1}{2} & & \frac{1}{2} & & & &\\ & & & & & \frac{1}{4} & & \frac{2}{4} & & \frac{1}{4} & & &\\ & & & & \mathbf{\frac{1}{8}} & & \frac{3}{8} & & \frac{3}{8} & & \mathbf{\frac{1}{8}} & &\\ & & & & & \mathbf{\frac{4}{16}} & & \frac{6}{16} & & \mathbf{\frac{4}{16}} & & &\\ & & & & & & \mathbf{\frac{10}{32}} & & \mathbf{\frac{10}{32}} & & & & \\ & & & & & & & \mathbf{\frac{20}{64}} & & & & & & \\ \end{array} $$

$\endgroup$
1
$\begingroup$

Suppose we seek to verify that

$$\sum_{k=0}^n {n+k\choose k} \frac{1}{2^k} = 2^n.$$

In the following we make an effort to use a different set of integrals from the answer by @MarkusScheuer, for variety's sake, even if this is not the simplest answer.

The difficulty here lies in the fact that the binomial coefficients on the LHS do not have an upper bound for the sum wired into them. We use an Iverson bracket to get around this:

$$[[0\le k\le n]] = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{w^k}{w^{n+1}} \frac{1}{1-w} \; dw.$$

Introduce furthermore

$${n+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1-z)^{k+1}} \; dz.$$

With the Iverson bracket in place we can let the sum range to infinity, getting

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} \sum_{k\ge 0} \frac{w^k}{(1-z)^k} \frac{1}{2^k} \; dz\; dw.$$

This converges when $|w| < |2(1-z)|.$ We require $\gamma \lt 2(1-\epsilon)$ or $\epsilon \lt 1-\gamma/2.$ Simplifying we have

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} \frac{1}{1-w/(1-z)/2} \; dz\; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z-w/2} \; dz\; dw.$$

The pole at $z=1-w/2$ is outside the contour due to the requirements on convergence, so we may use the negative of the residue there, getting

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{(1-w/2)^{n+1}} \; dw.$$

This could have been obtained by inspection, bypassing the Iverson bracket. Now put $w (1-w/2) = v$ so that $w = 1-\sqrt{1-2v}$ (this branch maps $w=0$ to $v=0$) to get (here we have $v=w-\cdots$ so the image of $|w|=\gamma$ makes one turn around the origin and may be deformed to a circle $|v|=\gamma'$)

$$\frac{1}{2\pi i} \int_{|v|=\gamma'} \frac{1}{v^{n+1}} \frac{1}{\sqrt{1-2v}} \frac{1}{\sqrt{1-2v}} \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\gamma'} \frac{1}{v^{n+1}} \frac{1}{1-2v} \; dv = 2^n.$$

This is the claim. Note that we may take $\gamma' \lt \gamma - \frac{1}{2} \gamma^2.$

Observe that

$$\mathrm{Res}_{z=\infty} \frac{1}{z^{n+1}} \frac{1}{1-z-w/2} = - \mathrm{Res}_{z=0} \frac{1}{z^2} z^{n+1} \frac{1}{1-w/2-1/z} \\ = - \mathrm{Res}_{z=0} z^{n} \frac{1}{z(1-w/2)-1} = 0.$$

This was an interesting exercise showing how the choice of contour for convergence influences the computation. The branch of $\sqrt{1-2v}$ that was used has the branch cut on $[1/2, \infty).$

$\endgroup$
0
$\begingroup$

The required equality can be written as $$\sum_{k=0}^n \binom{n+k}{k} 2^{n-k} = 2^{2n}$$

Now, we have $$\sum\binom{n+k}{k} x^k = \frac{1}{(1-x)^{n+1}}$$

Therefore, our sum equals the coefficient of $x^n$ in the product $$[x^n]\frac{1}{(1-x)^{n+1}(1-2 x)}= [x^{-1}]\cdot \frac{1}{(1-2x)(x(1-x))^{n+1}} $$ Equivalently, we have to show that the residue at $x=0$ of $$\frac{2}{1-x} \cdot \left(\frac{1}{x(2-x)}\right)^{n+1} $$ is $1$, for all $n\ge 0$ (example with WA).

Now, let's recall the Lagrange–Bürmann formula. Consider $f(x)$ an analytic function $f(0) = 0$, $f'(0) \ne 0$, with inverse $g(x)$, $H$ an analytic function. Then we have
$$\operatorname{Res}_{x=0}\ H'(x) \cdot \frac{1}{f^n(x)}= n[x^n] H(g(x))$$ for all $n\ge 1$.

Now, $f(x) = x(2-x)$, with inverse $g(x) = 1 - \sqrt{1-x}$, $H'(x) = \frac{2}{1-x}$, $H(x) = \log\frac{1}{(1-x)^2}$. Now, $$H(g(x)) = \log\frac{1}{(1-(1-\sqrt{1-x}))^2}= \log\frac{1}{1-x}= \sum_{n\ge 1} \frac{x^n}{n}$$ We are done.

$\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.