# Find $\sum\limits_{k=\frac{n+1}{2}}^n{n \choose k}$ closed form

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

-
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. –  Joel Cohen Oct 22 '11 at 15:25
@FoolForMath: That question is from Discrete math exam, for undergraduate students in computer science. I believe it have a nice closed form . –  MichaelS Oct 22 '11 at 15:28
@JoelCohen: You're right, I've edited the question and added that $n \in N_{odd}$ –  MichaelS Oct 22 '11 at 15:32
@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$. –  André Nicolas Oct 22 '11 at 15:36
@MichaelS:Alright,then for n is odd,simple induction shows the closed form to be $2^{(n-1)}$. –  VelvetThunder Oct 22 '11 at 15:40

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