Proof $\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k} = H_n$ by induction

Question

I found interesting task: Calculate $$\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k}$$

I have calculated some first values and I see that it is $H_n$. I found there tip that it can be solved by induction or by "integral" trick by considering $\sum_{k=1}^n(-1)^k{n\choose k}x^{k-1}$ I don't know what is that trick so I decided to solve it by induction.

Let $S_n = \sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k} $ $$ S_1 = 1 = H_1 \text{ ok.} $$ $$S_{n+1} = \sum_{k=1}^{n+1} (-1)^{k+1} \binom{n+1}{k}\frac{1}{k} = \\ -\sum_{k=0}^{n} (-1)^{k+1} \binom{n+1}{k+1}\frac{1}{k+1}$$ but I have problem with use induction assumption. $$-\sum_{k=0}^{n} (-1)^{k+1} \binom{n}{k}\frac{n+1}{(k+1)^2} = \\ -(n+1)\sum_{k=0}^{n} (-1)^{k+1} \binom{n}{k}\frac{1}{(k+1)^2}$$ but know I have $\frac{1}{(k+1)^2} $ instead of something like $\frac{1}{k}$

Answer 1

We show by induction the following is valid for $n\geq 1$: \begin{align*} \sum_{k=1}^n(-1)^{k+1}\binom{n}{k}\frac{1}{k}=H_n \end{align*}

Base step: $n=1$

\begin{align*} \sum_{k=1}^1(-1)^{k+1}\binom{1}{k}\frac{1}{k}=1=H_1 \end{align*}

Induction hypothesis: $n=N$

We assume the validity of \begin{align*} \sum_{k=1}^N(-1)^{k+1}\binom{N}{k}\frac{1}{k}=H_N\tag{1} \end{align*}

Induction step: $n=N+1$

We have to show \begin{align*} \sum_{k=1}^{N+1}(-1)^{k+1}\binom{N+1}{k}\frac{1}{k}=H_{N+1}\ \end{align*}

We obtain for $N\geq 1$: \begin{align*} \color{blue}{f_{N+1}}&\color{blue}{=\sum_{k=1}^{N+1}(-1)^{k+1}\binom{N+1}{k}\frac{1}{k}}\\ &=\sum_{k=1}^{N+1}(-1)^{k+1}\left[\binom{N}{k}+\binom{N}{k-1}\right]\frac{1}{k}\tag{2}\\ &=f_{N}+\sum_{k=1}^{N+1}(-1)^{k+1}\binom{N}{k-1}\frac{1}{k}\tag{3}\\ &=f_{N}-\frac{1}{N+1}\sum_{k=1}^{N+1}(-1)^k\binom{N+1}{k}\tag{4}\\ &=f_{N}-\frac{1}{N+1}\left[(1-1)^{N+1}-1\right]\\ &=f_{N}+\frac{1}{N+1}\\ &\,\,\color{blue}{=H_{N+1}} \end{align*} and the claim follows.

Comment:

• In (2) we use the binomial identity $\binom{p+1}{q}=\binom{p}{q}+\binom{p}{q-1}$.

• In (3) we apply the induction hypothesis (1).

• In (4) we use the binomial identity $\frac{p+1}{q+1}\binom{p}{q}=\binom{p+1}{q+1}$.

Answer 2

One can do it without induction. $$S_n=-\sum_{k=1}^{n}(-1)^k{n\choose k}\frac1k$$ So we have that $$S_n=-\sum_{k=1}^{n}(-1)^k{n\choose k}\int_0^1x^{k-1}dx=-\int_0^1\sum_{k=1}^n(-1)^k{n\choose k}x^{k-1}dx$$ Then form the binomial theorem we have that $$(1-x)^n=\sum_{k=0}^{n}{n\choose k}(-x)^k$$ Subtracting the $k=0$ term from both sides and multiplying both sides by $-1$, $$1-(1-x)^n=-\sum_{k=1}^{n}(-1)^k{n\choose k}x^k$$ So $$\frac{1-(1-x)^n}{x}=-\sum_{k=1}^{n}(-1)^k{n\choose k}x^{k-1}$$ and we have that $$S_n=\int_0^1\frac{1-(1-x)^n}{x}dx$$ Then the change of variable $x\mapsto 1-x$ provides $$S_n=-\int_1^0\frac{1-x^n}{1-x}dx=\int_0^1\frac{x^n-1}{x-1}dx$$ Then note that $$\begin{align} H_n&=\sum_{k=1}^{n}\frac1k\\ &=\sum_{k=1}^{n}\int_0^1x^{k-1}dx\\ &=\int_0^1\sum_{k=1}^{n}x^{k-1}dx\qquad \text{[Geometric series!!]}\\ &=\int_0^1\frac{x^n-1}{x-1}dx \end{align}$$ Which completes our proof.

Answer 3

We can use induction and a difference triangle.

Define a squence by $\ a_0 = x\ $ and$\ a_n := 1/n\ $ if $\ n>0.\ $ Then the $n$-th forward difference of the sequence is, up to sign, the partial sums of the sequence. That is, let $\ T_{m,n} \ $ be defined by $$ T_{m,0} = a_m, \ \textrm{ and } \; T_{m+1, n} - T_{m, n} = T_{m+1, n+1} \;\textrm{ for all }\; 0\le n\le m. \tag{1} $$ By induction on $\ n\ $, or otherwise, you can prove that $$ \Delta^n a_m := \sum_{k=0}^n (-1)^k \binom{n}{k} a_{m+n-k} \tag{2} $$ and also that $\ T_{m+n,n} = \Delta^n a_m.\ $ A particular case is $\ m=0\ $ where $$ T_{n,n} = \Delta^n a_0 = \sum_{k=0}^n (-1)^k \binom{n}{k} a_{n-k}. \tag{3}$$

Now $$ T_{n,n} = a_0 + \sum_{k=0}^{n-1} (-1)^k\binom{n}{k} \frac1{n-k} = a_0 + \sum_{k=1}^n (-1)^{n-k}\binom{n}{k} \frac1k .\tag{4} $$ Now prove that $$ T_{m,n} = (-1)^n/(m \binom{m-1}n) \; \textrm{ for all } \; 0\le n<m\ \tag{5} $$ by showing that the right side of equation $(5)$ satisfies equation $(1)$. Next, equation $(1)$ also implies $$ T_{n+1,n} = T_{n,n} + T_{n+1,n+1}. \tag{6} $$ Prove that this implies using $\ H_n = 1/n + H_{n-1}\ $ and induction that $$ T_{n,n} = (-1)^n(a_0 - H_n). \tag{7} $$ Comparing with equation $(4)$ we get our final result $$ H_n = \sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k}. \tag{8} $$