Binomial Harmonic Numbers

Question

Prove this equation for $0 \leq m \leq n$:
$$ \frac{1}{\binom{n}{m}}\sum_{k=1}^m \binom{n-k}{n-m} \frac{1}{k} = H_n - H_{n-m} $$ where $H_k$ denotes the k-th harmonic number $\left(~H_k := \sum_{n=1}^k \frac{1}{n}~\right)$.

Tried to use Abels partial summation $\big(\sum_{k=1}^m a_k b_k = a_m \sum_{k=1}^m - \sum_{k=1}^{m-1} (a_{k+1}-a_k)\sum_{i=1}^k b_i \big)$, but it leads to nowhere.

Answer 1

Prove by Induction:

Base Case: n=0
0 = 0 $\checkmark$

Induction Step:
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \begin{eqnarray*}\frac{1}{\binom{n+1}{m}} \sum_{k=1}^m \binom{n+1-k}{n+1-m} \frac{1}{k} &=& \frac{1}{\binom{n+1}{m}} \sum_{k=1}^m \frac{n+1-k}{n+1-m} \binom{n-k}{n-m} \frac{1}{k} \\ &=& \frac{1}{\binom{n+1}{m}} \frac{1}{n+1-m} \sum_{k=1}^m (n+1-k) \binom{n-k}{n-m} \frac{1}{k} \\ &=& \frac{1}{\binom{n+1}{m}} \frac{1}{n+1-m} \Big[ \sum_{k=1}^m (n+1) \binom{n-k}{n-m} \frac{1}{k} -\sum_{k=1}^m \binom{n-k}{n-m} \Big] \\ &=& \frac{1}{\binom{n+1}{m}} \frac{n+1}{n+1-m} \sum_{k=1}^m \binom{n-k}{n-m} \frac{1}{k} - \frac{1}{\binom{n+1}{m}} \frac{1}{n+1-m} \sum_{k=1}^m \binom{n-k}{n-m} \\ &=& H_n - H_{n-m} - \frac{1}{\binom{n+1}{m}} \frac{1}{n+1-m} \frac{n \binom{n-1}{n-m}}{n+1-m} \\ &=& H_n - H_{n-m} - \frac{m}{(n+1)(n+1-m)} \\ &=& H_n - H_{n-m} + \frac{-m+(n+1)-(n+1)}{(n+1)(n+1-m)} \\ &=& H_n - H_{n-m} + \frac{1}{n+1}-\frac{1}{n+1-m} \\ &=& \bbx{H_{n+1} - H_{n+1-m}} \end{eqnarray*}$

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{{1 \over {n \choose m}}\sum_{k = 1}^{m}{n - k \choose n - m}{1 \over k} = H_{n} - H_{n - m}:\ {\Large ?}.\quad H_{z}}$ is a Harmonic Number. $\ds{\quad0 \leq m \leq n}$.

\begin{align} {1 \over {n \choose m}}\sum_{k = 1}^{m}{n - k \choose n - m}{1 \over k} & = {1 \over {n \choose m}}\sum_{k = 1}^{\infty}{n - k \choose m - k}{1 \over k} = {1 \over {n \choose m}}\sum_{k = 1}^{\infty}{m - n - 1 \choose m - k} \pars{-1}^{m - k}\,{1 \over k} \\[5mm] & = {\pars{-1}^{m} \over {n \choose m}}\sum_{k = 1}^{\infty} \braces{\bracks{z^{m - k}}\pars{1 + z}^{m - n - 1}} \pars{-1}^{k}\int_{0}^{1}t^{k - 1}\,\dd t \\[5mm] & = {\pars{-1}^{m} \over {n \choose m}}\bracks{z^{m}} \pars{1 + z}^{m - n - 1}\int_{0}^{1}\sum_{k = 1}^{\infty}\pars{-tz}^{k} \,{\dd t \over t} \\[5mm] & = {\pars{-1}^{m} \over {n \choose m}}\bracks{z^{m}} \pars{1 + z}^{m - n - 1}\int_{0}^{1}{-tz \over 1 + tz}\,{\dd t \over t} \\[5mm] & = {\pars{-1}^{m + 1} \over {n \choose m}}\bracks{z^{m}} \pars{1 + z}^{m - n - 1}\ln\pars{1 + z} \\[5mm] & = {\pars{-1}^{m + 1} \over {n \choose m}} \left.\partiald{}{\epsilon}\bracks{z^{m}} \pars{1 + z}^{m - n - 1 + \epsilon}\,\right\vert_{\ \epsilon\ =\ 0} \\[5mm] & = {\pars{-1}^{m + 1} \over {n \choose m}} \left.\partiald{}{\epsilon}{m - n - 1 + \epsilon \choose m} \,\right\vert_{\ \epsilon\ =\ 0} \\[5mm] & = {\pars{-1}^{m + 1} \over {n \choose m}} \left.\partiald{}{\epsilon}{n - \epsilon \choose m}\pars{-1}^{m} \,\right\vert_{\ \epsilon\ =\ 0} \\[5mm] & = {\pars{-1}^{m + 1} \over {n \choose m}}\braces{-{n - \epsilon \choose m} \bracks{H_{n - \epsilon} - H_{n - m - \epsilon}}\pars{-1}^{m}} _{\ \epsilon\ =\ 0} \\[5mm] &= \bbx{H_{n} - H_{n - m}} \end{align}

