# How to prove this inequality $x^2_{n}\le\frac{8}{3}$

let sequence $$\{x_{n}\}$$ such $$x_{1}=0,x_{2}=1$$,and $$x_{n+1}=\left(1+\dfrac{1}{n}\right)x_{n}-x_{n-1},n\ge 2$$ show that $$x^2_{n}\le\dfrac{8}{3}$$

This problem it seem interesting,and $$x_{n+1}-x_{n}=\dfrac{1}{n}x_{n}-x_{n-1}$$ so we have $$x_{n+1}-x_{1}=\sum_{k=1}^{n}\dfrac{x_{k}}{k}-\sum_{k=1}^{n-1}x_{k}$$ where $$x_{0}=-1$$

It seem this problem very interesting,I guess this $$\dfrac{8}{3}$$ maybe is not best constant,But is stronger constant

• Hey,it's very interesting.I've made attempts to explore this problem for an hour, but have no methods. Commented Apr 1, 2020 at 9:51
• Thanks, This problem is from my teacher give me Commented Apr 1, 2020 at 11:06
• Does anyone have a computer that's more powerful than a macbook laptop? I have a python code and am trying to plot $x_n^2$ (and I seem to have discovered something interesting), but I don't have enough power to see enough pattern to support my claim lol. Commented Apr 1, 2020 at 11:52
• Sneak peak of what I've done so far: imgur.com/a/mu4Zg2f I should note that the x-axis is not n, but rather n*5000. So 20000 -> 1e8 And since I'm only plotting a_(n*5000) it might differ from a_n. I doubt that though. As you can see it goes up and down like smoothly Commented Apr 1, 2020 at 11:55
• My friends made some attempts to analysis the asymptotic property of $a_{6n}$, but had no idea about the bound 8/3. Commented Apr 1, 2020 at 22:17

Very interesting problem. A possible approach to the solution is through the theory of dynamical systems considering it as a perturbation of a conservative system. I guess that the solution below might be improved to provide a slightly better constant.

