# Limit of recursive sequence with floor

Sequences $x_n$ and $y_n$ are defined as $$x_n=\left\lfloor x_{n-1}\frac{y_{n+1}}{y_{n-1}}\right\rfloor,\\ y_n=y_{n-1}+1,\\ x_0=2015,\ y_0=307.$$ Compute $$\lim_{n\to\infty}\frac{x_n}{y_n^2}$$

My attempt: $y_n=307+n$ so $$x_n> x_{n-1} \frac{308+n}{306+n}>x_0\frac{(308+n)(309+n)}{306\cdot 307}\approx O(n^2),$$ so the limit is approximately $\dfrac{2015}{306\cdot 307}$. However, the answer is given as $\dfrac{2}{101}$. How to obtain this value?

• What competition is this from? – Antonio Vargas Mar 16 '18 at 18:47
• @AntonioVargas Berkeley Math Tournament – Cyclohexanol. Mar 16 '18 at 19:15
• A little correction for your approximation: it should be $$\frac{2015}{307 \cdot 308}$$ because $y_0=307$ and you can't get $306$ in the denominator – Yuriy S Apr 19 '18 at 9:03
• The limit can't be $\frac{2}{101}$ because $x_{10000}=2096543$ and $y_{10000} = 10307$ so $$\frac{x_{10000}}{y_{10000}^2}=\frac{2096543}{106234249}$$ and $$\frac{2096543}{106234249} - \frac{2}{101} = -\frac{717655}{10729659149} < 0$$ – Luca Savant Jul 28 '18 at 12:13

$\def\peq{\mathrel{\phantom{=}}{}}$Note that$$x_{n + 1} = \left[ x_n \frac{n + 309}{n + 307} \right] = x_n + \left[ \frac{2x_n}{n + 307} \right]. \quad \forall n \geqslant 0$$ First, it will be proved by induction on $n$ that $x_n = 13n + 2015$ for $0 \leqslant n \leqslant 23$. For $n = 0$ it is obvious. Now suppose it holds for $n$. Since$$2(13n + 2015) - 13(n + 307) = 13n + 39$$ and$$0 \leqslant n \leqslant 22 \Longrightarrow 0 \leqslant 13n + 39 < n + 307,$$ then$$x_{n + 1} = (13n + 2015) + \left[ \frac{2(13n + 2015)}{n + 307} \right] = 13(n + 1) + 2015.$$ End of induction.

Next, it will be proved by induction on $n$ that$$x_n = \begin{cases} (5m + 14)k + 635 · \dfrac{1}{2} m(m - 1) + 2033m + 2314; & n = 127m + k + 23,\ 0 \leqslant k \leqslant 24\\ (5m + 15)k + 635 · \dfrac{1}{2} m(m - 1) + 2033m + 2289; & n = 127m + k + 23,\ 25 \leqslant k \leqslant 50\\ (5m + 16)k + 635 · \dfrac{1}{2} m(m - 1) + 2033m + 2238; & n = 127m + k + 23,\ 51 \leqslant k \leqslant 75\\ (5m + 17)k + 635 · \dfrac{1}{2} m(m - 1) + 2033m + 2162; & n = 127m + k + 23,\ 76 \leqslant k \leqslant 100\\ (5m + 18)k + 635 · \dfrac{1}{2} m(m - 1) + 2033m + 2061; & n = 127m + k + 23,\ 101 \leqslant k \leqslant 126 \end{cases}$$ for $n \geqslant 23$, where $m$ and $k$ are integers. For $n = 23$, $x_{23} = 13 × 23 + 2015 = 2314$. Now suppose it holds for $n = 127m + k + 23$ where $0 \leqslant k \leqslant 126$.