Answer 3

This solution is similar to an inductive proof with respect to $m$.

Let the sum of interest be

$$s_{n,m}=\frac{1}{\binom{n}{m}} \sum _{k=1}^m \frac{1}{k} \binom{n-k}{n-m}$$

For $m=1$ we find

$$s_{n,1}=\frac{1}{n}$$

The difference of $s$ with respect to $m$ turns out to be surprisingly simple:

$$s_{n,{m+1}}-s_{n,m}=\frac{1}{n-m}\tag{1}$$

so that

$$s_{n,2}=\frac{1}{n}+\frac{1}{n-1}$$ $$s_{n,3}=\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}$$ $$...$$ $$s_{n,m}=\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}+...+\frac{1}{n-m+1}$$

The last expression is easily identified as the difference between two harmonic numbers. Hence

$$s_{n,m}=H_{n}-H_{n-m}$$

as requested.

And now we prove the recurence relation (1) using the definition

$$\binom{n}{m}=\frac{n!}{m!\;(n-m)!}$$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \begin{eqnarray*} s_{n,{m+1}}-s_{n,m} &=& \frac{1}{\binom{n}{m+1}} \sum_{k=1}^{m+1} \frac{1}{k}\binom{n-k}{n-m-1} - \frac{1}{\binom{n}{m}} \sum_{k=1}^{m} \frac{1}{k}\binom{n-k}{n-m}\\ &=& \frac{1}{\binom{n}{m}}\left( \frac{m+1}{n-m}\left( \sum_{k=1}^m \frac{1}{k} \binom{n-k}{n-m-1} +\frac{1}{m+1}\right) -\sum_{k=1}^m \frac{1}{k} \binom{n-k}{n-m}\right) \\ &=& \frac{1}{\binom{n}{m}}\left( \frac{1}{n-m}+ \sum_{k=1}^m \frac{1}{k}\binom{n-k}{n-m} \left( \frac{m+1}{m+1-k} -1 \right) \right) \\ &=& \frac{1}{\binom{n}{m}}\left( \frac{1}{n-m}+ \sum_{k=1}^m \frac{1}{m+1-k}\binom{n-k}{n-m} \right) \\ &=& \frac{1}{n-m}\frac{1}{\binom{n}{m}}\left( 1+\sum_{k=1}^m \frac{n-m}{m+1-k}\binom{n-k}{n-m} \right) \\ &=& \frac{1}{n-m}\frac{1}{\binom{n}{m}}\left( 1+\sum_{k=1}^m \binom{n-k}{m-k+1} \right) =\frac{1}{n-m} \\ \end{eqnarray*}$

In the last step we have used the identity

$\begin{eqnarray*} \binom{n}{m} &=& \sum_{k=1}^m \binom{n-k}{m-k+1} +1 = \sum_{k=1}^{m+1} \binom{n-k}{m-k+1} \\ \end{eqnarray*}$

which in turn results from iterating the basic recursion of the binomial coefficients

$\begin{eqnarray*} \binom{n}{m} &=& \binom{n-1}{m}+\binom{n-1}{m-1} \\ &=& \binom{n-1}{m}+\binom{n-2}{m-1}+\binom{n-2}{m-2} \\ &=& \binom{n-1}{m}+\binom{n-2}{m-1}+...+\binom{n-m}{1} +\binom{n-m-1}{0}\tag{2}\\ \end{eqnarray*}$

This completes the proof of (1) and hence the solution.

Comments

1) I feel that a much shorter proof should be possible starting from (2), but I didn't find it.

2) Interesting related formula (Derivative of binomial coefficients)

$$\frac{d}{dn}\ln\binom{n}{k} = H_{n} - H_{n-k}$$