$$A_n:=\sum_{k=0}^{n}{{n+k}\choose{n}} 2^k,\quad{B_n}:=\sum_{k=0}^{n}{{n+k}\choose{n}}(-1)^k$$

I've found that (based on values for small $n$) this identity seems to be true:


However, I'm stuck on trying to find a proof. Any ideas? Thanks!

  • 1
    $\begingroup$ Have you tried induction ? If you did, then $$ \dbinom{n+1+k}k = \frac{n+1+k}{n+1} \dbinom{n+k}k$$ might be useful. $\endgroup$ – Sandeep Silwal Jan 6 '18 at 3:02
  • $\begingroup$ Holy braces, Batman. Try not to overdo it with braces because it makes it difficult to clean up your TeX. $\endgroup$ – Cameron Williams Jan 6 '18 at 23:10

The striking symmetry of this binomial identity might lead us to ask what are the roles of $2$ and $-1$ and are there similar identities like this one? Here is a slight generalisation using essentially the same approach as @MarkoRiedel did in his nice answer.

We consider $a\in\mathbb{C}$ instead of $2$ resp. $-1$ and obtain \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{\binom{n+k}{n}a^k}\tag{0}\\ &=\sum_{k=0}^n\binom{-n-1}{k}(-a)^k\tag{1}\\ &=\sum_{k=0}^n[z^k]\frac{1}{(1-az)^{n+1}}\tag{2}\\ &=[z^0]\frac{1}{(1-az)^{n+1}}\sum_{k=0}^n\frac{1}{z^k}\tag{3}\\ &=[z^0]\frac{1}{(1-az)^{n+1}}\cdot\frac{1-z^{n+1}}{z^n(1-z)}\tag{4}\\ &=[z^n]\frac{1}{(1-az)^{n+1}(1-z)}\tag{5}\\ &=\frac{(-1)^n}{a^{n+1}}\mathrm{Res}_{z=0}\underbrace{\frac{1}{z^{n+1}\left(z-\frac{1}{a}\right)^{n+1}(z-1)}}_{f(z)}\tag{6}\\ &=\left(-\frac{1}{a}\right)^{n+1} \left(\mathrm{Res}_{z=\frac{1}{a}}+\mathrm{Res}_{z=1}+\mathrm{Res}_{z=\infty}\right)f(z)\tag{7} \end{align*}


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

  • In (2) and (3) we apply the coefficient of operator and use the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

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

  • In (5) we apply the same rule as we did in (3) and skip the term $z^{n+1}$ since it does not contribute to $[z^n]$.

  • In (6) we use the representation with residual at $z=0$.

  • In (7) we use the fact that computing the residue at zero is minus the sum of the residuals at the other poles and infinity.

Calculating the residuals gives \begin{align*} \mathrm{Res}_{z=\frac{1}{a}}f(z)&=\frac{1}{n!}\left[\frac{d^n}{dz^n}\left(\frac{1}{z^{n+1}(z-1)}\right)\right]_{z=\frac{1}{a}}\\ &=\frac{1}{n!}\left[\sum_{q=0}^n\binom{n}{q}\frac{d^q}{dz^q}\left(\frac{1}{z^{n+1}}\right)\frac{d^{n-q}}{dz^{n-q}}\left(\frac{1}{z-1}\right)\right]_{z=\frac{1}{a}}\\ &=\frac{1}{n!}\left[\sum_{q=0}^n\binom{n}{q}(-1)^q\frac{(n+q)!}{q!}\frac{1}{z^{n+1+q}} (-1)^{n-q}(n-q)!\frac{1}{(z-1)^{n-q+1}}\right]_{z=\frac{1}{a}}\\ &=(-1)^n\left(\frac{a^2}{1-a}\right)^{n+1}\sum_{q=0}^n\binom{n+q}{q}(1-a)^q\\ \mathrm{Res}_{z=1}f(z)&=\frac{1}{\left(1-\frac{1}{a}\right)^{n+1}}\\ &=\left(\frac{a}{a-1}\right)^{n+1}\\ \mathrm{Res}_{z=\infty}f(z)&=\mathrm{Res}_{z=0}\left(-\frac{1}{z^2}f\left(\frac{1}{z}\right)\right)\\ &=-\mathrm{Res}_{z=0}\left(\frac{1}{z^2}\cdot\frac{z^{n+1}}{\left(\frac{1}{z}-\frac{1}{a}\right)^{n+1}\left(\frac{1}{z}-a\right)}\right)\\ &=-\mathrm{Res}_{z=0}\frac{z^{2n+1}a^{n+1}}{(a-z)^{n+1}(1-z)}\\ &=0 \end{align*}

