# Asymptotic complexity for a series

Given a series defined as follows $$E[1] = 1$$ $$E[n] = 1 + \frac{1}{n-1} (E[1] + E[2] + \cdots + E[n-1]) ,\quad\text{for n>1}$$

What would be $E(n)$'s asymptotic growing speed (For example, E(n)~O(log(n)) or E(n)~O(loglog(n))..)?

At first sight, I though this series might converge to same fixed limit, how ever after some simple calculation, there's no limit for this series.

I calculte some E's for this series, which goes like the follows

E[100] = 6.177378
E[200] = 6.873031
E[300] = 7.279331
E[400] = 7.567430
E[500] = 7.790823
E[600] = 7.973312
E[700] = 8.127582
E[800] = 8.261202
E[900] = 8.379055


It seems this series grows very slowly and the growing speed seems to be something like O(log(n)). But I cannot prove it.

Can anybody give me some help? Thank you.

There is a closed formula for $E_n$ in terms of the Harmonic numbers $H_n,\,$ namely $E_{n+1} = 1 + H_n\,$ and therefore
$$E_{n+1} = 1 + \gamma + \ln n + \frac{1}{2n} + O(n^{-2})$$
Proof: We have $$E_n = 1 + \frac{1}{n-1}(E_1 + E_2 + \dots+ E_{n-1})$$ or $$(n-1)E_n = (n-1) + (E_1 + E_2 + \dots + E_{n-1})$$ and $$nE_{n+1} = n + (E_1 + E_2 + \dots + E_{n-1} + E_n)$$ $$=1 + (n-1) + (E_1 + E_2 + \dots + E_{n-1}) + E_n$$ $$=1 + (n-1)E_n + E_n = 1 + nE_n$$ And therefore $$E_{n+1} = \frac{1}{n} + E_n$$ From this $E_{n+1} = 1 + H_n$ and the asymptotic formula follow from the recurrence and asymptotic formulas from http://en.wikipedia.org/wiki/Harmonic_number.
Since the Harmonic numbers are well-known I can compute $E[2000] \approx 9.1778681\,$ and your calculation should reproduce this; other values are e.g. $H_{99}\approx 5.1773775, \; H_{499}\approx 6.7908234$