Harmonic number identity I search for an elementary proof of the following identity:
$$
\sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i}\binom{n}{i+k}=\binom{n}{k}\left(H_n-H_k\right)
$$
I have found the following proof:
$$
\sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i}\binom{n}{i+k}=\binom{n}{k}\left(H_n-H_k\right)\iff\sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i}\frac{k!(n-k)!}{(i+k)!(n-i-k)!}=H_n-H_k
$$
Now:
$$
\sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i}\frac{k!(n-k)!}{(i+k)!(n-i-k)!}=\sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i}\frac{i!\cdot k!}{(i+k)!}\frac{(n-k)!}{i!\cdot(n-i-k)!}=\sum_{i=1}^{n-k} (-1)^{i+1}\frac{\Gamma(i)\cdot \Gamma(k+1)}{\Gamma(i+k+1)}\binom{n-k}{i}={\sum_{i=1}^{n-k} (-1)^{i+1}\cdot\int_{0}^{1} x^{i-1}(1-x)^k dx\cdot\binom{n-k}{i}}={\int_{0}^{1} -\frac{(1-x)^k}{x}\cdot\sum_{i=1}^{n-k} \binom{n-k}{i}(-x)^{i}} \space dx={\int_{0}^{1} -\frac{(1-x)^k}{x}\cdot ((1-x)^{n-k}-1) \space dx}={\int_{0}^{1} \frac{1}{x}\cdot \left((1-x)^{k}-(1-x)^n\right) \space dx}={\int_{0}^{1} \frac{1}{1-x}\cdot \left(x^{k}-x^n\right) \space dx}={\int_{0}^{1} \frac{1-x^n}{1-x}-\frac{1-x^k}{1-x}\space dx}={\int_{0}^{1} \frac{1-x^n}{1-x}\space dx-\int_{0}^{1}\frac{1-x^k}{1-x}\space dx}={\int_{0}^{1} \sum_{i=0}^{n-1}x^i\space dx-\int_{0}^{1}\sum_{i=0}^{k-1}x^i\space dx}={\sum_{i=0}^{n-1}\int_{0}^{1}x^i\space dx-\sum_{i=0}^{k-1}\int_{0}^{1} x^i\space dx}={\sum_{i=0}^{n-1}\frac{1}{i+1}-\sum_{i=0}^{k-1}\frac{1}{i+1}}=H_n-H_k
$$
But think it isn't very elegant since it uses rather advanced techniques like the integral representation of the Beta-function. So is there a more elegant way?
 A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{\sum_{j\ =\ 1}^{n - k}{\pars{-1}^{j + 1} \over j}\,{n \choose j + k}
     ={n \choose k}\pars{H_{n} - H_{k}}:\ {\large ?}}$.

With an integral representation for $\ds{\mu \choose k}$ the evaluation is straightforward.

