Sum over k of n Choose k by x to the k by kth Harmonic Number/x = -1
Jump to navigation
Jump to search
Theorem
While for $x \in \R_{>0}$ be a real number:
- $\ds \sum_{k \mathop \in \Z} \binom n k x^k H_k = \paren {x + 1}^n \paren {H_n - \map \ln {1 + \frac 1 x} } + \epsilon$
when $x = -1$ we have:
- $\ds \sum_{k \mathop \in \Z} \binom n k x^k H_k = \dfrac {-1} n$
where:
- $\dbinom n k$ denotes a binomial coefficient
- $H_k$ denotes the $k$th harmonic number.
Proof
When $x = -1$ we have that $1 + \dfrac 1 x = 0$, so $\map \ln {1 + \dfrac 1 x}$ is undefined.
Let $S_n = \ds \sum_{k \mathop \in \Z} \binom n k x^k H_k$
Then:
\(\ds S_{n + 1}\) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \binom {n + 1} k x^k H_k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \paren {\binom n k + \binom n {k - 1} } x^k H_k\) | Pascal's Rule | |||||||||||
\(\ds \) | \(=\) | \(\ds S_n + x \sum_{k \mathop \ge 1} \paren {\binom n {k - 1} } x^{k - 1} \paren {H_{k - 1} + \frac 1 k}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds S_n + x S_n + \sum_{k \mathop \ge 1} \binom n {k - 1} x^k \frac 1 k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {1 + x} S_n + \frac 1 {n + 1} \sum_{k \mathop \ge 1} \binom {n + 1} k x^k\) | (look up result for this) |
A specific link is needed here. In particular: for the above You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by searching for it, and adding it here. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{LinkWanted}} from the code. |
Setting $x = -1$:
\(\ds S_{n + 1}\) | \(=\) | \(\ds \paren {1 + -1} S_n + \frac 1 {n + 1} \sum_{k \mathop \ge 1} \binom {n + 1} k \paren {-1}^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {n + 1} \sum_{k \mathop \ge 1} \binom {n + 1} k \paren {-1}^k\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds S_n\) | \(=\) | \(\ds \frac 1 n \sum_{k \mathop \ge 1} \binom n k \paren {-1}^k\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 n \paren {\sum_{k \mathop \ge 0} \binom n k \paren {-1}^k - \binom n 0}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 n \paren {0 - \binom n 0}\) | Alternating Sum and Difference of Binomial Coefficients for Given n | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {-1} n\) | Binomial Coefficient with Zero |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.7$: Harmonic Numbers: Exercise $9$