3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.