Harmonic number identity

Solution 1:

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

Solution 2:

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

Solution 3:

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.