# Induction on binomial Identity

I am having trouble proving the following identity:

$0\cdot {n\choose 0} + 2\cdot {n\choose 2} + 4\cdot {n\choose4}+\ldots = n\cdot2^{n-2}$

Here is what I have so far:

Proof:

Base: Let $n=0$:

LHS: $0\cdot {0\choose 0} = 0\cdot1 = 0$

RHS: $0\cdot 2^{0-2} = 0$

Step: Let $k\in \mathbb{Z} s.t k \geq 0$ and assume the identity is true for k.

Consider the LHS for $k+1$ where $k$ is even (I leave out the odd case because I think it will turn out the same?):

\begin{align} =& 0\cdot{k+1\choose 0}+2\cdot{k+1\choose 2}+4\cdot{k+1\choose 4}+... +k\cdot{k+1\choose k} \\=&0\cdot\left[{k\choose 0}+{k\choose -1}\right] + 2\cdot\left[{k\choose 2}+{k\choose 1}\right]+ 4\cdot\left[{k\choose 4}+{k\choose 3}\right]+\ldots+ k\cdot\left[{k\choose k}+{k\choose k-1}\right] \\=&\left[0\cdot{k\choose 0}+2\cdot {k\choose 2}+4\cdot{k\choose 4}+\ldots+k\cdot{k\choose k}\right] + \left[0\cdot{k\choose -1}+ 2\cdot {k\choose 1}+4\cdot {k\choose 3}+\ldots+k\cdot{k\choose k-1}\right] \\=& k\cdot2^{k-2} + \left[0\cdot{k\choose -1}+ 2\cdot {k\choose 1}+4\cdot {k\choose 3}+\ldots+k\cdot{k\choose k-1}\right] \\ \end{align} I know I need to end up with something like: \begin{align} =&k\cdot2^{k-2}+ \left[k\cdot2^{k-2} + 2^{k-1}\right] \\=&2k\cdot 2^{k-2} + 2^{k-1} \\=&k\cdot 2^{k-1}+2^{k-1} \\=&(k+1)\cdot 2^{k-1}\end{align}

But, how can I get what I need from the combinations above? It may not end up exactly like that, but what is the reasoning behind this?

-

A non-inductive proof now. We have: $$\sum_{0 \le k \le n} \binom{n}{k} z^k = (1 + z)^n$$ So we also have: $$\sum_{0 \le k \le \lfloor n / 2 \rfloor} \binom{n}{2 k} z^{2 k} = \frac{(1 + z)^n + (1 - z)^n}{2}$$ If you differentiate this with respect to $z$ you get: $$\sum_{0 \le k \le \lfloor n / 2 \rfloor} 2 k \binom{n}{2 k} z^{2 k - 1} = \frac{n (1 + z)^{n - 1} - n (1 - z)^{n - 1}}{2}$$ Then evaluate at $z = 1$ you get the requested sum: $$\sum_{0 \le k \le \lfloor n / 2 \rfloor} 2 k \binom{n}{2 k} = \frac{n 2^{n - 1}}{2} = n 2^{n - 2}$$

