Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.