Sum of combinations of n taken k where k is from n to (n/2)+1 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

 A: 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}$$