-
Generating functions help in many combinatoric identities –  robjohn Feb 5 '13 at 8:07
Can you explain how you got from the binomial theorem to the second line? I sort of understand the factor of $\dfrac{1}{2}$ since we only sum up $\left\floor{\dfrac{n}{2}\right\floor}$ binomial coefficients, but the rest I cannot figure out. –  CodeKingPlusPlus Feb 5 '13 at 17:25
The TeX is supposed to say " sum up $\left\lfloor\dfrac{n}{2}\right\rfloor$ binomial coefficients –  CodeKingPlusPlus Feb 5 '13 at 17:39
@CodeKingPlusPlus, thanks for the comments. Edited to match. –  vonbrand Feb 5 '13 at 18:10
@CodeKingPlusPlus, $(1 + z)^n$ has all terms positive, 1 - z)^n has odd terms negative. Add both, and the odd terms cancel out. – vonbrand Feb 5 '13 at 18:36 This is no longer really a hint: the induction step ended up messy enough that I went ahead and wrote it out, though the internal induction has only been indicated, not actually carried out properly. For the main induction step: \begin{align*} \sum_{k\ge 0}2k\binom{n+1}{2k}&=\sum_{k\ge 0}2k\left(\binom{n}{2k}+\binom{n}{2k-1}\right)\\\\ &=n2^{n-2}+\sum_{k\ge 0}2k\binom{n}{2k-1}\\\\ &=n2^{n-2}+\sum_{k\ge 0}2k\left(\binom{n-1}{2k-1}+\binom{n-1}{2k-2}\right)\\\\ &=n2^{n-2}+\sum_{k\ge 0}2k\binom{n-1}{2k-2}+\sum_{k\ge 0}2k\binom{n-1}{2k-1}\\\\ &=n2^{n-2}+\sum_{k\ge 0}(2k+2)\binom{n-1}{2k}+\sum_{k\ge 0}2k\binom{n-1}{2k-1}\\\\ &=n2^{n-2}+\sum_{k\ge 0}2k\binom{n-1}{2k}+2\sum_{k\ge 0}\binom{n-1}{2k}+\sum_{k\ge 0}2k\binom{n-1}{2k-1}\\\\ &=n2^{n-2}+(n-1)2^{n-3}+2^{n-1}+\sum_{k\ge 0}2k\binom{n-1}{2k-1}\;. \end{align*} Notice that the last term of the last line is just like the last term of the second line, but with the upper number in the binomial coefficients reduced by1. This suggests that we should look at both $$\sum_{k\ge 0}2k\binom{n}{2k}\quad\text{and}\quad\sum_{k\ge 0}2k\binom{n}{2k-1}$$ simultaneously. They’re a bit awkward to write, so I’ll introduce a couple of abbreviations: let $$f(n)=\sum_{k\ge 0}2k\binom{n}{2k}\quad\text{and}\quad g(n)=\sum_{k\ge 0}2k\binom{n}{2k-1}\;.$$ What’s been done already can be summed up as $$f(n+1)=n2^{n-2}+(n-1)2^{n-3}+2^{n-1}+g(n-1)\;,$$ and along the way we found that $$g(n)=(n-1)2^{n-3}+2^{n-1}+g(n-1)\;.$$ A straightforward induction now shows that \begin{align*} f(n+1)&=n2^{n-2}+(n-1)2^{n-3}+2^{n-1}+g(n-1)\\ &=n2^{n-2}+(n-1)2^{n-3}+(n-2)2^{n-4}+2^{n-1}+2^{n-2}+g(n-2)\\ &\;\vdots\\ &=\sum_{k=2}^nk2^{k-2}+\sum_{k=2}^{n-1}2^k+g(2)\\\\ &=\sum_{k=0}^{n-2}(k+2)2^k+4\sum_{k=0}^{n-3}2^k+4\\\\ &=n2^{n-2}+\sum_{k=0}^{n-3}(k+6)2^k+4\\\\ &=n2^{n-2}+\sum_{k=1}^{n-3}k2^k+6\sum_{k=0}^{n-3}2^k+4\\\\ &=n2^{n-2}+\sum_{k=1}^{n-3}\sum_{i=1}^k2^k+6\left(2^{n-2}-1\right)+4\\\\ &=(n+6)2^{n-2}+\sum_{i=1}^{n-3}\sum_{k=i}^{n-3}2^k-2\\\\ &=(n+6)2^{n-2}+\sum_{i=1}^{n-3}\left(\left(2^{n-2}-1\right)-\left(2^i-1\right)\right)-2\\\\ &=(n+6)2^{n-2}+\sum_{i=1}^{n-3}\left(2^{n-2}-2^i\right)-2\\\\ &=(n+6)2^{n-2}+(n-3)2^{n-2}-\sum_{i=1}^{n-3}2^i-2\\\\ &=(2n+3)2^{n-2}-\left(2^{n-2}-2\right)-2\\\\ &=(2n+2)2^{n-2}\\\\ &=(n+1)2^{n-1}\;. \end{align*} Added: Note that a combinatorial proof is also possible. A term2k\dbinom{n}{2k}$on the lefthand side is the total number of elements in$2k$-element subsets of$[n]$if each is counted once for each$2k$-element set in which it appears. Thus, the lefthand side counts each element of$[n]$once for each even-sized subset of$[n]$in which it appears. Fix an element$a\in[n]$. There is an obvious bijection between the even-sized subsets of$[n]$containing$a$and the odd-sized subsets of$[n]\setminus\{a\}$.$[n]\setminus\{a\}$has$2^{n-1}$subsets, so it has$2^{n-2}$odd-sized subsets. Thus,$a$appears in$2^{n-2}$even-sized subsets of$[n]$. The righthand side of the identity sums this figure over all$n$elements of$[n]$. - Can you explain the reasoning from line 2 to line 3? I don't immediately see the algebra work out or a combinatorial argument. – CodeKingPlusPlus Feb 5 '13 at 4:30 @CodeKingPlusPlus: You can’t see it because it’s wrong: I made a foolish mistake. I’m going to delete that part of the answer while I fix it. – Brian M. Scott Feb 5 '13 at 4:50 I don't see in the first part how you get in lines 4 to 5 that:$\sum\limits_{k \geq 0}^{}2k{n-1\choose 2k-2} = \sum\limits_{k \geq 0}^{}2k+2{n-1\choose 2k}$I let$n=5$and$k=2$and got the LHS =$24$and RHS =$6$– CodeKingPlusPlus Feb 5 '13 at 16:37 @CodeKingPlusPlus: You’re missing some parentheses: the RHS is$\sum_{k\ge 0}(2k+2)\binom{n-1}2k$. It’s just an index shift. If you prefer, let$j=k-1$then the LHS is$\sum_{j\ge -1}2(j+1)\binom{n-1}{2j}=\sum_{j\ge 0}(2j+2)\binom{n-1}{2j}$; now let$k=j$, and it becomes the RHS. And since they’re sums over$k$you can’t check equality for a specific$k$. When$n=5\$, LHS is $$0\binom4{-2}+2\binom40+4\binom42+6\binom44=0+2+24+6=32\;,$$ and RHS is $$2\binom40+4\binom42+6\binom44=2+24+6=32\;.$$ –  Brian M. Scott Feb 5 '13 at 21:21

