Question from isi previous years (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.
 A: 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.
A: 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.
