similar function toward a recurrence function

Question

Given the recurrence function $x_{n+1}=\sqrt{(x_n)^2+(x_n)^{1/2}}$ and $x_0=1$, find a function that has similar output with this function with large $n$.

I have tested out a few values for $x_{n}$ but I failed to find any relationship. Is there a general way to approach "find a similar function" type of problem? Also I have tried to find a recurrence relationship for this problem:however I don't think there exist material online for me to learn about how to solve a recurrence with squares and square roots. Some help will be greatly appreciated

Answer 1

A common way to deal with such things is to make lots of approximations. Treat $x_n$ as a function of $n$. We have: $$x_{n+1}^2-x_n^2=\sqrt{x_n}$$ $$(x_{n+1}-x_n)(x_{n+1}+x_n)=\sqrt{x_n}$$ For large $n$, $x_{n+1}-x_n = \frac{x_{n+1}-x_n}{n+1-n}\approx \frac{dx_n}{dn}$, and $x_{n+1}\approx x_n$. We hve:

$$2x_n\frac{dx_n}{dn}=\sqrt{x_n}$$ $$2\sqrt{x_n}dx_n=dn$$ $$\frac{4}{3}x_n^{\frac{3}{2}}=n+1\text{(I've chosen constant of integration as 1)}$$ Thus, $x_n=(\frac{3}{4}(n+1))^{\frac{2}{3}}$ for large $n$. Thus, $x_n$ goes as $n^{2/3}$ for large $n$. This can be shown by proving $\frac{1}{4}(n+1)^{2/3}<x_n<(n+1)^{2/3}$ .

The above relation holds true for $n=3$. Assume it holds true for $n$. Then for $n+1$, $$x_{n+1}=\sqrt{(x_n)^2+(x_n)^{1/2}} < \sqrt{(n+1)^{4/3}+(n+1)^{1/3}}$$

Now, $$(n+2)^{4/3}=(n+1+1)^{4/3}=(n+1)^{4/3}(1+\frac{1}{n+1})^{4/3}$$ $$>(n+1)^{4/3}(1+\frac{4}{3(n+1)}\text{(Bernoulli inequality)}$$ $$=(n+1)^{4/3}+\frac{4}{3}(n+1)^{1/3}>(n+1)^{4/3}+(n+1)^{1/3}$$ Thus, using the above inequality, we have $$x_{n+1}< \sqrt{(n+1)^{4/3}+(n+1)^{1/3}}<\sqrt{(n+2)^{4/3}}<(n+2)^{2/3}$$ Thus by induction, the upper bound on $x_n$ holds true. Similarly you can try showing the lower bound holds true.

Answer 2

Perhaps that the signification of "similar output" is that one want an equivalent for $x_n$ ? If this is the case, you can do as following.

It is easy to see that $x_n\to +\infty$, and that $x_{n+1}/x_n\to 1$. Put $v_n=x_{n+1}^{3/2}-x_n^{3/2}$. Then $v_n=x_n^{3/2}((\frac{x_{n+1}}{x_n})^{3//2}-1)$ is equivalent to $x_n^{3/2}\frac{3}{2}(\frac{x_{n+1}}{x_n}-1)$ (use that $\frac{x^{3/2}-1}{x-1}\to 3/2$ as $x\to 1$)and using that $x_{n+1}-x_n=\frac{x_{n+1}^2-x_n^2}{x_{n+1}+x_n}$, we get that $v_n\to 3/4$. Then using Cesaro's theorem, we have $\frac{v_1+\cdots+v_n}{n}$ that converge to $3/4$, and we get that $x_n$ is equivalent to $(3n/4)^{2/3}$.