Sum of Even Index Binomial Coefficients

From ProofWiki
Jump to: navigation, search

Theorem

Let $n > 0$ be a (strictly) positive integer.

Then:

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

where $\dbinom n i$ is a binomial coefficient.


That is:

$\dbinom n 0 + \dbinom n 2 + \dbinom n 4 + \cdots = 2^{n - 1}$


Proof 1

From Sum of Binomial Coefficients over Lower Index we have:

$\displaystyle \sum_{i \mathop \in \Z} \binom n i = 2^n$

That is:

$\dbinom n 0 + \dbinom n 1 + \dbinom n 2 + \dbinom n 3 + \cdots + \dbinom n n = 2^n$

as $\dbinom n i = 0$ for $i < 0$ and $i > n$.

This can be written more conveniently as:

$\dbinom n 0 + \dbinom n 1 + \dbinom n 2 + \dbinom n 3 + \dbinom n 4 + \cdots = 2^n$


Similarly, from Alternating Sum and Difference of Binomial Coefficients for Given n we have:

$\displaystyle \sum_{i \mathop \in \Z} \left({-1}\right)^i \binom n i = 0$

That is:

$\dbinom n 0 - \dbinom n 1 + \dbinom n 2 - \dbinom n 3 + \dbinom n 4 - \cdots = 0$

Adding them together, we get:

$2 \dbinom n 0 + 2 \dbinom n 2 + 2 \dbinom n 4 + \cdots = 2^n$

as the odd index coefficients cancel out.

Dividing by $2$ throughout gives us the result.

$\blacksquare$


Proof 2

Let $N^*_n$ be the initial segment of natural numbers, one-based.

Let:

$E_n = \left\{ {X : \left({X \subset N^*_n}\right) \land \left({2 \mathrel \backslash \left\vert X \right\vert}\right)}\right\}$
$O_n = \left\{ {X : \left({X \subset N^*_n}\right) \land \left({2 \nmid \left\vert X \right\vert}\right)}\right\}$


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:

$\displaystyle \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1} \iff \left\vert{E_n}\right\vert = 2^{n - 1}$

which is to be proved by induction below.


Basis of the Induction

Let $n = 1$.

Then

$\left\vert E_n \right\vert = \left\vert \left\{ {\varnothing}\right\} \right\vert = 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:

$\left\vert E_k \right\vert = 2^{k - 1}$

So:

$\left\vert O_k \right\vert = \left\vert 2^{N^*_k} \mathrel \backslash E_k \right\vert = 2^k - 2^{k-1} = 2^{k - 1}$


Induction Step

This is the induction step:

\(\displaystyle \left\vert {E_{k + 1} }\right\vert\) \(=\) \(\displaystyle \left\vert{\left\{ {X : \left({X \subset N^*_{k + 1} }\right) \land \left({2 \mathrel \backslash \left\vert{X}\right\vert }\right)}\right\} }\right\vert\) $\quad$ Definition of $E_n$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\vert \left\{ {X \vert X \in E_k}\right\} \cup \left\{ {X \cup \left\{ {k+1}\right\} \vert X \in O_k}\right\} \right\vert\) $\quad$ Construction of the set with smaller sets, considering the presence of the element $k+1$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{E_k}\right\vert + \left\vert{O_k}\right\vert\) $\quad$ $E_k$ and $O_k$ are disjoint by definition $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 2^{k - 1} + 2^{k - 1}\) $\quad$ Induction Hypothesis $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 2^k\) $\quad$ $\quad$

The result follows by induction.

$\blacksquare$


Sources