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.
 A: This proof is more a verification than a discovery method.  You need to know how to sum a binomial series, a geometric series, and the basic integral identity,
$$ (1) \quad \int_0^1 x^{m-1} dx = \frac{1}{m} $$  Clearing the $n!$ and summing the last sum in the opposite direction, you want to prove
$$ (2) \quad \sum_{m=1}^n \frac{(-1)^m}{m} \binom{n}{m} = -\sum_{m=1}^n \frac{1}{m} .$$
On the left-hand side of (2), insert(1), interchange $\sum$ with $\int$, do the binomial sum, and you get
$$ (3) \quad \sum_{m=1}^n \frac{(-1)^m}{m} \binom{n}{m} = \int_0^1 \frac{(1-x)^n - 1}{x} dx $$
On the right-hand side of (2), insert (1)  interchange $\sum$ with $\int$, do the geometric sum, and you get
$$ (4) \quad \sum_{m=1}^n \frac{1}{m} = -   \int_0^1 \frac{x^n-1}{x-1} dx. $$
The integrals are equivalent; the integral in (4) is the same as (3) by letting $x \to 1-x.$
A: 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$.
