Sum of Even Index Binomial Coefficients/Proof 2

Theorem

$\ds \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1}$

Proof

Let ${\N_n}^*$ be the initial segment of natural numbers, one-based.

Let:

$E_n = \set {X : \paren {X \subset {\N_n}^*} \land \paren {2 \divides \size X} }$

$O_n = \set {X : \paren {X \subset {\N_n}^*} \land \paren {2 \nmid \size X} }$

That is:

$E_n$ is the set of all subsets of ${\N_n}^*$ with an even number of elements

$O_n$ is the set of all subsets of ${\N_n}^*$ with an odd number of elements.

So by Cardinality of Set of Subsets:

$\ds \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1} \iff \size {E_n} = 2^{n - 1}$

which is to be proved by induction below.

Basis of the Induction

Let $n = 1$.

Then

$\size {E_n} = \size {\set \O} = 1$

and:

$2^{n - 1} = 2^{1 - 1} = 2^0 = 1$

This is the basis for the induction.

Induction Hypothesis

This is the induction hypothesis:

$\size {E_k} = 2^{k - 1}$

So:

$\size {O_k} = \size {2^{ {\N_k}^*} \divides E_k} = 2^k - 2^{k - 1} = 2^{k - 1}$

Induction Step

This is the induction step:

\(\ds \size {E_{k + 1} }\)

\(=\)

\(\ds \size {\set {X: \paren {X \subset {\N_{k + 1} }^* } \land \paren {2 \divides \size X} } }\)

Definition of $E_n$

\(\ds \)

\(=\)

\(\ds \size {\set {X: X \in E_k} \cup \set {X \cup \set {k + 1}: X \in O_k} }\)

Construction of the set with smaller sets, considering the presence of the element $k+1$

\(\ds \)

\(=\)

\(\ds \size {E_k} + \size {O_k}\)

$E_k$ and $O_k$ are disjoint by definition

\(\ds \)

\(=\)

\(\ds 2^{k - 1} + 2^{k - 1}\)

Induction Hypothesis

\(\ds \)

\(=\)

\(\ds 2^k\)

The result follows by induction.

$\blacksquare$