Combinatorial proof where n is an odd positive number and $n=2k+1$

Question

I'm struggling with this proof... if anyone could help, it would be super appreciated!

Let $n$ be an odd positive integer, and write $n = 2k + 1$. Give a combinatorial proof to show that $$\frac{2^n}{2}= \sum^n_{i=k+1} {n \choose i} .$$

Thanks in advance!

Answer 1

$$\sum_{i=k+1}^n\binom ni=\sum_{i=k+1}^{2k+1}\binom{2k+1}{i}$$ counts the number of subsets of a set $S$ with $2k+1$ elements, with at least half of the elements. To count this, we can first choose a subset of $S$ by, for each of the $2k+1$ elements, either choosing to put it in, or not. This can be done in $2^{2k+1}$ ways (since there are $2k+1$ independent choices to make). Afterwards, we can pair each subset $X$ with its "inverse" $S\setminus X$. Each of the ${2^{2k+1}\over2}={2^n\over2}$ pairs will contain exactly one subset with half the elements or more. Our result then follows. $\blacksquare$

Answer 2

$n$ odd means that there are an even number of $n\choose i$'s, as $i$ ranges from $0$ to $n$.

Then since ${n\choose i}={n\choose n-i}$, we get $2^n=\sum_{i=0}^n{n\choose i}=2\cdot\sum_{i=k+1}^n{n\choose i}$.

Answer 3

There are a few points to notice.

The numbers $0,......,k$ and $k+1, .....n$ are each half of the numbers from $0$ to $n=2k+1$.

${n\choose i}$ means "the number of ways to choose $i$ elements from $n$". Common sense tells as that choose $i$ elements to be selected is the exact same then choose all but $i$ elements to not be selected and so ${n\choose i}$ should equal ${n\choose n-i}$. And indeed ${n\choose i} = \frac {n!}{i!(n-i)!} = \frac {n!}{(n-i)!(n-(n-i))!} = {n\choose n-i}$.

Thus for any $ \le k$ then ${n\choose i} = {n\choose n-i=j}$ for some $j = n-i \ge k+1$.

So $\sum_{i = 0}^k {n\choose i} = \sum_{j=k+1}^n{n\choose j}$.

And so $\sum_{i=0}^n{n\choose i} = \sum_{i = 0}^k {n\choose i}+ \sum_{j=k+1}^n{n\choose j} = 2\sum_{j=k+1}^n{n\choose j}$.

Now if ${n\choose i}$ is all the ways to choose $i$ from $n$. then $\sum_{i=0}^n {n\choose i}$ is the total number of ways to choose any number from $n$. And common sense tells us that for every element in a set of $n$ items we can either choose it or not choose it. So $\sum_{i=0}^n {n\choose i} = 2^n$.

So.....

$2^n = \sum_{i=0}^n{n\choose i} = \sum_{i = 0}^k {n\choose i}+ \sum_{j=k+1}^n{n\choose j} = 2\sum_{j=k+1}^n{n\choose j}$

So $\frac {2^n}2= \sum_{j=k+1}^n{n\choose j}$.

We can interpret that as "the number of ways to select more than half of odd number of $n$ items is half of the total number of ways to pick any number of items".