11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What competition is this from? $\endgroup$ – Antonio Vargas Mar 16 '18 at 18:47
  • $\begingroup$ @AntonioVargas Berkeley Math Tournament $\endgroup$ – Cyclohexanol. Mar 16 '18 at 19:15
  • 1
    $\begingroup$ 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 $\endgroup$ – Yuriy S Apr 19 '18 at 9:03
  • $\begingroup$ 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$$ $\endgroup$ – Luca Savant Jul 28 '18 at 12:13
2
+25
$\begingroup$

$\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. $$

$\endgroup$
0
$\begingroup$

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...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.