9

In the question of the title, if I define $r(x)=\inf\{s\in \mathbb {N}:x_s\ge 2x\} $, i want to know how $r(x)$ behaves asymptotically, more precisely to know if $\lim\limits_{x\rightarrow \infty} \dfrac {r(x)}{\sqrt{x}}$ exists, and in that case,to find that limit.

Zach Langley
  • 1,367
lecheconmilo
  • 204
  • Generalizing, if we define $r_k(x)$ to be the smallest index $i$ such that $x_i \ge kx$, the limit of $r_k(x)$ as $x$ tends to infinitely empircally looks to be $2\sqrt{k} - 2$. – Zach Langley Aug 28 '18 at 20:44
  • 1
    Anyway, $2(\sqrt2-1)\sqrt x\leqslant r_2(x)\leqslant\sqrt x$. – Did Aug 28 '18 at 20:47
  • From $$x_{i+1}=x_{i}+\sqrt{x_{i}}=x_i\left(1+\frac{1}{\sqrt{x_{i}}}\right)=x_{i-1}\left(1+\frac{1}{\sqrt{x_{i-1}}}\right)\left(1+\frac{1}{\sqrt{x_{i}}}\right)=...\ =x\prod\limits_{k=0}^{i}\left(1+\frac{1}{\sqrt{x_{k}}}\right)\geq x\left(1+\frac{1}{\sqrt{x}}\right)$$ if $0<x\leq1$ then $1+\frac{1}{\sqrt{x}}\geq2$ and $x_1\geq 2x$. So we are looking for $x>1$, right?. – rtybase Aug 28 '18 at 20:49
  • @rtybase: $x\ge 1$. – TonyK Aug 28 '18 at 21:58

2 Answers2

3

A failed but probably fixable (edit: fixed below) attempt:

If we define $y_n = \sqrt{x_n}$ we get

$$y_{n+1} = \sqrt{y_{n}(1+y_n)}=y_n + \frac{1}{2}-\frac18 \frac{1}{y_n}+o(y_n^{-1}) \tag{1}$$

Then, for large $y_0$, we might (to be better justified) the approximation $$y_n \approx \frac{n}{2} +y_0$$

This should be valid for $y_0 \to \infty$ and $n = o(y_0)$

Now, $x_r/x_0 \approx 2 \iff y_r/y_0\approx \sqrt{2}$ so

$$r \approx 2 y_0 (\sqrt{2}-1) \tag{2}$$

And if we plug this in the expresion above we get

$$ \lim\limits_{x\rightarrow \infty} \dfrac {r(x)}{\sqrt{x}}=2(\sqrt{2}-1)=0.828227\cdots \tag{3}$$

Or in general,

$$ \lim\limits_{x\rightarrow \infty} \dfrac {r_k(x)}{\sqrt{x}}=2(\sqrt{k}-1) \tag{4}$$

Of course, this "proof" is faulty, because $r$ is proportional to $n$. However, perhaps it could be fixed. I suspect, from numerical evaluation, that the result is correct.

Edit: From $(1)$ we have the bounds (for $y_0$ large enough)

$$ y_0 + \frac12 - \frac{1}{8 y_0} <y_1 < y_0 + \frac12 \tag{5}$$

Further, $y_n$ is increasing and $$ \frac{1}{y_0 + \frac12 - \frac{1}{8 y_0}}<\frac{1}{y_0 }$$

Then we can extend $(5)$ iteratively:

$$ y_0 + \frac{n}{2} (1 - \frac{1}{4 y_0}) <y_n < y_0 + \frac{n}{2} \tag{6}$$

Dividing by $y_0$, calling $a = \frac{y_n}{y_0}$ and $b=\frac{n}{y_0}$ we get

$$b\left(1 - \frac{1}{4 y_0}\right) < 2 (a-1) < b \tag{7}$$

As $y_0 \to \infty$ we get $2 (a-1) = b$, which corresponds to eqs $(3)$,$(4)$ above.

(Just after writing this I saw Sangchul Lee's answer, I think it's basically the same idea)

leonbloy
  • 63,430
1

Write $y_n = \sqrt{x_n}$ as in user @leonbloy's answer. Then $y_0 = \sqrt{x}$ and

$$ y_{n+1} = \sqrt{y_n(y_n + 1)} = y_n + \frac{1}{2} + \frac{1}{g(y_n)} $$

where $g(y) = 4(y + \frac{1}{2} + \sqrt{y(y+1)} )$. So $ y_{n} = y_0 + \frac{n}{2} + \sum_{k=0}^{n-1} \frac{1}{g(y_k)} $. Together with the monotonicity of $g$, we obtain

$$ y_0 + \frac{n}{2} \leq y_n \leq y_0 + \frac{n}{2} + \frac{n}{g(\sqrt{x})}. $$

Now for each fixed $k > 1$, as $x\to\infty$ we have $y_{r_k(x)}/y_0 \to \sqrt{k}$ as $x\to\infty$. So

$$ \frac{2}{1+\frac{2}{g(\sqrt{x})}} \left( \frac{y_{r_k(x)}}{y_0} - 1 \right) \leq \frac{r_k(x)}{\sqrt{x}} \leq 2\left( \frac{y_{r_k(x)}}{y_0} - 1 \right). $$

Taking $x\to\infty$ proves that the ratio converges to $2(\sqrt{k}-1)$ as heuristically shown by @leonbloy.

Sangchul Lee
  • 167,468