Sum of Even Index Binomial Coefficients/Proof 1
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1}$
Proof
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$
Sources
- 1953: L. Harwood Clarke: A Note Book in Pure Mathematics ... (previous) ... (next): $\text I$. Algebra: The Binomial Theorem: Relations between coeffficients
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $37$