# 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 would guess that the two questions are together because the questioner wants to use the first in the second, but I can't be sure. It looks like you've included (a) without trying (a), so maybe you just accidentally included it? May 4, 2022 at 16:56
• It doesn't seem like you can do induction here, because you can use $\binom{k+1}i=\binom{k}{i}+\binom{k}{i-1},$ but then the coefficient ahead of $\binom{k}{i-1}$ will be wrong for the induction. You are going to need a different technique. May 4, 2022 at 16:59
• Which year question is it? May 4, 2022 at 19:34

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.

• Great :) please give hint or solution for (a)
– Sonu
May 5, 2022 at 2:11

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.

• Great :). Please give hints or solution for (a)
– Sonu
May 5, 2022 at 2:10
• @Sonu For a), you may use Mathematical Induction and $\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}$. May 5, 2022 at 2:21
• Okay :)... @river li
– Sonu
May 5, 2022 at 2:30