If $0 \leqslant k \leqslant 24$, because\begin{align*} &\peq 2x_n - (5m + 14)(n + 307)\\ &= 2\left( (5m + 14)k + 635 · \dfrac{1}{2} m(m - 1) + 2033m + 2314 \right) - (5m + 14)(127m + k + 330)\\ &= (5m + 14)k + 3m + 8 \geqslant 0, \end{align*}$$(5m + 14)k + 3m + 8 < 127m + k + 330 \Longleftrightarrow (5m + 13)k < 124m + 322,$$ and $0 \leqslant k \leqslant 24$ implies$$(5m + 13)k \leqslant 120m + 312 < 124m + 322,$$ then\begin{align*} &\peq x_{n + 1} = x_n + \left[ \frac{2x_n}{n + 307} \right]\\ &= \left( (5m + 14)k + 635 · \dfrac{1}{2} m(m - 1) + 2033m + 2314 \right) + (5m + 14)\\ &= (5m + 14)(k + 1) + 635 · \dfrac{1}{2} m(m - 1) + 2033m + 2314. \end{align*} Note that $(5m + 14) × 25 + 2314 = (5m + 15) × 25 + 2289$, thus the proposition holds for $0 \leqslant k \leqslant 24$. If $25 \leqslant k \leqslant 50$, $51 \leqslant k \leqslant 75$, $76 \leqslant k \leqslant 100$ or $101 \leqslant k \leqslant 126$, analogous deduction with the fact that\begin{align*} &\peq (5m + 18) · 127 + 635 · \frac{1}{2} m(m - 1) + 2033m + 2061\\ &= 317.5 m^2 + 2350.5 m + 4347\\ &= (5(m + 1) + 14) · 0 + 635 · \frac{1}{2} (m + 1)m + 2033(m + 1) + 2314 \end{align*} shows that the proposition also holds. End of induction.

Now for $n \geqslant 23$, suppose $n = 127m + k + 23$, where $0 \leqslant k \leqslant 126$, then\begin{gather*} x_n \geqslant x_{127m + 23} = \frac{1}{2} · 635m(m - 1) + 2033m + 2314,\\ x_n \leqslant x_{127(m + 1) + 23} = \frac{1}{2} · 635m(m + 1) + 2033m + 4347,\\ 127m + 23 = y_{127m + 23} \leqslant y_n \leqslant y_{127(m + 1) + 23} = 127m + 150. \end{gather*} Because\begin{gather*} \lim_{m → ∞} \frac{\dfrac{1}{2} · 635m(m - 1) + 2033m + 2314}{(127m + 150)^2} = \frac{\dfrac{1}{2} · 635}{127^2} = \frac{5}{254},\\ \lim_{m → ∞} \frac{\dfrac{1}{2} · 635m(m + 1) + 2033m + 4347}{(127m + 23)^2} = \frac{5}{254}, \end{gather*} then$$\lim_{n → ∞} \frac{x_n}{y_n^2} = \frac{5}{254} ≈ 0.01968504.$$

By your attempt we now that a limit exists, so we need to find just a limit of a subsequence of $\frac{x_{t(n)}}{y_{t(n)}^{2}}$ and that limit will be equal to the limit of the whole sequence. So, it's easy to check numerically that $$x_{127(k-1)+1}=740+k\frac{1941}{2}+k^2\frac{635}{2}$$ holds $\forall k \geq 1 \in \mathbb{N}$. I'll try to demonstrate this equation later in this answare. The following is a simple limit knowing that $$x(n)= 740 + n\frac{1941}{254}+n^2\frac{5}{254}$$ $$y(n) = 307 + n$$ So $$\lim_{n\to\infty} \frac{x(n)}{y(n)^2}= \frac{740 + n\frac{1941}{254}+n^2\frac{5}{254}}{94249 + 614 n + n^2}=\frac{5}{254}$$

# Not really a demonstration... yet

First it easy to check that for $g(t)=A+t$ $$\frac{g(t+1)}{g(t-1)}=\frac{A+t+1}{A+t-1}=\frac{A+t-1+2}{A+t-1}=1+\frac{2}{A+t-1}=1+\frac{2}{g(t-1)}$$ holds for evry real number if $g(t-1)\neq0$.

So in our case the equality $$x_n=\left\lfloor x_{n-1}\frac{y_{n+1}}{y_{n-1}}\right\rfloor = \left\lfloor x_{n-1} \left( 1+\frac{2}{y_{n-1}} \right) \right\rfloor = x_{n-1}+\left\lfloor \frac{2 x_{n-1}}{y_{n-1}}\right\rfloor$$ holds $\forall n \in \mathbb{N}$. Then is true that $$x_{127(k-1)+1}=x_{127(k-1)}+\left\lfloor \frac{2 x_{127(k-1)}}{y_{127(k-1)}}\right\rfloor$$

I do not know how to go forward...