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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: