2
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Noam D. Elkies Jun 17 '16 at 3:27
  • $\begingroup$ $\sum_{i\ \geq\ 0}{n \choose 2i} = 2^{n - 1} + {1 \over 2}\,\delta_{n0}$ to agree with the case $n = 0$. $\endgroup$ – Felix Marin Jun 19 '16 at 8:36
1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.