Prove the existence of limit of $x_{n+1}=x_n+\frac{x_n^2}{n^2}$

Question

The problem is: Let $\{x_n\}$ be a sequence such that $0<x_1<1$ and $x_{n+1}=x_n+\dfrac{x_n^2}{n^2}$. Prove that there exists the limit of $\{x_n\}$.

It is easy to show that $x_n$ is increasing, but I cannot prove it is bounded to show the existing of limit. Anyone have any ideas?

Answer 1

Let $x_1 = t \in (0,1)$. For any $n \ge 1$, it is easy to see $x_n \ge 0$. Since $e^y \ge 1 + y$ for all $y$, we have $$x_n = x_1 \prod_{k=1}^{n-1} \frac{x_{k+1}}{x_k} = t \prod_{k=1}^{n-1} \left(1 + \frac{x_{k}}{k^2}\right) \le t\exp\left(\sum_{k=1}^{n-1} \frac{x_k}{k^2}\right)\tag{*1}$$

Notice

• $x_1 \le t$.
• if $x_n \le tn$, then $x_{n+1} \le n t + t^2 \le (n+1)t$.

By induction, we have $x_n \le n t$ for all $n$.

Substitute this into $(*1)$, we get

$$x_n \le t \exp\left(t\sum_{k=1}^{n-1}\frac{1}{k}\right) \le t\exp\left(t(\log n + \gamma)\right) \le e^\gamma n^t$$ where $\gamma$ is Euler-Mascheroni constant.

Substitute above into $(*1)$ again, we find $$x_n \le t \exp\left(e^{\gamma} \sum_{k=1}^{n-1}\frac{1}{k^{2-t}}\right) \le t \exp\left( e^\gamma \zeta(2-t)\right) < \infty$$ where $\zeta(t)$ is the Riemann Zeta function.

Answer 2

The sequense is obviously monotone increasing since $x_{n+1}>x_n$. To prove that is converging we should show that is bounded. Expanding $x^n$ and doing the addition we take: $$ \eqalign{ x_{n+1} &= x_n + {x_n^2 \over n^2} \cr x_{n} &= x_{n-1} + {x_{n-1}^2 \over {(n-1)}^2} \cr x_{n-1} &= x_{n-2} + {x_{n-2}^2 \over {(n-2)}^2} \cr &\cdots \cr x_2 &= x_1 + {x_1^2 \over 1^2} \cr &\rightarrow \cr x_{n+1} &= x_1+ {x_{1}^2 \over {1}^2}+ {x_{2}^2 \over {2}^2}+\cdots+ {x_{n-1}^2 \over {(n-1)}^2}+ {x_{n}^2 \over {n}^2} \cr &< 1+ {2 \over {1}^2}+ {2 \over {2}^2}+ \cdots+ {2 \over {(n-1)}^2}+ {2 \over {n}^2} \cr &<1+ {2 \pi^2 \over 6} } $$

Answer 3

Because the sequence is increasing $$x_{n+1}=x_{n}+\frac{x_{n}^2}{n^2}<x_{n}+\frac{x_{n}x_{n+1}}{n^2}$$ $$\frac{1}{x_{n}}<\frac{1}{x_{n+1}}+\frac{1}{n^2}$$ (where it is easy to show that the $x_{n}>0$ is positive for all $n$)

so, $$\sum_{i=1}^n(\frac{1}{x_{i}}-\frac{1}{x_{i+1}})<\sum_{i=1}^n\frac{1}{i^2}$$ Because of $$\sum_{i=1}^n\frac{1}{i^2}<1+\sum_{i=2}^n\frac{1}{(i-1)i}<2-\frac{1}{n}<2$$ $$\sum_{i=1}^n(\frac{1}{x_{i}}-\frac{1}{x_{i+1}})<2$$ $$\frac{1}{x_{1}}-\frac{1}{x_{n+1}}<2$$ which is equivalent to $$x_{n+1}<\frac{1}{\frac{1}{x_{1}}-2}$$ so the sequence is bounded above

Answer 4

We define sequences $(f_n)$ and $(g_n)$ of functions on the interval $(0, 1]$ such that

$$ f_{1}(x) = x, \quad f_{n+1}(x) = f_n(x) + \frac{f_n(x)^2}{n^2}, \quad g_n(x) = \frac{1}{f_n(x)}. $$

We make several observations:

1. Since $f_n$ is positive and monotone increasing in $n$, $g_n$ is positive and monotone decreasing in $n$.

