Summation to n of Power of k over k

From ProofWiki
Jump to navigation Jump to search

Theorem

$\ds \sum_{k \mathop = 1}^n \dfrac {x^k} k = H_n \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\paren {x - 1}^k} k$

where:

$H_n$ denotes the $n$th harmonic number
$\dbinom n k$ denotes a binomial coefficient.


Proof 1

The proof proceeds by induction over $n$.

For all $n \in \Z_{\ge 1}$, let $\map P n$ be the proposition:

$\ds \sum_{k \mathop = 1}^n \dfrac {x^k} k = H_n \ds \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\paren {x - 1}^k} k$


Basis for the Induction

$\map P 1$ is the case:

\(\ds \sum_{k \mathop = 1}^1 \dfrac {x^k} k\) \(=\) \(\ds \dfrac {x^1} 1\)
\(\ds \) \(=\) \(\ds x\)
\(\ds \) \(=\) \(\ds 1 \paren {x - 1}\)
\(\ds \) \(=\) \(\ds 1 \dbinom 1 1 \paren {x - 1}\) Binomial Coefficient with Self, for example
\(\ds \) \(=\) \(\ds H_1 \sum_{k \mathop = 1}^1 \dbinom 1 k \dfrac {\paren {x - 1}^k} k\) Harmonic Number H1

Thus $\map P 1$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $\map P r$ is true, where $r \ge 1$, then it logically follows that $\map P {r 1}$ is true.


So this is the induction hypothesis:

$\ds \sum_{k \mathop = 1}^r \dfrac {x^k} k = H_r \ds \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\paren {x - 1}^k} k$


from which it is to be shown that:

$\ds \sum_{k \mathop = 1}^{r 1} \dfrac {x^k} k = H_{r 1} \ds \sum_{k \mathop = 1}^{r 1} \dbinom {r 1} k \dfrac {\paren {x - 1}^k} k$


Induction Step

This is the induction step:


\(\ds \sum_{k \mathop = 1}^{r 1} \dfrac {x^k} k\) \(=\) \(\ds \sum_{k \mathop = 1}^r \dfrac {x^k} k \dfrac {x^{r 1} } {r 1}\)
\(\ds \) \(=\) \(\ds H_r \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\paren {x - 1}^k} k \dfrac {x^{r 1} } {r 1}\) Induction Hypothesis
\(\ds \) \(=\) \(\ds H_r \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\paren {x - 1}^k} k \dfrac {\paren {x^{r 1} - 1} 1} {r 1}\)
\(\ds \) \(=\) \(\ds H_r \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\paren {x - 1}^k} k \dfrac {\paren {x^{r 1} - 1} } {r 1} \dfrac 1 {r 1}\)
\(\ds \) \(=\) \(\ds H_{r 1} \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\paren {x - 1}^k} k \dfrac {x^{r 1} - 1} {r 1}\)
\(\ds \) \(=\) \(\ds H_{r 1} \sum_{k \mathop = 1}^r \paren { \dbinom {r 1} k - \dbinom r {k - 1} } \dfrac {\paren {x - 1}^k} k \dfrac {x^{r 1} - 1} {r 1}\) Pascal's Rule
\(\ds \) \(=\) \(\ds H_{r 1} \sum_{k \mathop = 1}^r \dbinom {r 1} k \dfrac {\paren {x - 1}^k} k - \sum_{k \mathop = 1}^r \dbinom r {k - 1} \dfrac {\paren {x - 1}^k} k \dfrac {x^{r 1} - 1} {r 1}\)
\(\ds \) \(=\) \(\ds H_{r 1} \sum_{k \mathop = 1}^r \dbinom {r 1} k \dfrac {\paren {x - 1}^k} k - \sum_{k \mathop = 1}^r \dfrac k {r 1} \dbinom {r 1} k \dfrac {\paren {x - 1}^k} k \dfrac {x^{r 1} - 1} {r 1}\) Factors of Binomial Coefficient
\(\ds \) \(=\) \(\ds H_{r 1} \sum_{k \mathop = 1}^r \dbinom {r 1} k \dfrac {\paren {x - 1}^k} k - \dfrac 1 {r 1} \sum_{k \mathop = 1}^r \dbinom {r 1} k \paren {x - 1}^k \dfrac {x^{r 1} - 1} {r 1}\)
\(\ds \) \(=\) \(\ds H_{r 1} \sum_{k \mathop = 1}^r \dbinom {r 1} k \dfrac {\paren {x - 1}^k} k - \dfrac 1 {r 1} \paren {\paren {\paren {x - 1} 1 }^{r 1} - 1 - \paren {x - 1}^{r 1} } \dfrac {x^{r 1} - 1} {r 1}\) Binomial Theorem
\(\ds \) \(=\) \(\ds H_{r 1} \sum_{k \mathop = 1}^r \dbinom {r 1} k \dfrac {\paren {x - 1}^k} k - \dfrac {x^{r 1} - 1} {r 1} \dfrac {\paren {x - 1}^{r 1} } {r 1} \dfrac {x^{r 1} - 1} {r 1}\)
\(\ds \) \(=\) \(\ds H_{r 1} \sum_{k \mathop = 1}^{r 1} \dbinom {r 1} k \dfrac {\paren {x - 1}^k} k\)


