# Is there a closed form for this recurrence?

Given $$E_{n,k} = \begin{cases} 0 & \text{ if } n \leq k \\ n & \text{ if } k = 0 \\ \sum_{i=0}^{n-1} \dfrac{1}{n} \cdot E_{i,k-1} & \text{ otherwise } \end{cases}$$ I wonder is there a closed form for this recurrence that I'm not aware of?

-
Where does this arise? Just curiosity... –  vonbrand Mar 6 '13 at 17:54
Seems to me like the calculation of an expected value involving two variables. There is a recurrence $$E_{n+1, k} = \frac{1}{n+1} (n E_{n,k} + E_{n,k-1})$$ which suggests a probability of two sub-events happening. –  muzzlator Mar 6 '13 at 18:01
Compare this to the identity $$C_{n+1, k} = C_{n,k} + C_{n, k-1}$$ –  muzzlator Mar 6 '13 at 18:14
$E_{n,k}$ has a generating function given by: $$\sum_{k=1}^{\infty} E_{n,k} z^{k-1} = \frac{n+1}{2-z} - \frac{1}{1-z} + \frac{(z)_n}{n!(2-z)(1-z)}$$ where $(z)_n = z(z+1)\cdots(z+n-1)$ is the $n^{th}$ Pochhammer polynomial. No idea how to simplify this further. –  achille hui Mar 6 '13 at 18:34
@vonbrand: The problem is actually finding the expectation of $N$ given that $$\text{for } i = 1 \text{ to } k \{ N = \text{random}(N) \} \text{ where random }(N) = \{0, \ldots N-1\}$$ I tried to solved this problem using Dynamic Programming in $O(N^3)$ but it was too slow, so I guess there must be a nicer form for computing this expectation. –  Chan Mar 6 '13 at 20:52