2. Each $g_n$ is indefinitely differentiable on $(0, 1]$ and satisfies \begin{align*} g'_{n+1}(x) &= g'_n(x) \left( 1 - \frac{1}{(n^2 g_n(x) + 1)^2} \right), \\ g''_{n+1}(x) &= g''_n(x) \left( 1 - \frac{1}{(n^2g_n(x) + 1)^2} \right) + \frac{2n^2 g'_n(x)^2}{(n^2 g_n(x) + 1)^3}. \end{align*} Starting from $g_1'(x) = -1/x^2 < 0$ and $g_1''(x) = 2/x^3 > 0$, we can inductively prove that $g'_n \leq 0$ and $g''_n \geq 0$ for all $n$. (In other words, $g_n$ is convex and decreasing.)

3. By induction, we can check that $g_n(1) = 1/n$ and $g'_n(1) = -\prod_{k=2}^{n} (1 - k^{-2})$.

Now we are ready to prove the claim. By 2, we find that for all $x \in (0, 1]$

$$ |g'_n(x)| = -g_n'(x) \geq -g_n'(1) = |g_n'(1)|. $$

Thus by the mean value theorem, there exists $c$ between $x$ and $1$ such that

$$ g_n(x) - g_n(1) = -g_n'(c)(1 - x) \geq |g'_n(1)|(1 - x). $$

Taking $n \to \infty$ and utilizing 3, we have

$$ \lim_{n\to\infty} g_n(x) \geq (1 - x) \prod_{n=2}^{\infty} \left(1 - \frac{1}{n^2} \right). $$

If we write $c = \prod_{k=2}^{\infty} (1 - k^{-2}) > 0$, this implies

$$ \lim_{n\to\infty} f_n(x) \leq \frac{1}{c(1-x)} \quad x \in [0, 1)$$

and therefore the conclusion follows.

---

Addendum. Let us first show that $g_n'$ converges uniformly on any compact subinterval of $(0, 1]$ as $n \to \infty$. To this end, we investigate

$$ \left| g_n'(x) - \lim_{n\to\infty} g_n'(x) \right| = |g_n'(x)| \left[ 1 - \prod_{k=n+1}^{\infty} \left( 1 - \frac{1}{(k^2 g_k(x) + 1)^2} \right) \right]. $$

On any $[a, 1] \subset (0, 1]$, we have the following estimates:

• $|g_n'(x)| \leq |g_1'(x)| = x^{-2} \leq a^{-2}$.

• $g_n(x) \geq g_1(x) = 1/n$ and hence $k^2 g_k(x) + 1 \geq k+1$.

Combining these two observations, we have the following uniform estimate

$$ \left| g_n'(x) - \lim_{n\to\infty} g_n'(x) \right| \leq \frac{1}{a^2} \left[ 1 - \prod_{k=n+1}^{\infty} \left( 1 - \frac{1}{(k+1)^2} \right) \right]. $$

It is not hard to check that this bound goes to 0 as $n\to\infty$, and hence $g_n'$ converges uniformly on $[a, 1]$. As a consequence, $g(x) = \lim_n g_n(x)$ converges uniformly on $[a, 1]$, is differentiable and $ g'(x) = \lim_{n\to\infty} g_n'(x)$. This shows that

$$ g'(1) = -\prod_{n=2}^{\infty} \left( 1 - \frac{1}{n^2} \right) = -\frac{1}{2}. $$

Equivalently, we have

$$ \lim_{x \to 1^-} (1-x)f(x) = - \lim_{x \to 1^-} \frac{x - 1}{g(x) - g(1)} = -\frac1{g'(1)} = 2. $$

Answer 5

Here's a way to show convergence without providing an explicit upper bound.

We have $$x_n=x_1+\sum_{k=1}^{n-1}(x_{k+1}-x_k)=x_1+x_1^2+\sum_{k=2}^{n-1}\frac{x_k^2}{k^2},$$ hence the convergence of the sequence would follow from that of the latter series. Now, choose $t\in\left(\frac29,1\right)$ such that $x_3<3^t$. This implies $x_2<2^t$ because otherwise we would have $2^t+2^{2t-2}<3^t$ (false for $t<1$), and inductively yields $x_k<k^{t}$ also for all larger $k$: $$\begin{align}x_{k+1}<k^{t}+k^{2t-2}&<(k+1)^{t} \\ 1+\frac1{k^{2-t}}&<\left(1+\frac1k\right)^t\\ \frac{\log(1+k^{t-2})}{\log(1+1/k)}&<t, \end{align}$$ a consequence of $$\frac{1}{k^{2-t}\log(1+1/k)}\le \frac{1}{3^{2-t}\log(3/2)}<t \iff t> \frac1{\log3} W\left( \frac{\log(3)} {9\log(3/2)} \right)\approx0.216117. $$Therefore, since $$\begin{align}\frac{x_{k+1}^2/(k+1)^2}{x_k^2/k^2}&=\left(1+\frac{x_k}{k^2}\right)^2\left(1-\frac{1}{k+1}\right)^2\\&=\left(1+\frac{2x_k}{k^2}+\frac{x_k^2}{k^4}\right)\left(1-\dfrac2{k+1}+\frac1{(k+1)^2}\right)\\&=1-\frac{2\left(1+\dfrac1k\right)^{-1}}{k}+\dfrac{\left(1-\dfrac2{k+1}\right)\left(\dfrac{x_k}{k^{1+t/2}}\right)^2+\dfrac{2x_k}{k^t}+\dfrac1{k^t}\left(1-\dfrac1{k+1}\right)^2}{k^{2-t}},\end{align}$$ the series converges by Gauss's test, ergo, so does $x_n$.

Answer 6

Since $0\lt x_1\lt1$, the relation $$ x_{n+1}=x_n+\frac{x_n^2}{n^2}\tag{1} $$ implies not only that $x_n$ is increasing, but also inductively that $$ 0\lt x_n\lt n\tag{2} $$ Equation $(1)$ implies $$ \begin{align} \left(\frac1{x_{n+1}}-\frac1{n+1}\right)-\left(\frac1{x_n}-\frac1n\right) &=\left(\frac1n-\frac1{n+1}\right)-\left(\frac{n^2+x_n}{n^2x_n+x_n^2}-\frac{n^2}{n^2x_n+x_n^2}\right)\\ &=\frac1{n^2+n}-\frac1{n^2+x_n}\\ &=-\frac{n-x_n}{(n^2+n)(n^2+x_n)}\\ &\ge-\frac{n-x_n}{n^3(n+1)}\\ &\ge-\frac{n-x_n}{x_nn^2(n+1)}\\ &=-\frac1{n(n+1)}\left(\frac1{x_n}-\frac1n\right)\tag{3} \end{align} $$ Therefore, $$ \left(\frac1{x_{n+1}}-\frac1{n+1}\right) \ge\left(1-\frac1{n(n+1)}\right)\left(\frac1{x_n}-\frac1n\right)\tag{4} $$ and since $$ \prod_{n=1}^\infty\left(1-\frac1{n(n+1)}\right)=\frac1\pi\sin\left(\frac\pi\phi\right)\tag{5} $$ we have $$ \frac1{x_n}-\frac1n\ge\frac1\pi\sin\left(\frac\pi\phi\right)\left(\frac1{x_1}-1\right)\tag{6} $$ which means $$ \bbox[5px,border:2px solid #C0A000]{x_n\le\pi\csc\left(\frac\pi\phi\right)\frac{x_1}{1-x_1}}\tag{7} $$ where $\pi\csc\left(\frac\pi\phi\right)=3.3706903036$.

Therefore, since $x_n$ is increasing and bounded above, the limit exists and is bounded by $(7)$.

---

Motivational Note

I looked at $$ x_{n+1}-x_n=\frac{x_n^2}{n^2}\tag{8} $$ as representative of $$ \frac{\mathrm{d}x}{\mathrm{d}n}=\frac{x^2}{n^2}\tag{9} $$ whose solution is $$ \frac1x-\frac1n=C\tag{10} $$ So I considered $\frac1{x_n}-\frac1n$ which lead to $(3)$, $(4)$, $(6)$ and $(7)$.

---

Derivation of $\boldsymbol{(5)}$ $$ \begin{align} \prod_{k=1}^n\left(1-\frac1{k(k+1)}\right) &=\prod_{k=1}^n\frac{(k+1-\phi)(k+\phi)}{k(k+1)}\tag{11}\\ &=\underbrace{\frac{\Gamma(n+2-\phi)}{\Gamma(2-\phi)}}_{\prod(k+1-\phi)} \underbrace{\frac{\Gamma(n+1+\phi)}{\Gamma(1+\phi)}}_{\prod(k+\phi)} \underbrace{\frac{\Gamma(1)}{\Gamma(n+1)}}_{\prod\frac1k} \underbrace{\frac{\Gamma(2)}{\Gamma(n+2)}}_{\prod\frac1{k+1}}\tag{12}\\ &\to\frac1{\Gamma(2-\phi)\Gamma(1+\phi)}\tag{13}\\[6pt] &=\frac1{\Gamma\left(1-\frac1\phi\right)\Gamma\left(2+\frac1\phi\right)}\tag{14}\\ &=\frac1{\Gamma\left(1-\frac1\phi\right)\Gamma\left(\frac1\phi\right)}\tag{15}\\ &=\frac1\pi\sin\left(\frac\pi\phi\right)\tag{16} \end{align} $$ Explanation:
$(11)$: $k^2+k-1=(k+1-\phi)(k+\phi)$
$(12)$: break up the product of factors into a product of Gamma functions
$(13)$: $\lim\limits_{n\to\infty}\frac{\Gamma(n+2-\phi)\Gamma(n+1+\phi)}{\Gamma(n+1)\Gamma(n+2)}=1$ by Gautschi's Inequality
$(14)$: $\phi=1+\frac1\phi$
$(15)$: $\Gamma\left(2+\frac1\phi\right)=\left(1+\frac1\phi\right)\frac1\phi\,\Gamma\left(\frac1\phi\right)=\phi\,\frac1\phi\,\Gamma\left(\frac1\phi\right)=\Gamma\left(\frac1\phi\right)$
$(16)$: Euler's Reflection Formula

Answer 7

Another proof. Let $x_1=x\in (0,1)$ and suppose that for all $n\ge 1$ $$x_{n+1}=x_n+{x_n^2\over n^2}.\tag{1}$$ Let's prove by induction that if $\alpha={\ln3\over\ln2}-1\sim 0.585$ then $$x_n<{n\over (1-x)n^\alpha+1},\qquad n\ge 1,\; x\in (0,1).\tag{2} $$

The statement is true for $n=1$: $x_1=x<{1\over 2-x}$.

Denote $\epsilon =1-x$ and let us prove that if $(1)$ is true for $n$ then it is true for $n+1$ i.e. $$x_n<{n\over \epsilon n^\alpha+1}\;\;\Longrightarrow\;\; x_{n+1}<{n+1\over \epsilon (n+1)^\alpha+1},\qquad n\ge 1,\; \epsilon\in (0,1).\tag{3}$$

Using $(1)$ it's enugh to show
$${n\over \epsilon n^\alpha+1}+{1\over n^2}\Big({n\over \epsilon n^\alpha+1}\Big)^2<{n+1\over \epsilon (n+1)^\alpha+1}$$ that is $$(n+1)(\epsilon n^\alpha+1)^2-n(\epsilon (n+1)^\alpha+1)(\epsilon n^\alpha+1)-\epsilon (n+1)^\alpha-1>0.\tag{4}$$ After a little algebra the above inequality reduces to $$\eqalign{&\epsilon \big(n^{\alpha+1}+2n^{\alpha}-(n+1)^{\alpha+1}\big)+\epsilon^2\big(n^{2\alpha}(n+1)-n^{\alpha+1}(n+1)^\alpha\big)\cr&=\epsilon n^{1+\alpha} \bigg(1+{2\over n}-\Big(1+{1\over n}\Big)^{\alpha+1}\bigg)+\epsilon^2n^{1+2\alpha}\bigg(1+{1\over n}-\Big(1+{1\over n}\Big)^\alpha\bigg). \cr}\tag{5}$$ The coefficient of $\epsilon^2$ is clearly positive. Using the inequality $(1+t)^\beta<1+\beta t$, (true for $t>-1$ and $\beta\in(0,1)$) we obtain that the coefficient of $\epsilon n^{1+\alpha}$ satisfies $$1+{2\over n}-\Big(1+{1\over n}\Big)^{\alpha+1}>1+{2\over n}-\Big(1+{1\over n}\Big)\Big(1+{\alpha\over n}\Big)={n-2\alpha\over n^2}$$ which is positive for $n\ge2$. On the other hand, when $n=1$ the coefficient of $\epsilon $ in $(5)$ coincides with $3-2^{\alpha+1}$, which vanishes when $\alpha=\ln3/\ln2-1$. This proves $(4)$ for all $n\ge1$ and all $\epsilon \in(0,1)$, and therefore $(3)$ and $(2)$.

Regarding the convergence of $x_n$, we have that for $n\ge2$ (still with $x=x_1$) $$\eqalign{x_{n}&=x+\sum_{k=1}^{n-1} (x_{k+1}-x_k)<x+\sum_{k=1}^{n-1}\bigg({1\over (1-x)k^\alpha+1}\bigg)^2\cr& < x+{1\over (1-x)^2}\sum_{k=1}^\infty{1\over k^{2\alpha}}=x+{C_0\over(1-x)^2}\cr}$$ with $C_0\sim 6.4744$. The sequence $x_n$ is then bounded and increasing, so it must converge.