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