Greedy monotone subsequence in a random permutation Let $P$ be a permutation chosen uniformly at random from $S_n$.
Let $S = \{ i : \forall j < i, P(j) < P(i)\}$
(1 is in S too)
What is the expected value of the size of S?
My work:
Let this value is $L(n)$
$L(0) = 0, $
$L(k)=1+\frac{L(0)+...+L(k-1)}{k}$
But I can't simplify it
My work vol.2
$L(k-1) \le L(k)$, $L(2k) = 1 + \frac{L(0)+...+L(2k-1)}{2k} \ge 1 + \frac{L(k)+...+L(2k-1)}{2k} \ge 1+\frac{L(k)}{2}$ => $L(k) \ge log_2k$

Let $A_i$ be the event that $i \in S$, i.e. $P(j) < P(i)$ for all $j < i$, and let $I_{A_i}$ be the indicator random variable for $A_i$, so $I_{A_i}(P) = 1$ if $i \in S$ and $0$ otherwise. Then $|S| = I_{A_1} + I_{A_2} + \cdots + I_{A_n}$, so 
$$\mathbb{E}[|S|] = \mathbb{E}[I_{A_1}] + \cdots + \mathbb{E}[I_{A_n}] = \Pr[A_1] + \cdots + \Pr[A_n].$$
To calculate $\Pr[A_i]$, note that among $P(1), P(2), \dots, P(i)$, each is equally likely to be the largest since $P$ is sampled uniformly from $S_n$, so the probability $\Pr[A_i]$ that $P(i)$ is the largest of $P(1), P(2), \dots, P(i)$ is $\frac{1}{i}$. Then it follows that
$$\mathbb{E}[|S|] = 1 + \frac{1}{2} + \cdots + \frac{1}{n} = H_n \approx \log n$$
where $H_n$ is the $n$-th harmonic number.
