5
$\begingroup$

I wonder if there's a formula for obtaining the sum of $n\choose k$'s where $k$ is from $n$ to $\frac{n}{2}+1$. I found out that in odd numbers, it is $2^{n-1}$ (powerset divided by $2$).

  • 1 = 1
  • 3 = 4
  • 5 = 16
  • 7 = 64

However, It is not the case for even number. I can't come up with the pattern. Here's my observation

  • 2 = 1
  • 4 = 5
  • 6 = 22
  • 8 = 93
$\endgroup$

1 Answer 1

8
$\begingroup$

Recall that $$\sum_{k=0}^n \dbinom{n}k = 2^n$$ Also, recall that $$\dbinom{n}k = \dbinom{n}{n-k}$$ Hence, for odd $n$, we have \begin{align} 2^n & = \sum_{k=0}^n \dbinom{n}k\\ & = \sum_{k=0}^{(n-1)/2} \dbinom{n}k + \sum_{k=(n+1)/2}^n \dbinom{n}k\\ & = \sum_{k=0}^{(n-1)/2} \dbinom{n}{n-k} + \sum_{k=(n+1)/2}^n \dbinom{n}k\\ & = \sum_{k=(n+1)/2}^n \dbinom{n}k + \sum_{k=(n+1)/2}^n \dbinom{n}k\\ & = 2\sum_{k=(n+1)/2}^n \dbinom{n}k \end{align} Hence, if $n$ is odd, we have $$\sum_{k=(n+1)/2}^n \dbinom{n}k = 2^{n-1}$$ If $n$ is even, we have \begin{align} 2^n & = \sum_{k=0}^n \dbinom{n}k\\ & = \sum_{k=0}^{n/2-1} \dbinom{n}k + \dbinom{n}{n/2} + \sum_{k=n/2+1}^n \dbinom{n}k\\ & = \sum_{k=0}^{n/2-1} \dbinom{n}{n-k} + \dbinom{n}{n/2} + \sum_{k=n/2+1}^n \dbinom{n}k\\ & = \sum_{k=n/2+1}^n \dbinom{n}k + \sum_{k=n/2+1}^n \dbinom{n}k + \dbinom{n}{n/2}\\ & = 2\sum_{k=n/2+1}^n \dbinom{n}k + \dbinom{n}{n/2} \end{align} Hence, if $n$ is even, we have $$\sum_{k=n/2+1}^n \dbinom{n}k = 2^{n-1} - \dfrac12 \dbinom{n}{n/2}$$

$\endgroup$
1
  • $\begingroup$ Thanks! Nice and clear explanation $\endgroup$ Feb 10, 2013 at 7:56

You must log in to answer this question.

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