Using expectation to prove identity The problem is there are $n$ different balls with numbers $1,2,...,n$ in the bag. We take one ball at a time randomly, record the number and put it back(suppose the same probability $\dfrac 1 n$ to take any one). $N$ is the times that we take to get every ball at least once.
In the first part, I'm supposed to calculate the expectation of $N$. I made it easily: $$\mathbb{E}(N)=n\sum_{k=1}^{n}\dfrac 1 k$$
In the second question, there is an equation to prove:
$$\sum_{k=1}^{n-1}(-1)^{k+1}\binom n k \dfrac 1 k (1-\dfrac k n)^n=\sum_{k=1}^n \dfrac 1 k$$
I know that I should put the expectation into another way but I don't get it. L.H.S. reminds me of inclusion–exclusion principle, but I can't find an interpretation for $\dfrac 1 k$. Could someone give a combinatoric proof?
Thanks a lot~
 A: Suppose we seek to verify that
$$S_n = \sum_{k=1}^{n-1} (-1)^{k+1} {n\choose k} \frac{1}{k}
\left(1-\frac{k}{n}\right)^n = -1 + H_n.$$
We introduce
$$f(z) = n! (-1)^{n+1} \left(1-\frac{z}{n}\right)^n \frac{1}{z^2}
\prod_{q=1}^n \frac{1}{z-q}.$$
With $1\le k\le n-1$ we get
$$\mathrm{Res}_{z=k} f(z)
= n! (-1)^{n+1} \left(1-\frac{k}{n}\right)^n \frac{1}{k^2}
\prod_{q=1}^{k-1} \frac{1}{k-q} 
\prod_{q=k+1}^{n} \frac{1}{k-q}
\\ = n! (-1)^{n+1} \left(1-\frac{k}{n}\right)^n \frac{1}{k}
\frac{1}{k!} \frac{(-1)^{n-k}}{(n-k)!}
\\ = (-1)^{k+1} \left(1-\frac{k}{n}\right)^n \frac{1}{k}
{n\choose k}$$
so that
$$S_n = \sum_{k=1}^{n-1} \mathrm{Res}_{z=k} f(z).$$
Residues sum to zero so we need the residues at $z=0$ and at infinity.
The residue at zero is
$$\left.n!(-1)^{n+1} n\left(1-\frac{z}{n}\right)^{n-1}
\left(-\frac{1}{n}\right)
\prod_{q=1}^n \frac{1}{z-q}\right|_{z=0}
\\ - \left. n! (-1)^{n+1} \left(1-\frac{z}{n}\right)^n 
\prod_{q=1}^n \frac{1}{z-q} 
\sum_{q=1}^n \frac{1}{z-q}\right|_{z=0}
\\ = -n! (-1)^{n+1} \frac{(-1)^n}{n!}
+ n! (-1)^{n+1} \frac{(-1)^n}{n!} H_n
= 1 - H_n.$$
For the residue at infinity we have
$$\mathrm{Res}_{z=\infty} f(z)
= -\mathrm{Res}_{z=0} \frac{1}{z^2} f(1/z)
\\ = -\mathrm{Res}_{z=0} \frac{1}{z^2} 
n! (-1)^{n+1} \left(1-\frac{1}{nz}\right)^n z^2
\prod_{q=1}^n \frac{1}{1/z-q}
\\ = -\mathrm{Res}_{z=0}
n! (-1)^{n+1} \left(z-\frac{1}{n}\right)^n \frac{1}{z^n}
\prod_{q=1}^n \frac{z}{1-qz}
\\ = -\mathrm{Res}_{z=0}
n! (-1)^{n+1} \left(z-\frac{1}{n}\right)^n
\prod_{q=1}^n \frac{1}{1-qz}
= 0.$$
This means that $$S_n + 1 - H_n = 0$$ or alternatively
$$\bbox[5px,border:2px solid #00A000]{ S_n = -1 + H_n.}$$
Remark. The pole  at $z=n$ from the product  in $f(z)$ is canceled
by the power term $\left(1-\frac{z}{n}\right)^n.$
