# Prove an alternating binomial sum with odd weights

How can the following identity for positive integer $n$ be proved? It has been confirmed symbolically by Mathematica:

$$\sum_{i=1}^n (-1)^{1+i} (2n+1-2i) \binom{2n+1}{i} = 2n + 1$$

Induction seems quite cumbersome as $n$ appears in three instances on the left hand side. Also the usual binomial sum identities have an upper limit equal to the upper number in the binomial coefficient, whereas here these are $n$ and $2n+1$ respectively.

Background. This identity arose from a series expansion where the functions $U_k(\phi)$ recursively satisfy a differential equation depending on $U_{k-2}(\phi)$. After computing the first few by hand, I was able to see the pattern, and proceeded to prove it by induction. However for odd $k \ge 3$, this involved showing the identity

$$\sum_{\substack{j=1 \\ \text{j odd}}}^{k-2} (-1)^{(j-1)/2} \frac{2j}{(k-j)!!(k+j)!!} = (-1)^{(k+1)/2} \frac{2k}{(2k)!!}.$$

After rearranging and expanding the double factorials in terms of single factorials, obtained me

$$\sum_{\substack{j=1 \\ \text{j odd}}}^{k-2} (-1)^{(j+k)/2} \frac{j}{k} \binom{k}{(k-j)/2} = 1.$$

Putting $j = 2i-1$ and $k = 2n+1$ gives

$$\sum_{i=1}^n (-1)^i (2i-1) \binom{2n+1}{n+1-i} = (-1)^n (2n+1),$$

and writing the sum backwards (i.e. replacing $i$ by $n+1-i$) yields the above.

There is a slick answer using generating functions.

Subtracting the $2n+1$ over, and negating, this is equivalent to proving $$\sum_{i=0}^n\underbrace{(-1)^{i}\binom{2n+1}{i}}_{a_i}\underbrace{(2(n-i)+1)}_{b_{n-i}}=0$$ where I have given names to certain parts of the summation. We are trying to prove that the convolution of the sequences $a_i$ and $b_i$ is equal to zero. The generating function of the convolution is equal to the product of the generating functions for $a_i$ and $b_i$, so let us compute those: $$A(x) =\sum_{i=0}^\infty a_ix^i= \sum_{i=0}^\infty \binom{2n+1}{i}(-1)^ix^i = (1-x)^{2n+1}$$ $$B(x) =\sum_{i=0}^\infty b_ix^i= \sum_{i=0}^\infty(2i+1)x^i = 2\cdot\frac{x}{(1-x)^2}+\frac{1}{(1-x)}=\frac{1+x}{(1-x)^2}$$ Multiplying these, the sum we are trying to compute is the coefficient of $x^n$ in $$A(x)B(x) = (1+x)(1-x)^{2n-1}=\color{blue}{(1-x)^{2n-1}}+\color{green}{x(1-x)^{2n-1}}$$ The $x^n$ coefficient of $\color{blue}{(1-x)^{2n-1}}$ is $\binom{2n-1}{n}(-1)^n$, and the $x^n$ coefficient of $\color{green}{x(1-x)^{2n-1}}$ is the $x^{n-1}$ coefficient of $(1-x)^{2n-1}$ is equal to $(-1)^{n-1}\binom{2n-1}{n-1}$. Notice these are both central binomial coefficients with opposite signs, so their sum is zero.

• GFs rulez! (+1) – tired Apr 22 '18 at 19:09

Putting the right-hand side $2n+1$ to the left and multiplying the equation with $-1$ transforms the claim into

The following is valid for $n\geq 0$: \begin{align*} \sum_{i=0}^n(-1)^i(2n+1-2i)\binom{2n+1}{i}=0 \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{i=0}^n}&\color{blue}{(-1)^i(2n+1-2i)\binom{2n+1}{i}}\\ &=(2n+1)\sum_{i=0}^n(-1)^i\binom{2n+1}{i}-2(2n+1)\sum_{i=1}^n(-1)^i\binom{2n}{i-1}\tag{1}\\ &=(2n+1)\left[1+\sum_{i=1}^n(-1)^i\binom{2n}{i}-\sum_{i=1}^n(-1)^i\binom{2n}{i-1}\right]\tag{2}\\ &=(2n+1)\left[\sum_{i=0}^n(-1)^i\binom{2n}{i}+\sum_{i=0}^{n-1}(-1)^i\binom{2n}{i}\right]\tag{3}\\ &=(2n+1)\left[\sum_{i=0}^n(-1)^i\binom{2n}{i}+\sum_{i=0}^{n-1}(-1)^i\binom{2n}{2n-i}\right]\tag{4}\\ &=(2n+1)\sum_{i=0}^{2n}(-1)^i\binom{2n}{i}\tag{5}\\ &=(2n+1)(1-1)^{2n}\\ &\,\,\color{blue}{=0} \end{align*} and the claim follows.

Comment:

• In (1) we multiply out and use for the right-hand sum the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

