Simplification of ${0 \binom{n}{0} + 2 \binom{n}{2} + 4 \binom{n}{4} + 6 \binom{n}{6} + \cdots}$

Question

Simplify $$0 \binom{n}{0} + 2 \binom{n}{2} + 4 \binom{n}{4} + 6 \binom{n}{6} + \cdots,$$ where $n \ge 2.$

I think we can write this as the summation $\displaystyle\sum_{i=0}^{n} 2i\binom{n}{2i},$ which simplifies to $\boxed{n\cdot2^{n-2}}.$ Am I on the right track?

Answer 1

Sure. Notice that $$\sum _{i = 0}^{n}2i\binom{n}{2i}=\sum _{i = 0}^{n}\binom{2i}{1}\binom{n}{2i}=\sum _{i = 1}^{n}\binom{n}{1}\binom{n-1}{2i-1}=n\sum _{i=1}^n\binom{n-1}{2i-1}=n\cdot 2^{n-2}.$$ Notice that the last step is because you are adding half of the binomials, and the odd half equals the even half by the binomial theorem.

Answer 2

A combinatorial proof is in order!

The given expression is the number of ways to choose an even-sized subset of $n$ people, and promote one of them to be the leader. Notice that $n\cdot 2^{n-2}$ is the number of ways to choose the leader first, then choose an odd-sized subset from the remaining $n-1$ people (as the number of odd-sized subsets is the same as the number of even-sized ones). Hence the two sides are equal.

Answer 3

Spoilered answer:

$$\sum_{i} 2i \binom{n}{2i}=n\sum_{i} \binom{n-1}{2i-1}= n2^{n-2}$$

To get the second equaltiy note that $\sum_{i}\binom{n-1}{2i-1}=\sum_{i} \binom{n-1}{2i}$ as results from writing the binomial formula for $(1-1)^{n-1}$, and recall that $$\sum_{i}\binom{n-1}{2i-1}+\sum_{i} \binom{n-1}{2i}= \sum_{i} \binom{n-1}{i}= 2^{n-1}$$ as follows from using binomial formula for $(1+1)^{n-1}$.

Answer 4

Let $S$ be the sum in question.

Let $f(x)=(1+x)^n+(1-x)^n$. Then $f'(1)=2S$.

Now $f'(x)=n(1+x)^{n-1}-n(1-x)^{n-1}$ and so $f'(1)=n 2^{n-1}$.

Therefore, $S=n 2^{n-2}$.

Answer 5

One more answer for variety! This one uses nothing but Pascal's identity and the symmetric identity! (Assuming you already know that the sum of row $n$ is $2^n$, which can also be proved only using Pascal's identity.)

---

Visual interpretation

I think this proof is easiest to visualize on Pascal's triangle. Let's look at these identities graphically on Pascal's triangle:

Pascal's identity: $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Symmetric identity: $$\binom{n}{k} = \binom{n}{n-k}$$

Proof

Instead of calculating the sum shown, I will calculate half of it. (This way, the multipliers are $0$, $1$, $2$, etc. which will make it easier to see the pattern.)

Apply Pascal's identity. The number inside the circle represents the multiplier of that particular binomial coefficient. Each row has the same sum.

Next, we can reallocate the multipliers if the binomial coefficients are equal. Apply the symmetric identity:

For this specific example used, $n=8$. The constant multiplier at row $n-3$ is $n$.

The sum of row $n-3$ is therefore $n2^{n-3}$. Since we halved the sum initially, we double it to obtain our final answer: $$n2^{n-2}$$

Reflection

Although this proof seems kind of involved, visualizing the repeated differences/sums this way I think is a good exercise because it is very elementary, so it is a good fallback technique without any need to invoke derivatives or constructing a counting proof.

Answer 6

Here's an alternative approach, motivated by the appearance of even numbers in the summand. Because $$\frac{1+(-1)^k}{2}=\begin{cases}1&\text{if $k$ is even}\\0&\text{if $k$ is odd}\end{cases}$$ we have $$\sum_{k\ge 0} a_{2k} = \sum_{k\ge 0} a_k \frac{1+(-1)^k}{2}.$$ Now take $a_k=k\binom{n}{k}$ to obtain \begin{align} \sum_{k\ge 0} 2k\binom{n}{2k} &=\sum_{k\ge 0} k\binom{n}{k}\frac{1+(-1)^k}{2} \\ &=\sum_{k\ge 1} n\binom{n-1}{k-1}\frac{1+(-1)^k}{2} \\ &=\frac{n}{2}\sum_{k\ge 1} \binom{n-1}{k-1} +\frac{n}{2}\sum_{k\ge 1} \binom{n-1}{k-1}(-1)^k \\ &=\frac{n}{2}2^{n-1} +\frac{n}{2}(1-1)^{n-1} \\ &=\frac{n}{2}2^{n-1} +\frac{n}{2}[n=1] \\ &=n2^{n-2} \end{align} for $n \ge 2$.