Setting $$y_n=x_{n-1}$$ the given equation is equivalent to $$\left\{ \begin{array}{l} y_{n+1} = x_n\\ x_{n+1} = \left(1+\frac{1}{n}\right)x_n-y_n \end{array} \right.$$

Consider the following energy function for the system $$E_n = (x_n + y_n)^2+3(x_n-y_n)^2.$$ Using the definition of $$x_{n+1}$$ and $$y_{n+1}$$ above, a somehow lengthy, but straightforward computation gives $$E_{n+1} = E_n + \frac{4}{n}\left(1+\frac{1}{n}\right)x_n^2 - \frac{8}{n}x_ny_n = E_n + \frac{4 x_n^2}{n^2} + \frac{4}{n} \left(x_n (x_n-y_n) -x_ny_n\right).$$ Recalling that $$x_n-y_n = x_{n+1}-\frac{1}{n}x_n$$, this implies that $$E_{n+1} = E_n + \frac{4}{n} (x_{n+1}x_n - x_n y_n)$$ and hence \begin{align} E_{n+1} &= E_2 + \sum_{i=2}^n \frac{4}{i} (x_{i+1} y_{i+1} -x_iy_i) = E_2 + \frac{4}{n} x_{n+1} y_{n+1}+\sum_{i=3}^{n} \left( \frac{4}{i-1} - \frac{4}{i} \right)x_{i}y_{i} - 2x_2y_2\\ &=4+\frac{4}{n} x_{n+1} y_{n+1} + \sum_{i=3}^{n} \frac{4}{i(i-1)} x_{i}y_{i} \end{align} where in the last passage we used $$x_2 = 1$$ and $$y_2 = 0$$.

Observing that $$E_{n} \geq (x_n+y_n)^2+(x_n-y_n)^2 = 2(x_n^2+y_n^2)$$ we deduce $$2(x_{n+1}^2 + y_{n+1}^2) \leq E_{n+1} \leq 4 + \frac{2}{n}(x_{n+1}^2 + y_{n+1}^2)+\sum_{i=3}^{n} \frac{2(x_i^2 + y_i^2)}{i(i-1)}$$ or $$x_{n+1}^2 + y_{n+1}^2 \leq 4 +\sum_{i=3}^{n} \frac{2(x_i^2 + y_i^2)}{i(i-1)}$$

We now want to apply Gronwall's discrete lemma to this equation (see here). Recalling $$\sum_{i=2}^{\infty}\frac{2}{i(i+1)} = 1$$ we prove $$x_n^2 \leq 4e$$ which shows that the desired sequence is bounded despite with a worse constant than asked.

P.S.: Numerical inspection in the $$(x,y)$$ plane above suggests the optimal bound to be $$x_n^2 \leq \frac{9}{4}$$

P.P.S.: I was asked to add some insights on how the argument was developed. The techniques used are quite common in the analysis of ODEs. A good, undergraduate, introduction to some of the ideas below can be found in "Nonlinear Dynamics and Chaos" by Strogatz (link). I am not aware of thorough accessible works specifically dedicated to multidimensional discrete dynamical systems (which often arise though as Poincarè maps of higher dimensional systems of ODEs) since already the one-dimensional case gives rise to several tough problems.

Concerning the main steps of the argument:

• The transformation into a first order system is a common trick.
• Direct inspection of the "unperturbed" system (i.e. the one without the $$1/n$$ term) shows that all sequences generated by arbitrary $$x_1$$ and $$x_2$$ are 6-periodic. Hence the idea to look for an almost conserved quantity for the given case. Some educated guessing supported by simulation led to the definition of the "energy" $$E_n$$ above which is conserved up to $$O(\frac{1}{n})$$ terms.
• Gronwall's technique is finally standard tool in the field. However, in this case some pre-work was needed on the energy estimate to leave only converging terms (hence the somehow painful rearrangement and index shift in the latest steps).
• It seems so elegant. Commented Apr 4, 2020 at 2:11
• How do you deduce $2(x_{n+1}^2 + y_{n+1}^2) \leq E_{n+1}$ from $E_{n+1}=4+\frac{4}{n} x_{n+1} y_{n+1} + \sum_{i=3}^{n} \frac{4}{i(i-1)} x_{i}y_{i}$ ? What makes the $\sum_{i=3}^{n} \frac{4}{i(i-1)} x_{i}y_{i}$ terms magically disappear ? Commented Apr 4, 2020 at 4:03
• How do you think about, can you put your thoughts and thought process written down so I can learn it, thank you,and it's nice answer+1 Commented Apr 4, 2020 at 4:20
• @EwanDelanoy,because $E_{n+1}=(x_{n+1}+y_{n+1})^2+3(x_{n+1}-y_{n+1})^2\ge (x_{n+1}+y_{n+1})^2+(x_{n+1}-y_{n+1})^2=2(x^2_{n+1}+y^2_{n+1})$ Commented Apr 4, 2020 at 10:54
• Where did $4e$ come about? What happened to the $2$? Also, why is Stefano considering $\sum_{i=1}^\infty \frac{1}{i(i+1)}$ instead of $\sum_{i=2}^\infty \frac{1}{i(i+1)}$? Commented Apr 4, 2020 at 11:17

Just so this question is fully answered (i.e. getting the bound $$8/3$$) here I add a condensed proof of $$x_n^2 \leq \frac{8}{3}$$ from the answer given here as Community Wiki.

Define $$E_n = (x_n - x_{n-1})^2 + F_n\left(x_n + x_{n-1}\right)^2$$ with $$F_n = \frac{(n-1)}{3n+1}$$. The recurrence relation gives us $$E_{n+1} - E_n = \frac{(F_{n+1}-F_n)}{F_n}\cdot F_n\left(x_n + x_{n+1}\right)^2 \geq 0$$ since $$F_n$$ is a positive and increasing function. This shows that $$E_n$$ is increasing. We also see that $$E_{n+1} - E_n \leq \frac{(F_{n+1}-F_n)}{F_n}\cdot E_n \implies \frac{E_{n+1}}{F_{n+1}} \leq \frac{E_n}{F_n}$$ so $$\frac{E_n}{F_n}$$ is decreasing and since $$F_n$$ converges it follows that $$E_n$$ converges. To bound $$x_n$$ from $$E_n$$ note that the definition of $$E_n$$ (the equation for an ellipse) allows us to write $$x_n - x_{n-1} = \sqrt{E_n}\cos(\phi_n)$$ and $$x_n + x_{n-1} = \sqrt{\frac{E_n}{F_n}}\sin(\phi_n)$$ for some angle $$\phi_n$$. Thus

$$x_n^2 = \frac{E_n}{4}[\cos(\phi_n) + \frac{1}{\sqrt{F_n}}\sin(\phi_n)]^2$$ Maximizing the right hand side over $$\phi_n$$ gives us $$x_n^2 \leq \frac{E_n}{4}\left[1 + \frac{1}{F_n}\right] = E_n\cdot \frac{n}{n-1}$$ Since $$\frac{E_n}{F_n}$$ is decreasing we have $$E_n \leq F_n \frac{E_2}{F_2} = 8F_n$$ and $$x_n^2 \leq \frac{8n}{3n+1} \leq \frac{8}{3}$$ It is possible to improve the constant with a bit of numerical computation (using $$n=5$$ instead of $$n=2$$ when bounding $$E_n$$) to the best possible one $$\frac{9}{4}$$ (for which we have equality for $$n=3$$). The best possible asymptotic bound would be slightly smaller than $$2$$ (best possible in the sense that $$x_n^2 \approx 2$$ would occur infinitely many times).

• This might not be relevant, but according to numerical calculation, $x_n^2=1.96+t<1.97$ is the best I've gotten Commented Apr 8, 2020 at 20:03
• @GarethMa That is in good agreement with this. The absolute best asymptotic bound (i.e. that holds for very large $n$) we can get from this is $\sim 1.9735$. Commented Apr 8, 2020 at 20:12
• The best low-res picture: imgur.com/a/mu4Zg2f Commented Apr 8, 2020 at 20:13
• Also just wondering, how would 1.9735 be achieved? Like is there a closed form? Commented Apr 8, 2020 at 20:26
• @GarethMa All I said is that if you wanted to find the best asymptotic bound (i.e. a bound for very large $n$) then you would do that. However the question only asks for $8/3$ which we get directly and since $x_2^2 = 9/4$ the best bound that holds for all $n$ (which is what the question asks for) is $9/4$ and you can get that with using the value for $E_n/F_n$ for $n=6$ or so (and you would have to check the value of $x_n^2$ for $n\leq 6$). Commented Apr 8, 2020 at 20:41

(Too long for a comment)

Let $$S_0 = 0, \ S_n = \sum_{k=1}^n x_k.$$ Then applying summation by parts to the formula

$$x_{n+1}=\sum_{k=1}^{n}\dfrac{x_{k}}{k}-\sum_{k=1}^{n-1}x_{k}$$

yields the equation (for $$n\geq 2$$)

$$x_{n+1} = 1 + \frac{S_n}{n} - S_{n-1} + \sum_{k=1}^{n-1} \frac{S_k}{k(k+1)}$$

Adding $$S_n$$ to both sides of this also gives

$$S_{n+1} = 1 + \frac{S_n}{n} + x_n + \sum_{k=1}^{n-1} \frac{S_k}{k(k+1)}$$

I attempted to use these equations together with an inductive hypothesis of the form $$S_{n-1} \in [a,b] , x_n \in [c,d]$$ to show that $$x_{n+1}, S_{n+1}$$ must also lie in the same bounds. While you can get extremely close, it never quite works out and I've convinced myself that this method can not succeed no matter with choices we make for $$a,b,c,d.$$

However, using an established a bound $$|x_n| \leq M$$ (such as the one Stefano proved above) then we can prove inductively that $$S_n$$ is also bounded.

Conjecture - The sequence $$S_n$$ approaches a limit $$L,$$ and $$L = 1 + \sum_{n=1}^{\infty} \frac{S_n}{n(n+1)} \approx 1.953053682$$ A corollary of this is that $$x_n \to 0,$$ which it appears to do so very very slowly.

• I think the limit is not correct. Instead, it approaches 1.9735... - but the graph looks like this: imgur.com/a/mu4Zg2f Commented Apr 8, 2020 at 21:07