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