Show that $\sum_{k=1}^nk {n \choose 2k+1}=(n-2)2^{n-3}$

133 Views Asked by At

I am trying to show that $$\sum_{k=1}^nk {n \choose 2k+1}=(n-2)2^{n-3}.$$ When approaching these types of problems I always try to compute a few small, specific values myself just to get a better understanding of what the equation is doing. Also, induction is generally a good idea, so I would need to compute the base case anyways.

I try $n=1$: $$ \sum_{k=1}^1k {1 \choose 2k+1}= 1 {1 \choose 2(1)+1}={1 \choose 3}, $$ which doesn't make any sense because $n<k$. The answer is supposed to be $$(n-2)2^{n-3}=(1-2)^{1-3}=-1^{-2}=-\frac{1}{2},$$ which also doesn't make sense because choose notation never yields a fraction, so how am I to make sense of this problem, let alone prove it?

1

There are 1 best solutions below

0
On BEST ANSWER

It's easier to come up with a combinatorial proof of a formula for $\sum_{k=0}^{n}(2k+1)\binom{n}{2k+1}$ and a formula for $\sum_{k=0}^{n}\binom{n}{2k+1},$ then derive your formula by subtracting and dividing by $2.$

Basically, $\sum_{k=0}^{n}(2k+1)\binom{n}{2k+1}$ is the number of ways of selecting a committee of odd size with a chairperson selected from the committee. $\sum_{k=0}^{n}\binom{n}{2k+1}$ is the the number of ways to select an odd committee without a chair.

You can show that the first is $n2^{n-2},$ since you can first pick any chairperson and then select any even subset of the $n-1$ remaining. This is half the subsets (why?) so there are $2^{n-2}$ ways to pick the the rest of the committee. There are $2^{n-1}$ ways to pick just the committee without a chair.

So your sum is: $$\frac{n2^{n-2}-2^{n-1}}2=(n-2)2^{n-3}$$

Note, the committee with chair doesn't work when $n=1.$ The number of even subsets of of an empty set is $1,$ not $1/2.$

Also, note that $\sum_{k=0}^nk\binom{n}{2k+1}$ is the same as your sum since $k=0$ just contributes $0.$

There might be a more direct combinatorial argument, but I don't know what it is.