Expected Value of flipping through a book

Let's consider the equivalent problem in which we start at page $n$ and flip backwards through the book, going to each of the pages $0, 1, ..., n - 1$ with equal probability. Let $E_n$ be the expected number of flips. Then we have $E_0 = 0$ and

$E_n = 1 + \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i$

Then in particular we have

\begin{equation} \begin{split} E_{n + 1} &= 1 + \frac{1}{n + 1} \sum\limits_{i = 0}^{n} E_i \\ &= 1 + \frac{E_n}{n + 1} + \frac{n}{n + 1} \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i \\ &= 1 + \frac{E_n}{n + 1} + \frac{n}{n + 1} (1 + \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i) - \frac{n}{n + 1} \\ &= 1 - \frac{n}{n + 1} + \frac{1}{n + 1} E_n + \frac{n}{n + 1} E_n \\ &= \frac{1}{n + 1} + E_n \end{split} \end{equation}

whenever $n \geq 1$ (and the identity is easily verified when $n = 0$ as well).

Then by induction, we have $E_n = \sum\limits_{j = 1}^n \frac{1}{j}$, the $n$th harmonic number. This will be asymptotically very close to $\log_e(n)$.

Let $P_n$ be the expected number of flips in a book with $n$ pages. Then $P_0=0,\ P_1=1$ and $$P_n=1+\frac1n\sum_{k=0}^{n-1}P_k,\tag1$$ because we have to make one flip, and then we're equally likely to have any number of pages from $0$ to $n-1$ left to flip through.

We get $$\begin{align} P_1&=1\\ P_2&=\frac32\\ P_3&=\frac{11}6\\ P_4&=\frac{50}{24}\\ P_5&=\frac{174}{120} \end{align}$$

The denominators are obviously $n!$, so we look for the numerators in OEIS and find A000254, the unsigned Stirling numbers of the first kind.

OESI gives the recurrence $$a_{n+1}=(n+1)a_n+n!$$ for the unsigned Stirling numbers of the first kind, and dividing through by $(n+1)!$ we get $$P_{n+1}=P_n+\frac1{n+1}$$ which clearly gives $$P_n=\sum_{k=1}^n\frac1k=H_n,$$ the $n$th harmonic number. To complete the problem, we must show that the harmonic numbers satisfy the recurrence $(1)$.

Your turn.

Here is how I approached the first part of the problem. Consider a book with exactly $n$ pages. Let $P_1$ denote the first page you flipped to, and let $X_n$ represent the number of pages you flipped until you get to the last page. Note $P_1$ is uniformly distributed on the set $\{1,...,n\}$ and $E(X_1)=1$. Using the total law of expectation we get for $n\geq2$ that $$E(X_n)=\sum_{k=1}^{n}E(X_n|P_1=k)P(P_1=k)=\frac{1}{n}\sum_{k=1}^{n}E(X_n|P_1=k)$$

Notice $E(X_n|P_1=k)=1+E(X_{n-k})$ and so $$E(X_n)=\frac{1}{n}\sum_{k=1}^{n}\Big[1+E(X_{n-k})\Big]=1+\frac{E(X_0)+\dots+E(X_{n-1})}{n}$$ Replace $n$ with $n+1$ to get $$E(X_{n+1})=1+\frac{E(X_0)+\dots+E(X_{n})}{n+1}$$ Combining the previous two equations unveils the relation $$(n+1)(E(X_{n+1})-1)=(n+1)E(X_n)-n$$ which is equivalent to saying $$E(X_{n+1})=E(X_n)+\frac{1}{n+1}$$ So finally $$E(X_n)=\sum_{k=1}^{n}\frac{1}{k}$$