10
$\begingroup$

How to does one show $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{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 doesn one prove this using the Snake oil technique?

  • A combinatorial proof is also welcome.

$\endgroup$

marked as duplicate by Mike Earnest, Eevee Trainer, Parcly Taxel, jgon, Community Mar 17 at 3:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Induction will probably make this easy! $\endgroup$ – Zestylemonzi Jul 29 '16 at 11:25
  • $\begingroup$ @Zestylemonzi I am looking for a solution using the "snake oiling" technique :) thanks. As for solution, I do have some other methods which avoid induction $\endgroup$ – crskhr Jul 29 '16 at 11:26
  • 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$ 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$ – Brian M. Scott 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$ – Batominovski Jul 29 '16 at 12:56
9
$\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$
  • $\begingroup$ This is definitely a non-snake oil method. $\endgroup$ – Zack Ni Jul 29 '16 at 12:28
  • $\begingroup$ I'm sorry. Was I required to use a particular method? The OP made an attempt with that method but he never requested a specific method as an answer. $\endgroup$ – Batominovski Jul 29 '16 at 12:29
  • 1
    $\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
  • $\begingroup$ He didn't say "I want a solution using this method." Do you know how to read? $\endgroup$ – Batominovski Jul 29 '16 at 12:31
  • 4
    $\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$ – Batominovski Jul 29 '16 at 12:33
8
$\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$
  • $\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$ – Markus Scheuer 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$ – Markus Scheuer Sep 18 '16 at 7:08
  • $\begingroup$ I missed this one when it first appeared, Good work! (+1) (verified). $\endgroup$ – Marko Riedel Nov 5 '16 at 21:04
1
$\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$
  • $\begingroup$ Long way to go. Congratulations on getting there. $\endgroup$ – marty cohen 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$ – Felix Marin Jul 31 '16 at 2:11
0
$\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)|.$ 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

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

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$

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