Sum of Even Index Binomial Coefficients
Theorem
Let $n > 0$ be a (strictly) positive integer.
Then:
- $\ds \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 + \dotsb = 2^{n - 1}$
Proof 1
From Sum of Binomial Coefficients over Lower Index we have:
- $\ds \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:
- $\ds \sum_{i \mathop \in \Z} \paren {-1}^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 = \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$
Also see
Sources
- 1968: Murray R. Spiegel: Mathematical Handbook of Formulas and Tables ... (previous) ... (next): $\S 3$: The Binomial Formula and Binomial Coefficients: $3.10$
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {3-1}$ Permutations and Combinations: Exercise $7$
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $1$: Some Preliminary Considerations: $1.2$ The Binomial Theorem: Problems $1.2$: $3 \ \text{(e)}$