Proof $\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k} = H_n$ by induction 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}$


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