• In (2) we factor out $2n+1$. We separate from the left-hand sum the first term (with $i=0$) and apply to the left-hand sum the binomial identity $\binom{p+1}{q}=\binom{p}{q}+\binom{p}{q-1}$.

• In (3) we put the summand $1$ back to the left-hand sum and shift the index of the right-hand sum by one to start with $i=0$.

• In (4) we apply the binomial identity $\binom{p}{q}=\binom{p}{p-q}$ to the right-hand sum.

• In (5) we observe that the sums can be nicely merged.


Note that the $\ds{\color{#55f}{\textsf{first sum}}}$, in the last line, $\ds{\underline{\texttt{vanishes out}}}$: \begin{align} &\color{#55f}{\sum_{i = 0}^{2n + 1}\pars{-1}^{1 + i}\pars{2n + 1 - 2i} {2n + 1 \choose i}} = \left.\partiald{}{x}\sum_{i = 0}^{2n + 1}\pars{-1}^{1 + i} {2n + 1 \choose i}x^{2n + 1 - 2i}\,\right\vert_{\ x\ =\ 1} \\[5mm] = &\ -\,\partiald{}{x}\bracks{x^{-2n - 1}\pars{x^{2} - 1}^{2n + 1}}_{\ x\ =\ 1} = \color{red}{\large 0} \end{align} such that \begin{align} &\bbox[10px,#ffd]{\ds{\sum_{i = 1}^{n}\pars{-1}^{1 + i}\pars{2n + 1 - 2i}{2n + 1 \choose i}}} = 2n + 1 + \sum_{i = 0}^{n}\pars{-1}^{i + n}\pars{2i + 1} {2n + 1 \choose i + n + 1} \\[5mm] = &\ 2n + 1 - \sum_{i = 0}^{n}\pars{-1}^{i + 1}\pars{2n -2i + 1} {2n + 1 \choose 2n + 1 - i} \\[5mm] = &\ 2n + 1 - \sum_{i = 0}^{n}\pars{-1}^{i + 1}\pars{2n -2i + 1}{2n + 1 \choose i} \\[5mm] = &\ 2n + 1 - \bracks{-\pars{2n + 1} + \bbox[10px,#ffd]{\ds{\sum_{i = 1}^{n}\pars{-1}^{i + 1}\pars{2n -2i + 1}{2n + 1 \choose i}}}} \end{align}
Then, $$\bbx{% \bbox[10px,#ffd]{\ds{\sum_{i = 1}^{n}\pars{-1}^{1 + i}\pars{2n + 1 - 2i}{2n + 1 \choose i}}} = 2n + 1}$$

We may write:

$$\sum_{i=1}^n (-1)^{1+i} (2n+1-2i) \binom{2n+1}{i} = 2\sum_{i=1}^n (-1)^{i} i \binom{2n+1}{i} - (2n+1) \sum_{i=1}^n (-1)^{i} \binom{2n+1}{i} .$$

Now, we have

$$(2n+1) \sum_{i=1}^n (-1)^{i} \binom{2n+1}{i} = (-1)^n(n+1)\binom{2n+1}{n+1}-(2n+1) \tag{1}$$

and

$$2\sum_{i=1}^n (-1)^{i} i \binom{2n+1}{i} = (-1)^n(n+1)\binom{2n+1}{n+1} \tag{2}.$$

Can you see how?

Hint for $(2)$:
Use differentiation and Newton's binomial theorem to show that

$$\sum_{k=0}^{2n+1}\,k\,x^k\,\binom{2n+1}k = (2n+1)\,x\,(x+1)^{2n}\tag{3}.$$

Now, observe that for all $0\leq k \leq n$ we have $\binom{2n+1}{n+1+k} = \binom{2n+1}{n-k}$ and write

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

Now, change indices with $i = n-k$ and obtain that

\begin{align} \sum_{k=0}^{2n+1}\,k\,{(-1)}^k\,\binom{2n+1}k &= \sum_{i=0}^{n}\,(-1)^{i+1}\,\big((2n+1)-2i\big)\,\binom{2n+1}{i} \\&= 2\,\sum_{i=0}^{n}\,(-1)^{i}\,i\,\binom{2n+1}{i} - (2n+1)\,\sum_{i=0}^{n}\,(-1)^{i}\,\binom{2n+1}{i} \end{align}

Using $(1)$ and $(3)$, can you conclude?

• I see that the former can be obtained using a "truncated alternating binomial sum", as in (887960), (947817); did you obtain this with a different method? Also how is the latter obtained? – lastresort Apr 22 '18 at 9:10
• I have edited my answer with a hint for $(2)$. – Fimpellizieri Apr 22 '18 at 18:19
• I understand now. Thank you for your edit. – lastresort Apr 23 '18 at 3:12
• Actually, one can get the result straight from this expansion, in the hint, without first having to show that $(1)$ is true. Up to the value for the index $i=0$, the expansion is exactly what is being asked. – Fimpellizieri Apr 23 '18 at 5:30