Here is a proof, which relies on induction indirectly. Note that $$2k \dbinom{n}{2k} = 2k \dfrac{n!}{(n-2k)!(2k)!} = n \dfrac{(n-1)!}{(n-2k)!(2k-1!)} = n \dbinom{n-1}{2k-1}$$ Hence, $$\sum_{k=1}^{\lfloor n/2 \rfloor} 2k \dbinom{n}{2k} = n\sum_{k=1}^{\lfloor n/2 \rfloor} \dbinom{n-1}{2k-1}$$ Now note that $$(1+1)^{n-1} = \sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n-1}{2k} + \sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n-1}{2k-1} \,\,\,\,\, (\heartsuit)$$ and $$(1-1)^{n-1} = \sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n-1}{2k} - \sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n-1}{2k-1} \,\,\,\,\, (\spadesuit)$$ Hence, $$(\heartsuit) - (\spadesuit) \implies 2 \sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n-1}{2k-1} = 2^{n-1}$$ Hence, $$\sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n-1}{2k-1} = 2^{n-2}$$ Therefore, we get $$\sum_{k=1}^{\lfloor n/2 \rfloor} 2k \dbinom{n}{2k} = n\sum_{k=1}^{\lfloor n/2 \rfloor} \dbinom{n-1}{2k-1} = n2^{n-2}$$

-

Unlike with other proof methods, proofs by induction sometimes become easier if you make the statement to be proved stronger. In the present case, it seems that your approach should be successful if you add a corresponding statement about the sum of binomial coefficients with odd lower arguments to the claim:

$$\sum_{j=1}^{\lceil n/2\rceil}2j\binom n{2j-1}=2^{n-2}(n+2)\;.$$

-

Add the first two to get the third: \begin{align} \sum_{k=0}^nk\binom{n}{k}&=\sum_{k=0}^nn\binom{n-1}{k-1}&=n(1+1)^{n-1}&=n2^{n-1}\\ \sum_{k=0}^n(-1)^kk\binom{n}{k}&=\sum_{k=0}^n(-1)^kn\binom{n-1}{k-1}&=n(1-1)^{n-1}&=0\\ \sum_{k=0}^{\lfloor n/2\rfloor}2k\binom{n}{2k}&&&=n2^{n-1}\\ \end{align}

-