Silly doubt proving $2^{n-1}={n\choose 0}+ {n\choose 2}+ {n\choose 4}+ \dots $?

Question

I have to prove that

$$2^{n-1}={n\choose 0}+ {n\choose 2}+ {n\choose 4}+ \dots $$

I checked the case where $n-1$ is even but I am a little confused when $n-1$ is odd:

$$2^{n-1}={n-1\choose 0}+{n-1\choose 1}+{n-1\choose 2}+\dots +{n-1 \choose n-1}$$

I know we can group the terms pairwise with the identity ${n\choose k}+{n\choose k+1}={n+1 \choose k}$ and obtain:

$$2^{n-1}={n\choose 0}+{n\choose 2}+{n\choose 4}+\dots +{n-1 \choose n-2 } +{n-1 \choose n-1}$$

But when I do the last pair I would obtain:

$${n-1 \choose n-2 } +{n-1 \choose n-1}={n \choose n-2}$$

And the exercise says the last term should be $\displaystyle {n \choose n-1}$ or $\displaystyle {n\choose n}$. I might be missing something truly silly, but I'm not seeing at the moment.

Answer 1

Since $n-1$ is odd, $\binom{n}{n-1}$ can't be a term which appears, since all the "denominators" are even. So the only question is whether the final term should be $\binom{n}{n-2}$ or $\binom{n}{n}$. But if $\binom{n}{n}$ were produced by your process, it would be produced by $\binom{n-1}{n} + \binom{n-1}{n+1}$, which is clearly rubbish; where would the $n+1$ "denominator" come from? So you're right, and you don't need to be worried.

It might help you if, instead of writing $\dots$ at the end of the expression you're trying to prove, you also wrote the final term.

Answer 2

The claim is that $2^{n-1}$ is the total number of even-sized subsets of a given set with $n$ elements.

To see this, we can pair the even-sized subsets up with the odd-sized ones: Choose a fixed element $a$ from the base set, and pair $X$ with $X\setminus\{a\}$ if $a\in X$, and with $X\cup\{a\}$ otherwise. This always assigns an even set to an odd set, so there must be equally many of them.

In particular, the number of even sets is $2^n/2=2^{n-1}$.

Answer 3

Have we already demonstrated:

$\sum_{i=0}^{n} {n\choose i} = 2^{n}$?

Cases where $n$ is even: $n = 2k$

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

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

$\sum_\limits{i=0}^{k} {2k\choose 2i} = 2^{n} - 2^{n-1} = 2^{n-1}$

Answer 4

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k = 0}^{\infty}{n \choose 2k} & = \sum_{k = 0}^{\infty}{n \choose k}{1 + \pars{-1}^{k} \over 2} = {1 \over 2}\sum_{k = 0}^{\infty}{n \choose k} + {1 \over 2}\sum_{k = 0}^{\infty}{n \choose k}\pars{-1}^{k} \\[5mm] & = {1 \over 2}\,\pars{1 + 1}^{\,n} + {1 \over 2}\,\bracks{1 + \pars{-1}}^{\,n} = \bbx{\ds{2^{n - 1} + {1 \over 2}\,\delta_{n,0}}} \end{align}