# Formula for $\sum_{i\geq 0} i{n \choose 2i}$?

So I know that $\sum_{i\geq 0}{n \choose 2i}=2^{n-1}=\sum_{i\geq 0}{n \choose 2i-1}$. However, I need formulas for $\sum_{i\geq 0}i{n \choose 2i}$ and $\sum_{i\geq 0}i{n \choose 2i-1}$. Can anyone point me to a formula with proof for these two sums? My searches thus far have only turned up those first two sums without the $i$ coefficient in the summand. Thanks!

• Hints: Do you know the formula for the generating polynomial $\sum_i {n \choose 2i} x^i$? Do you know how to get at the sum of $i$ times the $x^i$ coefficient of a polynomial? – Noam D. Elkies Jun 17 '16 at 3:27
• $\sum_{i\ \geq\ 0}{n \choose 2i} = 2^{n - 1} + {1 \over 2}\,\delta_{n0}$ to agree with the case $n = 0$. – Felix Marin Jun 19 '16 at 8:36

## 3 Answers

Here’s a solution not using generating functions. Let

$$a_n=\sum_kk\binom{n}{2k}\;,$$

the first of your two sums. Suppose that you have a pool of players numbered $1$ through $n$; then $k\binom{n}{2k}$ is the number of ways to choose $2k$ players from the pool to form a team and then designate one of the lowest-numbered $k$ on the team as the captain. Thus, $a_n$ is the number of ways to pick a team with an even number of members and designate one member of the lower-numbered half of the team to be the captain. Note that $k=0$ contributes $0$ to $a_n$, so we may as well consider only $k\ge 1$.

We can choose team and captain in a different way, however. We first pick the player who will be the highest-numbered player in the lower half; if that player’s number is $\ell$, we must have $1\le\ell\le n-1$. For some $k$ between $1$ and $n-\ell$ inclusive we then pick $k$ players numbered above $\ell$ and $k-1$ players numbered below $\ell$. Finally, we pick one of the $k$ chosen players numbered $\ell$ or lower to be the captain. For a given $\ell$ and $k$ this can be done in $k\binom{n-\ell}k\binom{\ell-1}{k-1}$ different ways. Thus,

\begin{align*} a_n&=\sum_{\ell=1}^{n-1}\sum_{k=1}^{n-\ell}k\binom{n-\ell}{k}\binom{\ell-1}{k-1}\\ &=\sum_{\ell=1}^{n-1}(n-\ell)\sum_k\binom{n-1-\ell}{k}\binom{\ell-1}k\tag{1}\\ &=\sum_{\ell=1}^{n-1}(n-\ell)\sum_k\binom{n-1-\ell}{k}\binom{\ell-1}{\ell-1-k}\\ &=\sum_{\ell=1}^{n-1}(n-\ell)\binom{n-2}{\ell-1}\tag{2}\\ &=\sum_{\ell=0}^{n-2}(n-1-\ell)\binom{n-2}\ell\\ &=(n-1)2^{n-2}-\sum_\ell\ell\binom{n-2}\ell\\ &=(n-1)2^{n-2}-(n-2)2^{n-3}\\ &=n2^{n-3}\;. \end{align*}

To get $(1)$ I used the identity $m\binom{n}m=n\binom{n-1}{m-1}$ and shifted the index $k$ by one; there’s no need to specify limits on the inner summation, because examination shows that it’s over all values of $k$ that yield non-zero terms. $(2)$ follows from the Vandermonde identity.

The formula $a_n=n2^{n-3}$ is valid for $n\ge 2$, and clearly $a_0=a_1=0$.

Your second sum is

$$b_n=\sum_{k\ge 0}k\binom{n}{2k-1}=\sum_{k\ge 1}k\binom{n}{2k-1}=\sum_{k\ge 0}(k+1)\binom{n}{2k+1}\;.$$

This corresponds to choosing an odd number $2k+1$ of players for your team and naming a captain from the lowest-numbered $k+1$ members of the team. The alternative calculation is almost the same as before: $\ell$ is the number of the player in the middle of the team when it’s arranged by number, which can be anything from $1$ to $n$ inclusive, and

