Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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)}$. – Quixotic Oct 22 '11 at 15:40
up vote 6 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.