<s>[INST] 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.
 [/INST] 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.
</s>