# Prove that $(-1)^n\sum_{k=0}^{n}{{{n+k}\choose{n}}2^k}+1=2^{n+1}\sum_{k=0}^{n}{{{n+k}\choose{n}}(-1)^k}$

Define:

$$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:

$${\left(-1\right)}^nA_n+1=2^{n+1}B_n$$

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

• 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. – Sandeep Silwal Jan 6 '18 at 3:02
• Holy braces, Batman. Try not to overdo it with braces because it makes it difficult to clean up your TeX. – 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*}

Comment:

• 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*}

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

\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*}

• Beautiful ... this deserves more upvotes! – tired Jan 14 '18 at 13:29
• @tired: Many thanks for your nice comment. :-) – Markus Scheuer Jan 14 '18 at 13:32
• (+1) Awesome! I didn't realize I had stumbled upon a special case of such a beautifully general formula! – Ant Jan 15 '18 at 0:51
• 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.... – Aforest Jan 15 '18 at 5:29
• @MarkusScheuer Thanks. I'd add some details to my answer when I have time. – 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.

• (+1) Wow, nice! I love your formal power series solutions for these types of proofs. – 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}

$(1):-x(1-x)^{k-m-1}=(1-\frac1{1-x})(1-x)^{k-m}=(1-x)^{k-m}-(1-x)^{k-m-1}$

$(2):\binom{n+k}{k}(n+k+1)=\frac{(n+k+1)!}{n!k!}=\binom{n+k+1}{k+1}(k+1)$

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.

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