Let $x_{n+1} = x_n + 1/(x_1 + x_2 +\ldots + x_n)$ with $x_1 = 1$. Show that $x_n\sim\sqrt{2\log(n)}$.

Question

As the title states we have a sequence defined by

$$x_{n+1} = x_n + \dfrac{1}{x_1 + x_2 + \cdots + x_n}$$

with $x_1 = 1$.

The first few terms are: $1, 2, \frac{7}{3}, \frac{121}{48} \cdots$

Any ideas would be appreciated.

Answer 1

Repeatedly integrating by parts yields $$ \int\sqrt{2\log(x)}\,\mathrm{d}x=x\sqrt{2\log(x)}-x\sum_{k=0}^{n-1}\frac{(2k-1)!!}{\sqrt{2\log(x)}^{\,2k+1}}-\int\frac{(2n-1)!!\,\mathrm{d}x}{\sqrt{2\log(x)}^{\,2n+1}}\tag{1} $$ and $$ \int\frac{\mathrm{d}x}{\sqrt{2\log(x)}}=\frac{x}{\sqrt{2\log(x)}}+x\sum_{k=1}^{n-1}\frac{(2k-1)!!}{\sqrt{2\log(x)}^{\,2k+1}}+\int\frac{(2n-1)!!\,\mathrm{d}x}{\sqrt{2\log(x)}^{\,2n+1}}\tag{2} $$ Therefore, using the Euler-Maclaurin Sum Formula and $(1)$ and $(2)$, for $n\gt1$, we get $$ \left(\sum_{j=1}^n\sqrt{2\log(j)}\,\mathcal{I}(j)\right)^{-1}=\frac1{n\sqrt{2\log(n)}}\,\mathcal{I}(n)\tag{3} $$ where $\mathcal{I}(n)=1+O\left(\frac1{\log(n+1)}\right)$.

Furthermore, $$ \int\frac{\mathrm{d}x}{x\sqrt{2\log(x)}^{\,k}}=\frac1{2-k}\sqrt{2\log(x)}^{\,2-k}+C\tag{4} $$ Thus, applying the Euler-Maclaurin Sum Formula to $(3)$ and $(4)$ gives $$ \sum_{k=2}^n\left(\sum_{j=1}^k\sqrt{2\log(j)}\,\mathcal{I}(j)\right)^{-1} =\sqrt{2\log(n)}\,\mathcal{I}(n)\tag{5} $$

---

Using the definition of $x_n$, we get $$ \begin{align} x_{n+1} &=2+\sum_{k=2}^nx_{k+1}-x_k\\ &=2+\sum_{k=2}^n\left(\sum_{j=1}^kx_j\right)^{-1}\tag{6} \end{align} $$ Equation $(5)$ and $(6)$ show that $$ x_{n+1}=\sqrt{2\log(n)}+O\left(\frac1{\sqrt{\log(n)}}\right)\tag{7} $$

Answer 2

I'll rename the series $y_n$ for convenience. Think of $y_n$ as samples of the function $y(x)$, at points $x_n = n dx$.

Now, your relation simply states that: $$y_{n+1}-y_{n}= y'(x)dx = \frac{dx}{\int y(x) dx}$$

So you have an integral equation that must be solved. I don't know how to solve it, but showing that your function satisfies the equation is easy: $$\frac{d\sqrt{2\log x}}{dx}=\frac{1}{x\sqrt{2\log x}}$$ And for large enough x: $$\int\sqrt{2\log x}\ dx\approx x\sqrt{2\log x}$$

Answer 3

I revisited this question and came up with a very different approach. It is so different, that I didn't think it could be incorporated into my previous answer; so, I have added a second answer.

---

Basic Bounds

Since $x_1=1$ and $$ x_{n+1}-x_n=\left(\sum_{k=1}^nx_k\right)^{-1}\tag1 $$ $x_n$ is a positive, monotonically increasing, concave function of $n$. Therefore, $$ \frac{n+1}2\,x_n\le\sum_{k=1}^nx_k\le nx_n\tag2 $$ The left-hand inequality is because $x_k\ge\frac knx_n$ ($x_1=1,x_2=2$, and $x_n$ is concave in $n$; concavity is maintained by extending $x_0=0$). The right-hand inequality is because $x_k\le x_n$.

We can modify the left hand inequality in $(2)$ by substituting $n\mapsto n+1$ and then subtracting $x_{n+1}$ from both sides to get $$ \frac{n}2\,x_{n+1}\le\sum_{k=1}^nx_k\le nx_n\tag3 $$ Taking reciprocals of $(3)$ and applying $(1)$, we get $$ \frac1{nx_n}\le x_{n+1}-x_n\le\frac2{nx_{n+1}}\tag4 $$ Noting that $2x_n\le x_n+x_{n+1}\le2x_{n+1}$, we can multiply $(4)$ by $x_n+x_{n+1}$ to get $$ \frac2n\le x_{n+1}^2-x_n^2\le\frac4n\tag5 $$ Summing $(5)$ yields $$ \sqrt{1+2H_n}\le x_{n+1}\le\sqrt{1+4H_n}\tag6 $$

---

Asymptotics

Apply $(4)$ and $(6)$ to get that $\frac{x_m}{x_n}\ge1+\epsilon$ requires $m-n\gt\frac{x_n\epsilon}{\frac2{nx_n}}\ge nH_n\epsilon$. Thus, if we set $m=n+nH_n\epsilon$, for $n\le k\le m$, we have $x_k\ge\frac{x_m}{1+\epsilon}$. Therefore, $$ \begin{align} \sum_{k=1}^mx_k &\ge\frac{x_m}{1+\epsilon}\overbrace{\frac{mH_n\epsilon}{1+H_n\epsilon}}^{\substack{\text{number of}\\\text{terms}\\\ge\frac{x_m}{1+\epsilon}}}\tag7\\ &=mx_m\underbrace{\frac1{1+\epsilon}\frac{H_n\epsilon}{1+H_n\epsilon}}_{\substack{\text{can be made close to}\\\text{$1$ by choosing $\epsilon$ small}\\\text{and $n$ big}}}\tag8 \end{align} $$ Due to $(8)$, for large $n$, $(3)$ becomes $$ \sum_{k=1}^nx_k\sim nx_n\tag9 $$ which leads to $(6)$ becoming $$ \begin{align} x_{n+1} &\sim\sqrt{1+2H_n}\tag{10}\\[3pt] &\sim\sqrt{2\log(n)}\tag{11} \end{align} $$