# Chaitanya's Random Pages

## July 26, 2014

### Harmonic numbers in terms of binomial coefficients

Filed under: mathematics — ckrao @ 11:48 am

Harmonic numbers $H_n$ are the sums of reciprocals of the first $n$ natural numbers. $\displaystyle H_n := \sum_{k=1}^n \frac{1}{k}\quad\quad(1)$

The first few terms are 1, 3/2, 11/6, 25/12, 137/60, 49/20, 363/140, …

An interesting sum relating the harmonic numbers to the binomial coefficients is $\displaystyle H_n = \sum_{k=1}^n \binom{n}{k} \frac{(-1)^{k-1}}{k}.\quad\quad(2)$

For example, for $n=7$: \begin{aligned} & \quad \frac{7}{1} - \frac{21}{2} + \frac{35}{3} - \frac{35}{4} + \frac{21}{5} - \frac{7}{6} + \frac{1}{7}\\ &= \frac{363}{140}\\ &= \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7}. \end{aligned}

One way of proving this is by mathematical induction on $n$, where we also use the following result that looks similar but is easier to prove. $\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^{k}}{k+1} = \frac{1}{n+1}\quad\quad(3)$

For example, for $n = 7$: $\displaystyle \frac{1}{1} - \frac{7}{2} + \frac{21}{3} - \frac{35}{4} + \frac{35}{5} - \frac{21}{6} + \frac{7}{7} - \frac{1}{8} = \frac{1}{8}.$

Equation (3) can be proved by using the identity $\frac{1}{k+1}\binom{n}{k} = \frac{1}{n+1} \binom{n+1}{k+1}$. From this, \begin{aligned} & \sum_{k=0}^n \binom{n}{k} \frac{(-1)^{k}}{k+1}\\ &= \frac{1}{n+1}\sum_{k=0}^n \binom{n+1}{k+1} (-1)^{k}\\ &= \frac{1}{n+1}\sum_{k'=1}^{n+1} \binom{n+1}{k'} (-1)^{k'-1}\\ &= \frac{1}{n+1}\left(\sum_{k'=0}^{n+1} \binom{n+1}{k'} (-1)^{k'} (-1) - \binom{n+1}{0} (-1)^{-1}\right)\\ &= \frac{1}{n+1}\left[ \left( (1-1)^{n+1} . (-1)\right) - (-1)\right]\\ &= \frac{1}{n+1}, \end{aligned}

as required.

Then to prove (2) firstly note that for $n=1$, $\sum_{k=1}^1 \binom{1}{k} \frac{(-1)^{k-1}}{k} = 1 = H_1$, so the result is true when $n = 1$. Assume it is true for $n = m$ for some positive integer $m$. That is, assume $\displaystyle H_m = \sum_{k=1}^m \binom{m}{k} \frac{(-1)^{k-1}}{k}.\quad\quad(4)$

Then \begin{aligned} \sum_{k=1}^{m+1} \binom{m+1}{k} \frac{(-1)^{k-1}}{k} &= \sum_{k=1}^{m} \binom{m+1}{k} \frac{(-1)^{k-1}}{k} + \binom{m+1}{m+1} \frac{(-1)^{m}}{m+1}\\ &= \sum_{k=1}^{m} \left( \binom{m}{k} + \binom{m}{k-1} \right) \frac{(-1)^{k-1}}{k} + \frac{(-1)^{m}}{m+1}\\ &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \sum_{k=1}^{m} \binom{m}{k-1} \frac{(-1)^{k-1}}{k} + \frac{(-1)^{m}}{m+1}\\ &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \sum_{k'=0}^{m-1} \binom{m}{k'} \frac{(-1)^{k'}}{k'+1} + \frac{(-1)^{m}}{m+1}\\ &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \sum_{k'=0}^{m} \binom{m}{k'} \frac{(-1)^{k'}}{k'+1} - \binom{m}{m} \frac{(-1)^{m}}{m+1}+ \frac{(-1)^{m}}{m+1}\\ &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \frac{1}{m+1} \quad \text{(using (3))}\\ &= H_m + \frac{1}{m+1} \quad \text{(using (4))}\\ &= H_{m+1}. \end{aligned}

Hence we have shown that if (2) is true for $n=m$, it is also true for $n=m+1$. Then by the principle of mathematical induction (2) is true for all natural numbers $n$.

A more beautiful proof of (2), taken from here, is to write $1/(k+1) = \int_0^1 x^k\ \text{d}x$ and so \begin{aligned} H_n &= \sum_{k=0}^{n-1} \frac{1}{k+1}\\ &= \sum_{k=0}^{n-1} \int_0^1 x^k\ \text{d}x\\ &= \int_0^1 \left( \sum_{k=0}^{n-1} x^k \right) \ \text{d}x\\ &= \int_0^1 \frac{1-(1-u)^n}{u} \text{d}u\\ &= \int_0^1 \frac{-\sum_{k=1}^n \binom{n}{k} (-1)^k u^k}{u} \text{d}u\\ &= \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \int_0^1 u^{k-1} \text{d}u\\ &= \sum_{k=1}^n\binom{n}{k} \frac{(-1)^{k-1}}{k},\\ \end{aligned}

as required.