How do I evaluate the sum:$${n \choose 1} + 3{n \choose 3} +5{n \choose 5} + 7{n \choose 7} ...$$in closed form? I don't really know how to start and approach this question. Any help is greatly appreciated.

  • 1
    $\begingroup$ Once the problem of the range of the summation is settled, use the (often mentioned on this site) identity $$j{n\choose j}=n{n-1\choose j-1}.$$ $\endgroup$ – Did Jul 4 '14 at 16:17
  • $\begingroup$ @Did Please look at my updated question $\endgroup$ – Vishwa Iyer Jul 4 '14 at 16:22
  • $\begingroup$ I have. Please spend 5 minutes to find one of the many questions already on the site and asking this. $\endgroup$ – Did Jul 4 '14 at 16:23
  • $\begingroup$ @Did I have indeed searched the site and I have not found any question that's the same as this one, which is the reason i'm asking the question in the first place. $\endgroup$ – Vishwa Iyer Jul 4 '14 at 16:26
  • $\begingroup$ @Did based on your first comment, my sum would basically be $$n{n-1 \choose 0} + n{n-1 \choose 2} + n{n-1 \choose 4} + ...$$ Since (based on the answers and comments) the sum of the even binomial coefficients is $2^{n-1 -1} = 2^{n-2}$, the sum evaluates to $n*2^{n-2}$. $\endgroup$ – Vishwa Iyer Jul 4 '14 at 16:54

Starting with \begin{align} (1+t)^{n} = \sum_{k=0}^{n} \binom{n}{k} t^{k} \end{align} it is seen that \begin{align} \frac{1}{2} \left[ (1+t)^{n} - (1-t)^{n} \right] = \sum_{k=1}^{[(n+1)/2]} \binom{n}{2k-1} t^{2k-1}. \end{align} Now differentiating both sides leads to \begin{align} \sum_{k=1}^{[(n+1)/2]} (2k-1) \binom{n}{2k-1} t^{2k-2} = \frac{n}{2} \left[ (1+t)^{n-1} + (1-t)^{n-1} \right] \end{align} and upon setting $t=1$ the desired result is \begin{align} \sum_{k=1}^{[(n+1)/2]} (2k-1) \binom{n}{2k-1} = 2^{n-2} \ n. \end{align}


Hint: We have $\binom{n}{2k-1}=\frac{n}{2k-1}\binom{n-1}{2k-2}$.

Note that $\binom{a}{b}=0$ if $b\gt a$.

  • $\begingroup$ Please look at my updated question. $\endgroup$ – Vishwa Iyer Jul 4 '14 at 16:22
  • $\begingroup$ There are several approaches, of which I mentioned one. You will end up with $n$ times the sum of the even-numbered binomial coefficients for $n-1$. The sum of the even-numbered binomial coefficients is the same as the sum of the odd-numbered ones. $\endgroup$ – André Nicolas Jul 4 '14 at 16:27
  • $\begingroup$ As insurance against minor error, compute the answer for $n=1$, $2$, $3$, maybe $4$. $\endgroup$ – André Nicolas Jul 4 '14 at 16:34

Here is a combinatorial proof because I like combinatorial proofs.

Note that that $\sum_{k \geq 0} \binom{n}{2k} = 2^{n-1}$. One way to prove this result is with the binomial theorem. We will use this fact.

Now $\sum_{k \geq 0} (2k+1)\binom{n}{2k+1}$ can be interpreted as choosing a subset of odd size from a set with $n$ elements in one of $\binom{n}{2k+1}$ ways and then choosing a distinguished element from such a subset in one of $2k+1$ ways.

Another way to make the same choice would be to first choose the distinguished element in one of $n$ ways and then choose the remaining elements of such a subset in one of $\binom{n-1}{2k}$ ways. Thus we have

$$\sum_{k \geq 0} (2k+1)\binom{n}{2k+1} = n \sum_{k\geq 0} \binom{n-1}{2k} = n 2^{n-2}.$$

Notice this solution essentially uses the hint Did gave in the comments. The identity Did provides can be proven combinatorially as we have or algebraically.


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.