Prove an alternating binomial sum with odd weights

Question

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.

Answer 1

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.

Answer 2

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?

Answer 3

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.

Answer 4

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#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{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \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}^{1 + i}\pars{2n + 1 - 2i}{2n + 1 \choose i} \\[5mm] = &\ 2n + 1 + \color{#55f}{\sum_{i = 0}^{2n + 1}\pars{-1}^{1 + i}\pars{2n + 1 - 2i} {2n + 1 \choose i}} - \sum_{i = n + 1}^{2n + 1}\pars{-1}^{1 + i}\pars{2n + 1 - 2i} {2n + 1 \choose i} \end{align}

---

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