With $\ds{0\ <\ a\ <\ 1}$:
\begin{align}&\color{#66f}{\large%
\sum_{j\ =\ 1}^{n - k}{\pars{-1}^{j + 1} \over j}\,{n \choose j + k}}
=-\sum_{j\ =\ 1}^{\infty}{\pars{-1}^{j} \over j}\,{n \choose n - j - k}
\\[5mm]&=-\sum_{j\ =\ 1}^{\infty}{\pars{-1}^{j} \over j}
\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n - j - k + 1}}\,{\dd z \over 2\pi\ic}
=-\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n - k + 1}}
\sum_{j\ =\ 1}^{\infty}{\pars{-z}^{j} \over j}\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ a}
{\pars{1 + z}^{n}\ln\pars{1 + z} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic}
=\lim_{\mu\ \to\ 0}\partiald{}{\mu}\oint_{\verts{z}\ =\ a}
{\pars{1 + z}^{\mu + n} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic}
\\[5mm]&=\lim_{\mu\ \to\ 0}\partiald{}{\mu}{\mu + n \choose n - k}
={1 \over \pars{n - k}!}\lim_{\mu\ \to\ 0}
\partiald{}{\mu}\bracks{\Gamma\pars{\mu + n + 1} \over  \Gamma\pars{\mu + k + 1}}
\\[5mm]&={1 \over \pars{n - k}!}\braces{%
-\,{n! \over k!}\bracks{\Psi\pars{k + 1} - \Psi\pars{n + 1}}}
\\[5mm]&={n! \over k!\,\pars{n - k}!}\braces{%
\bracks{\Psi\pars{n + 1} + \gamma} - \bracks{\Psi\pars{k + 1} + \gamma}}
=\color{#66f}{\large{n \choose k}\pars{H_{n} - H_{k}}}
\end{align}
A: I upvoted the excellent answer by @FelixMarin.
Note that we do not need the Gamma function step. We have $$\lim_{\mu\to 0} \frac{\partial}{\partial\mu} {\mu+n\choose n-k}
= \lim_{\mu\to 0} \frac{\partial}{\partial\mu} \frac{1}{(n-k)!} 
\prod_{q=0}^{n-k-1} (\mu+n-q)
\\= \frac{1}{(n-k)!} 
\lim_{\mu\to 0} \prod_{q=0}^{n-k-1} (\mu+n-q) \sum_{q=0}^{n-k-1} \frac{1}{\mu+n-q}
\\= \frac{1}{(n-k)!} 
\frac{n!}{k!} (H_n - H_k) = {n\choose k} (H_n - H_k).$$
A: It can be proved by induction on $n$. Fix $n$, and suppose that 
$$\sum_{i\ge 1}\frac{(-1)^{i+1}}i\binom{n}{i+k}=\binom{n}k(H_n-H_k)$$
for $k\le n$. Then for $k\le n$ we have
$$\begin{align*}
\sum_{i\ge 1}\frac{(-1)^{i+1}}i\binom{n+1}{i+k}&=\sum_{i\ge 1}\frac{(-1)^{i+1}}i\left(\binom{n}{i+k}+\binom{n}{i+k-1}\right)\\\\
&=\sum_{i\ge 1}\frac{(-1)^{i+1}}i\binom{n}{i+k}+\sum_{i\ge 1}\frac{(-1)^{i+1}}i\binom{n}{i+k-1}\\\\
&\overset{*}=\binom{n}k(H_n-H_k)+\binom{n}{k-1}(H_n-H_{k-1})\\\\
&=\left(\binom{n}k+\binom{n}{k-1}\right)H_n-\binom{n}kH_k-\binom{n}{k-1}H_{k-1}\\\\
&=\binom{n+1}kH_n-\binom{n}k\left(H_{k-1}+\frac1k\right)-\binom{n}{k-1}H_{k-1}\\\\
&=\binom{n+1}kH_n-\left(\binom{n}k+\binom{n}{k-1}\right)H_{k-1}-\binom{n}k\frac1k\\\\
&=\binom{n+1}kH_n-\binom{n+1}kH_{k-1}-\binom{n}k\frac1k\;,
\end{align*}$$
where I used the induction hypothesis twice at the starred step. At this point it’s easier to work backwards from the desired $\binom{n+1}k(H_{n+1}-H_k)$: it’s
$$\binom{n+1}kH_n-\binom{n+1}kH_{k-1}+\binom{n+1}k\frac1{n+1}-\binom{n+1}k\frac1k\;,$$
and
$$\begin{align*}
\binom{n+1}k\frac1{n+1}-\binom{n+1}k\frac1k&=\frac{n!}{k!(n+1-k)!}-\frac{(n+1)!}{k\cdot k!(n+1-k)!}\\\\
&=\frac{(k-n-1)n!}{k\cdot k!(n+1-k)!}\\\\
&=-\frac{n!}{k\cdot k!(n-k)!}\\\\
&=-\binom{n}k\frac1k\;,
\end{align*}$$
so
$$\binom{n+1}k(H_{n+1}-H_k)=\binom{n+1}kH_n-\binom{n+1}kH_{k-1}-\binom{n}k\frac1k\;,$$
exactly as desired. This omits only the case $k=n+1$, which is trivial.