Putting all together in (7) gives \begin{align*} &\left(-\frac{1}{a}\right)^{n+1} \left(\mathrm{Res}_{z=\frac{1}{a}}+\mathrm{Res}_{z=1}+\mathrm{Res}_{z=\infty}\right)f(z)\\ &\quad=\left(-\frac{1}{a}\right)^{n+1}\left((-1)^n\left(\frac{a^2}{1-a}\right)^{n+1}\sum_{k=0}^n\binom{n+k}{k}(1-a)^k +\left(\frac{a}{a-1}\right)^{n+1}+0\right)\\ &\quad\color{blue}{=-\left(\frac{a}{1-a}\right)^{n+1}\sum_{k=0}^n\binom{n+k}{n}(1-a)^k+\left(\frac{1}{1-a}\right)^{n+1}}\tag{8} \end{align*}

We finally conclude from (0) and (8)

The following is valid for non-negative integer $n$ and $a\in\mathbb{C}$ \begin{align*} \color{blue}{(1-a)^{n+1}\sum_{k=0}^n\binom{n+k}{n}a^k =1-a^{n+1}\sum_{k=0}^n\binom{n+k}{n}(1-a)^k} \end{align*}

Some special cases:

$a=-1, a=2$ (OP's identity):

\begin{align*} 2^{n+1}\sum_{k=0}^n\binom{n+k}{n}(-1)^k=1+(-1)^n\sum_{k=0}^n\binom{n+k}{n}2^k \end{align*}


\begin{align*} \sum_{k=0}^n\binom{n+k}{k}\frac{1}{2^k}=2^n \end{align*}

$a=\frac{1}{3}, a=\frac{2}{3}$:

\begin{align*} \left(\frac{2}{3}\right)\sum_{k=0}^n\binom{n+k}{n}\frac{1}{3^k} =1-\frac{1}{3^{n+1}}\sum_{k=0}^n\binom{n+k}{n}\left(\frac{2}{3}\right)^k \end{align*}

  • $\begingroup$ Beautiful ... this deserves more upvotes! $\endgroup$ – tired Jan 14 '18 at 13:29
  • $\begingroup$ @tired: Many thanks for your nice comment. :-) $\endgroup$ – Markus Scheuer Jan 14 '18 at 13:32
  • $\begingroup$ (+1) Awesome! I didn't realize I had stumbled upon a special case of such a beautifully general formula! $\endgroup$ – Ant Jan 15 '18 at 0:51
  • $\begingroup$ I agree that it's a nice alternative approach, but I wonder why people don't like my answer which did everything in three lines.... $\endgroup$ – Aforest Jan 15 '18 at 5:29
  • 1
    $\begingroup$ @MarkusScheuer Thanks. I'd add some details to my answer when I have time. $\endgroup$ – Aforest Jan 15 '18 at 8:29

Using formal power series we have the Iverson bracket

$$[[0\le k\le n]] = [z^n] z^k \frac{1}{1-z}.$$

We then get for $A_n$

$$\sum_{k\ge 0} [z^n] z^k \frac{1}{1-z} {n+k\choose k} 2^k = [z^n] \frac{1}{1-z} \sum_{k\ge 0} z^k {n+k\choose n} 2^k \\ = [z^n] \frac{1}{1-z} \frac{1}{(1-2z)^{n+1}}.$$

This yields for $1+(-1)^n A_n$

$$1 + (-1)^n [z^n] \frac{1}{1-z} \frac{1}{(1-2z)^{n+1}} = 1 + [z^n] \frac{1}{1+z} \frac{1}{(1+2z)^{n+1}}$$

This is

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

Now the residue at infinity is zero by inspection and we get the closed form (residues sum to zero)

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

We evidently require (Leibniz rule)

$$\frac{1}{n!} \left(\frac{1}{z^{n+1}} \frac{1}{1+z} \right)^{(n)} \\ = \frac{1}{n!} \sum_{q=0}^n {n\choose q} \frac{(-1)^q (n+q)!}{n!} \frac{1}{z^{n+1+q}} \frac{(n-q)! (-1)^{n-q}}{(1+z)^{n-q+1}} \\ = (-1)^n \sum_{q=0}^n {n+q\choose q} \frac{1}{z^{n+1+q}} \frac{1}{(1+z)^{n-q+1}}.$$

