<s>[INST] How to solve the following identity? $$
\sum_{i=2}^{n-k+1} \frac{{{n-i}\choose{k-1}}}{{n} \choose k} \frac{1}{i -1} = \frac{k}{n}\sum_{i=k +1}^{n} \frac{1}{i - 1}.
$$
I came across this identity while I was solving a probability problem. I was able to show that it is true for $k=1$ and $k=2$. But I haven't yet cracked how to solve it for all $k>1$.

For k = 1, it is obviously true.
  $$
LHS = \frac{1}{n} \sum_{i=2}^{n} \frac{1}{i-1} = RHS
$$
For k=2, the equations are correct.
  \begin{eqnarray}
LHS &=& \frac{2}{n(n-1)}\sum_{i=2}^{n-1}\frac{n-i}{i-1}\\
&=& \frac{2}{n(n-1)}\sum_{i=2}^{n-1}\left(\frac{n-1}{i-1} - 1\right)\\
&=& \frac{2}{n}\left(\sum_{i=2}^{n-1}\frac{1}{i-1} - 1 + \frac{1}{n -1} \right)\\
&=&\frac{2}{n}\sum_{i=3}^{n}\frac{1}{i-1}\\
&=&RHS
\end{eqnarray}

 [/INST] Multiplication with $\binom{n}{k}$ gives
\begin{align*}
\sum_{i=2}^{n-k+1}\binom{n-i}{k-1}\frac{1}{i-1}&=\binom{n}{k}\frac{k}{n}\sum_{i=k+1}^n\frac{1}{i-1}\tag{1}\\
&=\binom{n-1}{k-1}\left(H_{n-1}-H_{k-1}\right)
\end{align*}
In (1) we apply the binomial identity $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$ and the definition of the Harmonic numbers $H_n=1+\frac{1}{2}+\cdots+\frac{1}{n}$.
Shifting the index $i$ by one gives
\begin{align*}
\sum_{i=1}^{n-k}\binom{n-i-1}{k-1}\frac{1}{i}=\binom{n-1}{k-1}\left(H_{n-1}-H_{k-1}\right)
\end{align*}

Substituting $n \rightarrow n+1$ and $k \rightarrow k+1$ gives the somewhat more convenient representation
  \begin{align*}
\sum_{i=1}^{n-k}\binom{n-i}{k}\frac{1}{i}=\binom{n}{k}\left(H_n-H_k\right)\tag{2}
\end{align*}

We transform the left-hand side and obtain
\begin{align*}
\sum_{i=1}^{n-k}\binom{n-i}{k}\frac{1}{i}&=\sum_{i=0}^{n-k-1}\binom{n-i-1}{k}\frac{1}{i+1}&\qquad(i\rightarrow i-1)\\
&=\sum_{i=0}^{n-k-1}\binom{k+i}{k}\frac{1}{n-k-i}&\qquad(i\rightarrow n-k-1-i)\\
&=\sum_{i=k}^{n-1}\binom{i}{k}\frac{1}{n-i}&\qquad(i\rightarrow i+k)
\end{align*}

The identity  (2)  can now be written as
  \begin{align*}
\color{blue}{\sum_{i=k}^{n-1}\binom{i}{k}\frac{1}{n-i}=\binom{n}{k}\left(H_n-H_k\right)}\tag{3}
\end{align*}

We show the validity of (3) for $1\leq k\leq n$ with the help of generating functions.

Expanding 
  \begin{align*}
\color{blue}{-\frac{\log(1-z)}{(1-z)^{k+1}}}&=\left(\sum_{i=0}^\infty\binom{-k-1}{i}(-z)^i\right)\left(\sum_{l=1}^\infty\frac{1}{l}z^l\right)\tag{4}\\
&=\left(\sum_{i=0}^\infty\binom{k+i}{k}z^i\right)\left(\sum_{l=1}^\infty\frac{1}{l}z^l\right)\tag{5}\\
&=\sum_{n=1}^\infty\left(\sum_{{i+l=n}\atop{i\geq 0,l\geq1}}\binom{k+i}{k}\frac{1}{l}\right)z^n\\
&=\sum_{n=1}^\infty\left(\sum_{i=0}^{n-1}\binom{k+i}{k}\frac{1}{n-i}\right)z^n\\
&=\sum_{n=1}^\infty\left(\sum_{i=k}^{n+k-1}\binom{i}{k}\frac{1}{n-i+k}\right)z^n\tag{6}\\
&\color{blue}{=\sum_{n=k+1}^\infty\left(\sum_{i=k}^{n-1}\binom{i}{k}\frac{1}{n-i}\right)z^{n-k}}\tag{7}\\
\end{align*}
  shows  $-\frac{\log(1-z)}{(1-z)^{k+1}}$ is a generating function of the left-hand side of (3).

Comment:


*

*In (4) we apply the binomial series expansion and the logarithmic  series expansion.

*In (5) we use the binomial identity
\begin{align*}
\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^{q}
\end{align*}

*In (6) we shift the index $i$ to start from $i=k$.

*In (7) we shift the index $n$ to start from $n=k+1$.

On the other hand according to formula (1.2) in Riordan arrays and harmonic number identities by W. Wang it is also the generating function of the right-hand side of (3)
  \begin{align*}
\color{blue}{-\frac{\log(1-z)}{(1-z)^{k+1}}}&=\sum_{n=1}^\infty\binom{n+k}{k}(H_{n+k}-H_k)z^n\\
&=\color{blue}{\sum_{n={k+1}}^\infty\binom{n}{k}(H_n-H_k)z^{n-k}}
\end{align*}
and the claim follows.

</s>