How to prove an identity involving a finite sum of binomial coefficients

Question

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.

Answer 1

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

Answer 2

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