Sum over k of -2 Choose k

From ProofWiki
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}$

whether $n$ is odd or even.

Hence the result.

$\blacksquare$


Sources