\begin{align*} b_n&=\sum_{\ell=1}^n\sum_{k=0}^{n-\ell}(k+1)\binom{n-\ell}{k}\binom{\ell-1}k\\ &=\sum_{\ell=1}^n\sum_{k=0}^{n-\ell}k\binom{n-\ell}k\binom{\ell-1}k+\sum_{\ell=1}^n\sum_{k=0}^{n-\ell}\binom{n-\ell}k\binom{\ell-1}k\\ &=\sum_{\ell=1}^n(n-\ell)\sum_k\binom{n-1-\ell}{k-1}\binom{\ell-1}k+\sum_{\ell=1}^n\binom{n-1}{\ell-1}\\ &=\sum_{\ell=1}^n(n-\ell)\sum_k\binom{n-1-\ell}k\binom{\ell-1}{k+1}+2^{n-1}\\ &=\sum_{\ell=1}^n(n-\ell)\sum_k\binom{n-1-\ell}k\binom{\ell-1}{\ell-2-k}+2^{n-1}\\ &=\sum_{\ell=1}^n(n-\ell)\binom{n-2}{\ell-2}+2^{n-1}\\ &=n\sum_\ell\binom{n-2}\ell-\sum_{\ell=1}^n\ell\binom{n-2}{\ell-2}+2^{n-1}\\ &=n2^{n-2}-\sum_\ell(\ell+2)\binom{n-2}\ell+2^{n-1}\\ &=n2^{n-2}-2\sum_\ell\binom{n-2}\ell-\sum_\ell\ell\binom{n-2}\ell+2^{n-1}\\ &=n2^{n-2}-2^{n-1}-(n-2)\sum_\ell\binom{n-3}{\ell-1}+2^{n-1}\\ &=n2^{n-2}-(n-2)2^{n-3}\\ &=(n+2)2^{n-3}\;, \end{align*}

valid for $n\ge 2$. Clearly $b_1=1$.

As a matter of possible interest, these sequences are essentially OEIS A001792 and OEIS A045623, though with different starting points in each case. Thus, $a_n$ turns out to be (among many other things) the number of parts in all compositions of $n-1$, and $b_n$ to be the number of ones in all compositions of $n$. Many other interpretations and many references can be found at the OEIS links.

It’s also not hard to verify that $\sum_{k=1}^nb_k=a_{n+1}$ for $n\ge 1$.

So for n even you can use ${n \choose 2i} = {n \choose n-2i}$ to rewrite the sum as $\sum_i i {n \choose n-2i}$ then add this sum to the original sum to get $\sum_i n{n \choose n-2i}$

$\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}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \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{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

Just one !!!. The other ones are similar to the present one.

\begin{align} \color{#f00}{\sum_{i\ \geq\ 0}i{n \choose 2i}} & = \half\sum_{i\ \geq\ 1}2i{n \choose 2i} = \half\sum_{i\ \geq\ 1}i{n \choose i}{1 + \pars{-1}^{i} \over 2} \\[3mm] & = \left.{1 \over 4}\,\partiald{}{x}\sum_{i\ \geq\ 1}{n \choose i}x^{i} \right\vert_{\ x\ =\ 1} - \left.{1 \over 4}\,\partiald{}{x}\sum_{i\ \geq\ 1}{n \choose i}x^{i} \right\vert_{\ x\ =\ -1} \\[3mm] & = \left.{1 \over 4}\,\partiald{}{x}\bracks{\pars{1 + x}^{n} - 1} \right\vert_{\ x\ =\ 1} - \left.{1 \over 4}\,\partiald{}{x}\bracks{\pars{1 + x}^{n} - 1} \right\vert_{\ x\ =\ -1} \\[3mm] & = {1 \over 4}\,n\,2^{n - 1} - {1 \over 4}\,n\,\delta_{n1} = \color{#f00}{{1 \over 4}\pars{2^{n - 1}n - \delta_{n1}}} \end{align}