Summation to n of Power of k over k

From ProofWiki
Jump to navigation Jump to search

Theorem

$\displaystyle \sum_{k \mathop = 1}^n \dfrac {x^k} k = H_n + \displaystyle \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\left({x - 1}\right)^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 $P \left({n}\right)$ be the proposition:

$\displaystyle \sum_{k \mathop = 1}^n \dfrac {x^k} k = H_n + \displaystyle \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\left({x - 1}\right)^k} k$


Basis for the Induction

$P \left({1}\right)$ is the case:

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

Thus $P \left({1}\right)$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

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


So this is the induction hypothesis:

$\displaystyle \sum_{k \mathop = 1}^r \dfrac {x^k} k = H_r + \displaystyle \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\left({x - 1}\right)^k} k$


from which it is to be shown that:

$\displaystyle \sum_{k \mathop = 1}^{r + 1} \dfrac {x^k} k = H_{r + 1} + \displaystyle \sum_{k \mathop = 1}^{r + 1} \dbinom {r + 1} k \dfrac {\left({x - 1}\right)^k} k$


Induction Step

This is the induction step:


\(\displaystyle \sum_{k \mathop = 1}^{r + 1} \dfrac {x^k} k\) \(=\) \(\displaystyle \sum_{k \mathop = 1}^r \dfrac {x^k} k + \dfrac {x^{r + 1} } {r + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle H_r + \displaystyle \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\left({x - 1}\right)^k} k + \dfrac {x^{r + 1} } {r + 1}\) Induction Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle H_r + \displaystyle \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\left({x - 1}\right)^k} k + \dfrac {\left({x^{r + 1} - 1}\right) + 1} {r + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle H_r + \displaystyle \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\left({x - 1}\right)^k} k + \dfrac {\left({x^{r + 1} - 1}\right)} {r + 1} + \dfrac 1 {r + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle H_r + \displaystyle \sum_{k \mathop = 1}^r \dbinom r k \dfrac {\left({x - 1}\right)^k} k + \left({x - 1}\right) \sum_{k \mathop = 0}^r \dfrac {x^k} {r + 1} + \dfrac 1 {r + 1}\)
further work needed
\(\displaystyle \) \(=\) \(\displaystyle H_{r + 1} + \displaystyle \sum_{k \mathop = 1}^{r + 1} \dbinom r k \dfrac {\left({x - 1}\right)^k} k\)



So $P \left({r}\right) \implies P \left({r + 1}\right)$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\forall n \in \Z_{\ge 1}: \displaystyle \sum_{k \mathop = 1}^n \dfrac {x^k} k = H_n + \displaystyle \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\left({x - 1}\right)^k} k$


Proof 2

Differentiating with respect to $x$:

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


Thus:

\(\displaystyle \sum_{k \mathop = 1}^n \dfrac {x^k} k\) \(=\) \(\displaystyle \int \dfrac {x^n - 1} {x - 1} \rd x\)
\(\displaystyle \) \(=\) \(\displaystyle \int \dfrac {\paren {z + 1}^n - 1} z \rd z\) Integration by Substitution
\(\displaystyle \) \(=\) \(\displaystyle \int \paren {\dfrac {\paren {z + 1}^n} z - \dfrac 1 z} \rd z\)
\(\displaystyle \) \(=\) \(\displaystyle \int \paren {\dfrac 1 z \sum_{k \mathop = 0}^n \dbinom n k z^k - \dfrac 1 z} \rd z\) Binomial Theorem
\(\displaystyle \) \(=\) \(\displaystyle \int \paren {\sum_{k \mathop = 1}^n \dbinom n k z^{k - 1} + \dfrac 1 z - \dfrac 1 z} \rd z\)
\(\displaystyle \) \(=\) \(\displaystyle \int \paren {\sum_{k \mathop = 1}^n \dbinom n k z^{k - 1} } \rd z\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop = 1}^n \dbinom n k \dfrac {z^k} k + C\) Primitive of Power
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop = 1}^n \dbinom n k \dfrac {\paren {x - 1}^k} k + C\) Primitive of Power


When $x = 1$ we have:

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

The result follows.


Sources