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

• There is a general algorithm for verifying identities of this type. For something more hands-on, you could consider the generating functions of both expressions. – Greg Martin Apr 2 at 15:53

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

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