How to prove an identity involving a finite sum of binomial coefficients I’m struggling to prove this identity $\displaystyle\sum_{m=1}^{n}{\left(\binom nm\frac{{{\left( -1 \right)}^{m-1}}n!}{m} \right)}=\sum_{m=0}^{n-1}{\frac{n!}{n-m}}$. I do understand that it equals $\begin{bmatrix}
   n+1  \\
   2  \\
\end{bmatrix}$ but if possible, I would like to find a proof without explicitly using Stirling numbers. Any help would be appreciated.

We can both sides of the identity divide by $n!$ and want to show
\begin{align*}
\sum_{m=1}^n\binom{n}{m}\frac{(-1)^{m-1}}{m}=\sum_{m=0}^{n-1}\frac{1}{n-m}\tag{1}
\end{align*}

We start with the left-hand side of (1) and obtain
\begin{align*}
a_n&=\color{blue}{\sum_{m=1}^n\binom{n}{m}\frac{(-1)^{m-1}}{m}}\\
&=\sum_{m=1}^n\left(\binom{n-1}{m}+\binom{n-1}{m-1}\right)\frac{(-1)^{m-1}}{m}\\
&=a_{n-1}+\sum_{m=1}^{n}\binom{n-1}{m-1}\frac{(-1)^{m-1}}{m}\\
&=a_{n-1}-\frac{1}{n}\sum_{m=1}^n\binom{n}{m}(-1)^{m}\tag{2}\\
&=a_{n-1}-\frac{1}{n}\left((1-1)^n-1\right)\\
&=a_{n-1}+\frac{1}{n}\\
&\,\,\color{blue}{=H_n}
\end{align*}
with $H_n=1+\frac{1}{2}+\cdots+\frac{1}{n}$ the $n$-th Harmonic number.


The right-hand side gives
\begin{align*}
\color{blue}{\sum_{m=0}^{n-1}\frac{1}{n-m}}&=\sum_{m=0}^{n-1}\frac{1}{m+1}\tag{3}\\
&=\sum_{m=1}^{n}\frac{1}{m}\tag{4}\\
&\,\,\color{blue}{=H_n}
\end{align*}
and the claim (1) follows.

Comment:

*

*In (2) we use the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.


*In (3) we switch the order of summation $m\to n-1-m$.


*In (4) we shift the index to start with $m=1$.
