Sum over k of n Choose k by x to the k by kth Harmonic Number

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $x \in \R_{> 0}$ be a real number.


Then:

$\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$

where:

$\dbinom n k$ denotes a binomial coefficient
$H_k$ denotes the $k$th harmonic number
$0 < \epsilon < \dfrac 1 {x \paren {n + 1} }$


Result for $x = -1$

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

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 \sum_{k \mathop \in \Z} \binom n k x^k H_k + \sum_{k \mathop \in \Z} \binom n {k - 1} x^k H_k\)
\(\ds \) \(=\) \(\ds S_n + x \sum_{k \mathop \ge 1} \binom n {k - 1} x^{k - 1} \paren {H_{k - 1} + \frac 1 k}\) Definition of $S_n$
\(\ds \) \(=\) \(\ds S_n + x \sum_{k \mathop \ge 1} \binom n {k - 1} x^{k - 1} H_{k - 1} + x \sum_{k \mathop \ge 1} \binom n {k - 1} x^{k - 1} \frac 1 k\)
\(\ds \) \(=\) \(\ds S_n + x \sum_{k \mathop \ge 0} \binom n k x^k H_k + \sum_{k \mathop \ge 1} \binom n {k - 1} x^k \frac 1 k\) Translation of Index Variable of Summation
\(\ds \) \(=\) \(\ds S_n + x S_n + \sum_{k \mathop \ge 1} \frac k {n + 1} \binom {n + 1} k x^k \frac 1 k\) Definition of $S_n$, Factors of Binomial Coefficient
\(\ds \) \(=\) \(\ds \paren {x + 1} S_n + \frac 1 {n + 1} \sum_{k \mathop \ge 1} \binom {n + 1} k x^k\) simplifying
\(\ds \) \(=\) \(\ds \paren {x + 1} S_n + \frac 1 {n + 1} \paren {\sum_{k \mathop \ge 0} \binom {n + 1} k x^k - \binom {n + 1} 0 x^0}\) forcing the summation to include the $k = 0$ term
\(\ds \) \(=\) \(\ds \paren {x + 1} S_n + \frac {\paren {x + 1}^{n + 1} - 1} {n + 1}\) Binomial Theorem and Binomial Coefficient with $0$
\(\ds \leadsto \ \ \) \(\ds \frac {S_{n + 1} } {\paren {x + 1}^{n + 1} }\) \(=\) \(\ds \frac {S_n} {\paren {x + 1}^n} + \frac 1 {n + 1} - \frac 1 {\paren {n + 1} \paren {x + 1}^{n + 1} }\) dividing through by $\paren {x + 1}^{n + 1}$


As $S_1 = x$, we have that:

\(\ds \dfrac {S_n} {\paren {x + 1}^n}\) \(=\) \(\ds \frac {S_{n - 1} } {\paren {x + 1}^{n - 1} } + \frac 1 n - \frac 1 {n \paren {x + 1}^n}\)
\(\ds \) \(=\) \(\ds \frac {S_{n - 2} } {\paren {x + 1}^{n - 2} } + \frac 1 {n - 1} - \frac 1 {\paren {n - 1} \paren {x + 1}^{n - 1} } + \frac 1 n - \frac 1 {n \paren {x + 1}^n}\)
\(\ds \) \(=\) \(\ds \dots\)
\(\ds \) \(=\) \(\ds \frac {S_1} {\paren {x + 1}^1} + \frac 1 2 + \frac 1 3 + \dots + \frac 1 n - \frac 1 {2 \paren {x + 1}^2} - \frac 1 {3 \paren {x + 1}^3} - \dots - \frac 1 {n \paren {x + 1}^n}\)
\(\ds \) \(=\) \(\ds \frac x {x + 1} - 1 + \frac 1 {x + 1} + 1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 n - \frac 1 {x + 1} - \frac 1 {2 \paren {x + 1}^2} - \frac 1 {3 \paren {x + 1}^3} - \dots - \frac 1 {n \paren {x + 1}^n}\)
\(\ds \) \(=\) \(\ds 1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 n - \frac 1 {x + 1} - \frac 1 {2 \paren {x + 1}^2} - \frac 1 {3 \paren {x + 1}^3} - \dots - \frac 1 {n \paren {x + 1}^n}\)
\(\ds \) \(=\) \(\ds H_n - \ds \sum_{k \mathop = 1}^n \frac 1 {k \paren {x + 1}^k}\) Definition of Harmonic Number


From Corollary to Power Series Expansion for $\map \ln {1 + x}$ we have:

$\ds \map \ln {1 - z} = -\sum_{k \mathop \ge 1} \frac {z^k} k$

Hence by Logarithm of Reciprocal we have:

$\ds \ln \frac 1 {1 - z} = -\map \ln {1 - z} = \sum_{k \mathop \ge 1} \frac {z^k} k$


Thus:

\(\ds \map \ln {1 + \frac 1 x}\) \(=\) \(\ds \ln \dfrac 1 {1 - \dfrac 1 {x + 1} }\)
\(\ds \) \(=\) \(\ds \sum_{k \mathop \ge 1} \frac 1 {k \paren {x + 1}^k}\)


So as $n \to \infty$, $\ds \sum_{k \mathop \ge 1} \frac 1 {k \paren {x + 1}^k}$ converges, and so:

\(\ds \sum_{k \mathop = 1}^n \frac 1 {k \paren {x + 1}^k}\) \(<\) \(\ds \frac 1 {\paren {n + 1} \paren {x + 1}^{n + 1} } \sum_{k \mathop \ge 0} \frac 1 {\paren {x + 1}^k}\)
\(\ds \) \(=\) \(\ds \frac 1 {\paren {n + 1} \paren {x + 1}^n x}\)


The result follows.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_over_k_of_n_Choose_k_by_x_to_the_k_by_kth_Harmonic_Number&oldid=563793"