Exercise 1.4.20* (Conundrum 2/8)

Question

Show that if $m$ and $n$ are integers with $0\leq m <n$, then
$$\sum_{k=m+1}^n (-1)^k \binom{n}{k} \binom{k-1}{m} = (-1)^{m+1}.$$

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

Same auxiliary function in Exercise 20 and 21.

\begin{proof} 
 Consider the function $f$ defined on $\R$ by
$$f(x) = 
\left\{
\begin{array}{ll}
\frac{1 - (1-x)^n}{x}& 	ext{if } x 
e 0,\
n & 	ext{if } x = 0.
\end{array}
ight.
$$
Despite appearances, $f$ is a polynomial function, because, for $x 
e 0$,
\begin{align*}
f(x) &= \frac{1 - (1-x)^n}{1 - (1-x)} = 1 + (1-x) + (1-x)^2 + \cdots + (1-x)^{n-1},
\end{align*}
and $f(0) = n = 1 + (1-0) + (1-0)^2 + \cdots + (1-0)^{n-1}$.

Moreover, if $x 
e 0$,
\begin{align*}
f(x) &= \frac{1}{x} \left(1-  \sum_{k=0}^n (-1)^k \binom{n}{k} x^k ight)\
&= \sum_{k=1}^n (-1)^{k+1} \binom{n}{k} x^{k-1}, \
\end{align*}
and this equality remains true if $x = 0$. Therefore, for all $x \in \R$,
\begin{align*}
f(x) &= 1 + (1-x) + (1-x)^2 + \cdots + (1-x)^{n-1}\
&= \sum_{k=1}^n (-1)^{k+1} \binom{n}{k} x^{k-1}.
\end{align*}

\bigskip
We compute the $m$-th derivative of $f$, in two ways, and in particular $f^{(m)}(1)/m!$.

If $u_j(x) = x^j$, then $u^{(i)}(x) =  \frac{j!}{(j-i)!} x^{j-i}$ if $i\leq j$, and $u_j^{(k)}(x) = 0$ if $i >j$.

If $v_j(x) =(1- x)^j$, then $v_j^{(i)}(x) = (-1)^i  \frac{j!}{(j-i)!} (1-x)^{j-i}$, and $v_j^{(i)}(x) = 0$ if $i >j$.

\medskip
Therefore, using the second expression of $f(x)$, for $m<n$,
$$f^{(m)}(x) = \sum_{k=m+1}^n (-1)^k \binom{n}{k} \frac{(k-1)!}{(k-1-m)!} x^{k-1-m},$$
thus
$$\frac{f^{(m)}(1)}{m!} =  \sum_{k=m+1}^n (-1)^k \binom{n}{k} \binom{k-1}{m}.$$
Using the first expression of $f(x)$,
$$f^{m}(x) = (-1)^m \left(  \frac{m!}{0!}+ (1-x) \frac{m!}{1!}+ \cdots+ \frac{m!}{n-1-m)!} (1-x)^{n-1-m}ight),$$
thus
$$\frac{f^{(m)}(1)}{m!} = (-1)^m.$$
The comparison gives
$$\sum_{k=m+1}^n (-1)^k \binom{n}{k} \binom{k-1}{m} = (-1)^{m+1}.$$

\end{proof}

Exercise 1.4.20* (Conundrum 2/8)

Answers

Comments

Exercise 1.4.20* (Conundrum 2/8)

Answers

Comments

Add answer