Expectation value of number of drawings of increasing sequences of labelled balls from an urn. 
An urn contains $n$ balls, labelled from $1$ to $n$. A sequence of drawings with re-insertion is made, until the drawn ball is labelled with a number which is less than or equal to the number of the previous drawing. a. Given a positive integer $k$, find the probability that the number of drawings is greater than $k$; b. Find the expectation value of the number of drawings.

Here is what I've done. For $k = 0$ and $k = 1$, the probability is $1$: after the first drawing is done, at least another drawing has to be done, to determine whether the sequence terminates. For $k \ge n$ probability is $0$: if one has drawn the sequence $1,\dotsc,n$ then she will surely draw a ball labelled with a number less than or equal to $n$. Thus, the interesting events are ones with $1 \le k \le n-1$.
First part
Sketching the situation and naming $X$ the number of drawings, I've conjectured that
$$
\mathbb{P}(X \ge k) = \frac{\sum_{j=k+1}^{n-1} \binom{n}{j}}{n^n}
$$
Why is it wrong? Simply because I've totally forgot about the terminating drawing. If a sequence of $k$ drawings is obtained, what we have is:


*

*A sequence of $k-1$ increasing drawings, which can be counted like order-less drawings sequences of length $k-1$, i.e $\binom{n}{k-1}$ choices;

*A last drawing, which results in a number $k'$ such that $k' \le \max{(d_1,\dotsc,d_{k-1})}$ where $d_i$ is the $i$-th drawing label.


How can I incorporate that second point in my formula?
Second part
Then, I'm stuck on the computation of the expectation value.
1. Is my reasoning broken from beginning? How can I justify my conjecture?
2. Which is the correct way of computing expectation value? I've tried with
$$\mathbb{E}(X) = \sum_{k=0}^\infty \mathbb{P}(X \ge k),
$$
is that right?

I think $P(X\geq k) = P(X>k-1)= \frac{n}{n}\frac{n-1}{n}...\frac{n-(k-1)}{n}$ whenever $1\leq k\leq n$, then use your formula.
