3
$\begingroup$

Write $$\sum\limits_{k=\frac{n+1}{2}}^n{n \choose k}$$ in its closed form.
$n \in N_{odd}$

First time to confront this kind of problem. How do I solve it?

(If its a "you are asking for too much" question, I will much appreciate a link to a good explanatory site on the subject.)

  • 2
    Firt a remark : $\frac{n+1}{2}$ is not always an integer, so maybe you meant its integer part. Then, for a hint : using $\binom{n}{k} = \binom{n}{n-k}$ should help simplify the formula.2011-10-22
  • 0
    @FoolForMath: That question is from Discrete math exam, for undergraduate students in computer science. I believe it have a nice closed form .2011-10-22
  • 0
    @JoelCohen: You're right, I've edited the question and added that $n \in N_{odd}$2011-10-22
  • 2
    @MichaelS: The answer depends on whether $n$ is odd or even. Look first at odd $n$. **Calculate**, for say $n=3$, then $n=5$, maybe for $n=7$, **all** the binomial coefficients. You are likely to get enough information to see what is going on. Then do similar calculations for $n=2$ (maybe), $n=4$, $n=6$.2011-10-22
  • 1
    @MichaelS:Alright,then for n is odd,simple induction shows the closed form to be $2^{(n-1)}$.2011-10-22

1 Answers 1

6

Writing $2n+1$ instead of $n$ gives $$\sum\limits_{k=n+1}^{2n+1}{2n+1 \choose k}$$ and that is exactly a half of the summands in the expansion of $(1+1)^{2n+1}$, so the answer is $4^n$. Or, in the initial terms, $2^{n-1}$.