4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Greg Martin Apr 2 at 15:53
3
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.