Question from isi previous years

Question

(a) Show that $\left(\begin{array}{l}n \\ k\end{array}\right)=\sum_{m=k}^{n}\left(\begin{array}{c}m-1 \\ k-1\end{array}\right)$.

(b) Prove that $$ \left(\begin{array}{l} n \\ 1 \end{array}\right)-\frac{1}{2}\left(\begin{array}{l} n \\ 2 \end{array}\right)+\frac{1}{3}\left(\begin{array}{l} n \\ 3 \end{array}\right)-\cdots+(-1)^{n-1} \frac{1}{n}\left(\begin{array}{l} n \\ n \end{array}\right)=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} $$

I was thinking mathematical induction for the second part that is,,,

Let $$ \begin{aligned} P(n):\left(\begin{array}{l} n \\ 1 \end{array}\right)-\left(\frac{1}{2}\right)\left(\begin{array}{l} n \\ 2 \end{array}\right) &+\frac{1}{3}\left(\begin{array}{c} n \\ 3 \end{array}\right) \cdots+(-1)^{n-1} \frac{1}{n}\left(\begin{array}{l} n \\ n \end{array}\right) \\ &=1+\frac{1}{2}+\cdots \frac{1}{n} \end{aligned} $$ $P(1):\left(\begin{array}{l}1 \\ 1\end{array}\right)=1$. $P(1)$ true. $$ \begin{aligned} P(2):\left(\begin{array}{l} 2 \\ 1 \end{array}\right)-\frac{1}{2}\left(\begin{array}{l} 2 \\ 2 \end{array}\right) \\ =& 2-\frac{1}{2}=1+\frac{1}{2} \end{aligned} $$ $P(2)$ is also true. Let $p(k)$ tque $\Rightarrow\left(\begin{array}{l}k \\ 1\end{array}\right)-\frac{1}{2}\left(\begin{array}{l}k \\ 2\end{array}\right)+\frac{1}{3}\left(\begin{array}{l}k \\ 3\end{array}\right) \cdots+(-1)^{k+\frac{1}{k}}$ Now we try to show $p(k+1)$ will be true $1+\frac{1}{2}+\cdots \frac{1}{k}$ $P(k+1)=\left(\begin{array}{c}k+1 \\ 1\end{array}\right)-\frac{1}{2}\left(\begin{array}{c}k+1 \\ 2\end{array}\right)+\cdots(-1)^{k} \frac{1}{k+1}\left(\begin{array}{l}k+1 \\ k+1\end{array}\right)$

I cannot argue from here,,, please help me for both part. Thank you.

Answer 1

Suppose we seek to evaluate

$$S_n = \sum_{k=1}^n \frac{(-1)^{k-1}}{k}{n\choose k}.$$

We introduce the function

$$f(z) = n! (-1)^{n-1} \frac{1}{z} \prod_{q=0}^n \frac{1}{z-q}.$$

We have for $1\le k\le n$ that

$$\mathrm{Res}_{z=k} f(z) = n! (-1)^{n-1} \frac{1}{k} \prod_{q=0}^{k-1} \frac{1}{k-q} \prod_{q=k+1}^n \frac{1}{k-q} \\ = n! (-1)^{n-1} \frac{1}{k} \frac{1}{k!} \frac{(-1)^{n-k}}{(n-k)!} = \frac{(-1)^{k-1}}{k}{n\choose k}.$$

It follows that the desired sum is given by

$$S_n = \sum_{k=1}^n \mathrm{Res}_{z=k} f(z).$$

Now residues sum to zero and the residue at infinity is zero by inspection. Therefore the sum must be equal to

$$S_n = -\mathrm{Res}_{z=0} f(z) = - n! (-1)^{n-1} \mathrm{Res}_{z=0} \frac{1}{z^2} \prod_{q=1}^n \frac{1}{z-q} \\ = n! (-1)^n \left.\left(\prod_{q=1}^n \frac{1}{z-q}\right)'\right|_{z=0} \\ = n! (-1)^n \left. \prod_{q=1}^n \frac{1}{z-q} \sum_{q=1}^n \frac{1}{q-z} \right|_{z=0} = n! (-1)^n \frac{(-1)^n}{n!} H_n \\ = H_n = 1+ \frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}.$$

This is the claim.

Answer 2

Sketch of a proof using Mathematical Induction:

Recall the identity (well-known, easy to prove) $$\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}. \tag{1}$$

For (a):

Using (1), we have $$\sum_{m=k}^{n + 1} \binom{m-1}{k-1} = \sum_{m=k}^{n} \binom{m-1}{k-1} + \binom{n}{k-1} = \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}.$$

We are done.

$\phantom{2}$

For (b):

Using (1), we have \begin{align*} &\sum_{k=1}^{n+1} \frac{(-1)^{k - 1}}{k}\binom{n+1}{k}\\ =\, & \sum_{k=1}^{n} \frac{(-1)^{k - 1}}{k}\binom{n+1}{k} + \frac{(-1)^n}{n + 1} \\ =\, & \sum_{k=1}^{n} \frac{(-1)^{k - 1}}{k}\binom{n}{k} + \sum_{k=1}^{n} \frac{(-1)^{k - 1}}{k}\binom{n}{k-1} + \frac{(-1)^n}{n + 1} \\ =\,& \sum_{k=1}^{n} \frac{(-1)^{k - 1}}{k}\binom{n}{k} + \frac{1}{n + 1}\left(\sum_{k=1}^{n} \frac{(-1)^{k - 1}(n + 1)}{k}\binom{n}{k-1} + (-1)^n\right)\\ =\,& \sum_{k=1}^{n} \frac{(-1)^{k - 1}}{k}\binom{n}{k} + \frac{1}{n + 1}\left(\sum_{k=1}^{n} (-1)^{k - 1}\binom{n + 1}{k} + (-1)^n\right)\\ =\,& \sum_{k=1}^{n} \frac{(-1)^{k - 1}}{k}\binom{n}{k} + \frac{1}{n + 1}\left(1 - \sum_{k=0}^{n + 1} (-1)^{k}\binom{n + 1}{k}\right)\\ =\,& \sum_{k=1}^{n} \frac{(-1)^{k - 1}}{k}\binom{n}{k} + \frac{1}{n + 1} \end{align*} where we have used the binomial theorem (letting $x = 1$) $$(1 - x)^{n + 1} = \sum_{k=0}^{n + 1} (-x)^{k}\binom{n + 1}{k}.$$

We are done.