Sum of Odd Index Binomial Coefficients
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{i \mathop \ge 0} \binom n {2 i + 1} = 2^{n - 1}$
where $\dbinom n i$ is a binomial coefficient.
That is:
- $\dbinom n 1 + \dbinom n 3 + \dbinom n 5 + \dotsb = 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:
- $(1): \quad \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:
- $(2): \quad \dbinom n 0 - \dbinom n 1 + \dbinom n 2 - \dbinom n 3 + \dbinom n 4 - \cdots = 0$
Subtracting $(2)$ from $(1)$, we get:
- $2 \dbinom n 1 + 2 \dbinom n 3 + 2 \dbinom n 5 + \cdots = 2^n$
as the even index coefficients cancel out.
Dividing by $2$ throughout gives us the result.
$\blacksquare$
Also see
Sources
- 1953: L. Harwood Clarke: A Note Book in Pure Mathematics ... (previous) ... (next): $\text I$. Algebra: The Binomial Theorem: Relations between coeffficients
- 1968: Murray R. Spiegel: Mathematical Handbook of Formulas and Tables ... (previous) ... (next): $\S 3$: The Binomial Formula and Binomial Coefficients: $3.11$
- 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)}$