1

Show that

$$ \sum_{r=1}^{n} (-1)^{r-1} \binom{n}{r} \left(1 + \frac{1}{2} + \cdots + \frac{1}{r} \right) = \frac{1}{n} $$

My attempt. I tried by taking the general term

$$ T_r = (-1)^{r-1} \binom{n}{r} \left(1 + \frac{1}{2} + \cdots + \frac{1}{r} \right). $$

It looked somewhat like $\binom{n}{r} \int x^{r-1} \, \mathrm{d}x = \binom{n}{r} \frac{x^r}{r} $, so I took an expansion say

$$ T_1(r) = (-1)^{r-1} \binom{n}{r} \left(1 + x + x^2 + \cdots + x^{r-1} \right). $$

This simplifies to

$$ T_1(r) = (-1)^{r-1}\binom{n}{r} \frac{1-x^r}{1-x}. $$

I am struck after this I tried to rearrange this and done some simplification but I failed.

Please help me.

Sangchul Lee
  • 167,468
hinsberg
  • 25
  • 4
  • 1
    Note you've forgotten the signs in both statements of the problem... – Brian Moehring May 08 '21 at 17:28
  • $(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} +\cdots+ \frac{1}{r} )$ becomes much prettier than (1 + $ \frac{1}{2} $ + $ \frac{1}{3} $ +$ \frac{1}{4} $ ............+$ \frac{1}{r} $): $(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} +\cdots+ \frac{1}{r} )$. It is also easier to type. Surround entire expressions in dollar signs, not each separate term. – Arthur May 08 '21 at 17:38

2 Answers2

2

\begin{align} \sum_{r=1}^n (-1)^{r-1} \binom{n}{r} \sum_{k=1}^r \frac{1}{k} &= \sum_{k=1}^n \frac{1}{k} \sum_{r=k}^n (-1)^{r-1} \binom{n}{r} \\ &= \sum_{k=1}^n \frac{1}{k} (-1)^{k-1} \binom{n-1}{k-1} \\ &= \frac{1}{n}\sum_{k=1}^n (-1)^{k-1} \frac{n}{k} \binom{n-1}{k-1} \\ &= \frac{1}{n}\sum_{k=1}^n (-1)^{k-1} \binom{n}{k} \\ &= \frac{1}{n} \end{align}

RobPratt
  • 45,619
  • Can u please mention the second step more elaborately how did u write that – hinsberg May 09 '21 at 01:11
  • See the first identity here. You can derive it by applying upper negation twice, as shown in Concrete Mathematics, page 165, or via combinatorial proof, as shown in Proofs That Really Count (Identity 168). – RobPratt May 09 '21 at 01:32
  • I am really sorry but I didn't understand what u have said I was asking how did u convert the first step I mean how did u interchange the sigma notations – hinsberg May 09 '21 at 03:40
  • Both double sums are equivalent to summing over $1\le k\le r\le n$. – RobPratt May 09 '21 at 06:31
1

First, let's summarize what you've already shown: The given sum is equivalent to $$\sum_{r=1}^n \int_0^1\left((-1)^{r-1}\binom{n}{r}\frac{1-x^r}{1-x}\right)\,dx$$

The first thing we'll do to this is make the sum start at $r=0$ instead of $r=1$ (which doesn't change anything since when $r=0$ the integrand is $0$), move the [finite] sum inside the integral, and then rearrange algebraically:

$$\begin{align*}\sum_{r=1}^n \int_0^1&\left((-1)^{r-1}\binom{n}{r}\frac{1-x^r}{1-x}\right)\,dx = \sum_{r=0}^n \int_0^1\left((-1)^{r-1}\binom{n}{r}\frac{1-x^r}{1-x}\right)\,dx \\ &= \int_0^1 \sum_{r=0}^n \left((-1)^{r-1}\binom{n}{r}\frac{1-x^r}{1-x}\right)\,dx \\ &= \int_0^1 (1-x)^{-1}\left(\sum_{r=0}^n\binom{n}{r}(-x)^r-\sum_{r=0}^n\binom{n}{r}(-1)^r\right)\,dx\end{align*}$$

Now both sums have the form $\sum_{r=0}^n \binom{n}{r} a^r = (1+a)^n$ by the binomial theorem, so by simplifying: $$\int_0^1(1-x)^{-1}\left((1-x)^n - (1-1)^n\right)\,dx = \int_0^1 (1-x)^{n-1}\,dx = \frac{1}{n}$$

Brian Moehring
  • 21,088