Evaluate at $z=-1/2$ to get

$$(-1)^n \sum_{q=0}^n {n+q\choose q} (-2)^{n+1+q} 2^{n-q+1} = 2^{2n+2} \sum_{q=0}^n {n+q\choose q} (-1)^{q+1}.$$

Restoring the multiplier in front now yields

$$- \frac{1}{2^{n+1}} 2^{2n+2} \sum_{q=0}^n {n+q\choose q} (-1)^{q+1} = 2^{n+1} \sum_{q=0}^n {n+q\choose q} (-1)^{q}.$$

This is $2^{n+1} B_n$ as claimed.

  • $\begingroup$ (+1) Wow, nice! I love your formal power series solutions for these types of proofs. $\endgroup$ – Ant Jan 7 '18 at 23:59

Here is a proof of the general case below. My original answer is at the end.

$$\forall m,n\in\Bbb N,\ \forall x\in\Bbb R,\ \sum_{k=0}^{m}\binom{n+k}{k}(1-x)^kx^{n+1}=1-\sum_{k=0}^{n}\binom{m+k}{k}x^k(1-x)^{m+1}$$

Let $m,n\in\Bbb N$, $f:x\mapsto\sum_{k=0}^{m}\binom{n+k}{k}(1-x)^kx^{n+1}$, we have $f(0)=0$ and for all $x\in\Bbb R$, \begin{align} f'(x)&=(n+1)x^{n}\sum_{k=0}^{m}\binom{n+k}{k}(1-x)^k-x^{n+1}\sum_{k=0}^{m}\binom{n+k}{k}k(1-x)^{k-1}\\ &=x^{n}(1-x)^{m}\cdot A \end{align} where \begin{align} A&=\sum_{k=0}^{m}\binom{n+k}{k}(n+1)(1-x)^{k-m}-\sum_{k=0}^{m}\binom{n+k}{k}kx(1-x)^{k-m-1}\\ &=\sum_{k=0}^{m}\binom{n+k}{k}(n+k+1)(1-x)^{k-m}-\sum_{k=0}^{m}\binom{n+k}{k}k(1-x)^{k-m-1}\tag1\\ &=\sum_{k=1}^{m+1}\binom{n+k}{k}k(1-x)^{k-m-1}-\sum_{k=1}^{m}\binom{n+k}{k}k(1-x)^{k-m-1}\tag2\\ &=\binom{n+m+1}{m+1}(m+1)\\ &=\frac{(n+m+1)!}{n!\ m!} \end{align}



Thus, \begin{align} \forall x\in \Bbb R,\ f(x)&=A\int_0^xt^n(1-t)^mdt\\ &=A\int_{1-x}^1(1-s)^ns^mds\tag{$s=1-t$}\\ &=A\int_0^1(1-s)^ns^mds-A\int_0^{1-x}(1-s)^ns^mds\\ &=1-\sum_{k=0}^{n}\binom{m+k}{k}x^k(1-x)^{m+1}\tag3 \end{align}

$(3):$ integration by parts proves that $\int_0^1(1-s)^ns^mds=\frac{n!\ m!}{(n+m+1)!}=A^{-1}$, and $m\leftrightarrow n$ and $x\leftrightarrow 1-x$ in the expressions of $f$ give the second term.

Original answer:

The general formula of your question is $I_x(a,b)=1-I_{1-x}(b,a)$ where $I$ is the regularized incomplete beta function. The negative binomial distribution may also be helpful.

Note that $\forall n\in\Bbb N,\ \forall x\in\Bbb R,\ I_x(n+1,n+1)=\sum^{n}_{k=0}\binom{n+k}{k}(1-x)^kx^{n+1}$.

The question is to prove that $$\sum_{k=0}^{n}{{n+k}\choose{n}}2^k(-1)^{n+1}=1-\sum_{k=0}^{n}{{n+k}\choose{n}}(-1)^{k}2^{n+1}$$ which is a special case for $I_{-1}(n+1,n+1)=1-I_2(n+1,n+1)$.

  • $\begingroup$ Nice work! This proof is satisfying. I already (+1)'d when you first answered (yours was the only answer for quite a few hours), since the links you provided were informative (especially what the Wiki article mentioned about probability). Thanks for re-visiting the question and sharing this nice proof! $\endgroup$ – Ant Jan 20 '18 at 10:42

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.