4
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\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
    Commented Jul 4, 2014 at 16:17
  • $\begingroup$ @Did Please look at my updated question $\endgroup$ Commented Jul 4, 2014 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
    Commented Jul 4, 2014 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$ Commented Jul 4, 2014 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$ Commented Jul 4, 2014 at 16:54

3 Answers 3

7
$\begingroup$

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}

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Please look at my updated question. $\endgroup$ Commented Jul 4, 2014 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$ Commented Jul 4, 2014 at 16:27
  • $\begingroup$ As insurance against minor error, compute the answer for $n=1$, $2$, $3$, maybe $4$. $\endgroup$ Commented Jul 4, 2014 at 16:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .