A rich and generous man possesses $n$ pounds. Some poor cousins arrive at his mansion. Being generous he decides to give them money. On day 1 , he chooses uniformly at random an integer between $n-1$ and 1 inclusive and gives it to the first cousin. Then he is left with $x$ pounds. On day 2 , he chooses uniformly at random an integer between $x-1$ and 1 inclusive and gives it to the second cousin and so on. If $x=1$ then he does not give the next cousin any money. His choices of the uniform numbers are independent. Let $X_{i}$ be his fortune at the end of day $i$.

Show that $X$ is a Markov chain and find its transition probabilities.

Let $\tau$ be the first time he has 1 pound left, i.e. $\tau=\min \left\{i \geqslant 1: X_{i}=1\right\}$. Show that

$$\mathbb{E}[\tau]=\sum_{i=1}^{n-1} \frac{1}{i}$$