So $\map P r \implies \map P {r 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\forall n \in \Z_{\ge 1}: \ds \sum_{k \mathop = 1}^n \dfrac {x^k} k = H_n \ds \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\paren {x - 1}^k} k$


Proof 2

Differentiating with respect to $x$:

\(\ds \dfrac \d {\d x} \paren {\sum_{k \mathop = 1}^n \dfrac {x^k} k}\) \(=\) \(\ds \sum_{k \mathop = 1}^n\dfrac \d {\d x}\paren {\dfrac {x^k} k}\) Applications of Linear Combination of Derivatives
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 1}^n k \dfrac {x^{k - 1} } k\) Power Rule for Derivatives
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 1}^n x^{k - 1}\)
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 0}^{n - 1} x^k\) Translation of Index Variable of Summation
\(\ds \) \(=\) \(\ds \dfrac {x^n - 1} {x - 1}\) Sum of Geometric Sequence


Thus:

\(\ds \sum_{k \mathop = 1}^n \dfrac {x^k} k\) \(=\) \(\ds \int \dfrac {x^n - 1} {x - 1} \rd x\)
\(\ds \) \(=\) \(\ds \int \dfrac {\paren {z 1}^n - 1} z \rd z\) Integration by Substitution: $z = x - 1$
\(\ds \) \(=\) \(\ds \int \paren {\dfrac {\paren {z 1}^n} z - \dfrac 1 z} \rd z\)
\(\ds \) \(=\) \(\ds \int \paren {\dfrac 1 z \sum_{k \mathop = 0}^n \dbinom n k z^k - \dfrac 1 z} \rd z\) Binomial Theorem
\(\ds \) \(=\) \(\ds \int \paren {\sum_{k \mathop = 1}^n \dbinom n k z^{k - 1} \dfrac 1 z - \dfrac 1 z} \rd z\) Binomial Coefficient with Zero
\(\ds \) \(=\) \(\ds \int \paren {\sum_{k \mathop = 1}^n \dbinom n k z^{k - 1} } \rd z\)
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 1}^n \dbinom n k \int z^{k - 1} \rd z\) Linear Combination of Primitives
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 1}^n \dbinom n k \dfrac {z^k} k C\) Primitive of Power
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\paren {x - 1}^k} k C\)


When $x = 1$ we have:

\(\ds \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\paren {1 - 1}^k} k C\) \(=\) \(\ds \sum_{k \mathop = 1}^n \dfrac {1^k} k\)
\(\ds \leadsto \ \ \) \(\ds 0 C\) \(=\) \(\ds \sum_{k \mathop = 1}^n \dfrac 1 k\)
\(\ds \leadsto \ \ \) \(\ds C\) \(=\) \(\ds H_n\) Definition of Harmonic Number

The result follows.


Sources

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