Sum of combinations of n taken k where k is from n to (n/2)+1

Solution 1:

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