# Summation to n of Power of k over k

## 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

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