Sum over k of -2 Choose k
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{k \mathop = 0}^n \binom {-2} k = \paren {-1}^n \ceiling {\dfrac {n + 1} 2}$
where:
- $\dbinom {-2} k$ is a binomial coefficient
- $\ceiling x$ denotes the ceiling of $x$.
Proof
\(\ds \sum_{k \mathop = 0}^n \binom {-2} k\) | \(=\) | \(\ds \sum_{k \mathop = 0}^n \paren {-1} \binom {k - \paren {-2} - 1} k\) | Negated Upper Index of Binomial Coefficient | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 0}^n \paren {-1} \binom {k + 1} k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 0}^n \paren {-1} \paren {k + 1}\) | Binomial Coefficient with Self minus One | |||||||||||
\(\ds \) | \(=\) | \(\ds 1 - 2 + 3 - 4 + \cdots \pm \paren {n + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {1 + 2 + 3 + 4 + \cdots + \paren {n + 1} } - 2 \times \paren {2 + 4 + 6 + 8 + \cdots + m}\) | where $m = n$ or $m = n + 1$ according to whether $n$ is odd or even |
When $n$ is even, we have:
\(\ds \) | \(\) | \(\ds \paren {1 + 2 + 3 + 4 + \cdots + \paren {n + 1} } - 2 \times \paren {2 + 4 + 6 + 8 + \cdots + n}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {1 + 2 + 3 + 4 + \cdots + \paren {n + 1} } - 4 \paren {1 + 2 + 3 + 4 + \cdots + \frac n 2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 2}^{n + 1} k - 4 \sum_{k \mathop = 1}^{\frac n 2} k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {n + 1} \paren {n + 2} } 2 - 4 \frac {\frac n 2 \paren {\frac n 2 + 1} } 2\) | Closed Form for Triangular Numbers | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {n + 1} \paren {n + 2} } 2 - \frac {n \paren {n + 2} } 2\) | simplifying | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {n + 2} \paren {n + 1 - n} } 2\) | simplifying | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n + 2} 2\) | simplifying |
As $n$ is even, $n + 1$ is odd, and so:
- $\dfrac {n + 2} 2 = \paren {-1}^n \ceiling {\dfrac {n + 1} 2}$
$\Box$
When $n$ is odd, we have:
\(\ds \) | \(\) | \(\ds \paren {1 + 2 + 3 + 4 + \cdots + \paren {n + 1} } - 2 \times \paren {2 + 4 + 6 + 8 + \cdots + n + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {1 + 2 + 3 + 4 + \cdots + \paren {n + 1} } - 4 \paren {1 + 2 + 3 + 4 + \cdots + \frac {n + 1} 2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 2}^{n + 1} k - 4 \sum_{k \mathop = 1}^{\frac {n + 1} 2} k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {n + 1} \paren {n + 2} } 2 - 4 \frac {\frac {n + 1} 2 \paren {\frac {n + 1} 2 + 1} } 2\) | Closed Form for Triangular Numbers | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {n + 1} \paren {n + 2} } 2 - \frac {\paren {n + 1} \paren {n + 3} } 2\) | simplifying | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {n + 1} \paren {\paren {n + 2} - \paren {n + 3} } } 2\) | simplifying | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {-1} \frac {n + 1} 2\) | simplifying |
As $n$ is odd, $n + 1$ is even, and so $\dfrac {n + 1} 2$ is an integer.
Thus from Real Number is Integer iff equals Ceiling:
- $\paren {-1} \dfrac {n + 1} 2 = \paren {-1}^n \ceiling {\dfrac {n + 1} 2}$
$\Box$
Thus:
- $\ds \sum_{k \mathop = 0}^n \binom {-2} k = \paren {-1}^n \ceiling {\dfrac {n + 1} 2}$
Hence the result.
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: $(37)$