I would like to prove that the following sequence of ratios $(x_n)$ where $x_n = c_n/c_{n-1}$ converges to a finite limit $L$:
$$\lim_{n\to\infty} x_n = \lim_{n\to\infty}\frac{c_n}{c_{n-1}} = L$$
Where $c_n$ is defined by the recurrence relation:
$c_n = c_{n-1} + \lfloor c_{n-4}/2 \rfloor$ for $n \geq 4$, with initial conditions $c_0=3, c_1=4, c_2=5, c_3=6$.
I feel there should be a similar approach to proving limit of consecutive Fibonacci numbers converges, which I think might require me to solve the recurrence, but the floor function doesn't help.
Some observations, verification by computer software has led me to predict that the limit tends towards $L = 1.25372495821…$, which appears to be very close to a solution to the equation:
$$x^4 – x^3 – \frac{1}{2}=0$$
This would be the characteristic equation to the recurrence relation $\alpha_n = \alpha_{n-1} + \alpha_{n-4}/2$, which is very similar to the way how $c_n$ is defined.
Any ideas? I exhausted most of the standard undergraduate analysis techniques for proving sequences converge, no luck though.
Best Answer
It is clear that $c_n\rightarrow\infty$, and $x_n\ge 1$ for all $n$. Note that $$ x_n = \frac{c_n}{c_{n-1}} = \frac{c_{n-1} + \lfloor\frac{c_{n-4}}{2}\rfloor}{c_{n-1}} = 1 + \frac{c_{n-2}}{c_{n-1}}\frac{c_{n-3}}{c_{n-2}}\frac{c_{n-4}}{c_{n-3}}\frac{\lfloor\frac{c_{n-4}}{2}\rfloor}{c_{n-4}} = 1 + \frac{1}{x_{n-1}x_{n-2}x_{n-3}}\frac{\lfloor\frac{c_{n-4}}{2}\rfloor}{c_{n-4}}. $$ Since $x_n\ge 1$ and $\frac{\lfloor\frac{c_{n-4}}{2}\rfloor}{c_{n-4}}\le\frac{1}{2}$ for all $n$, we have $$ x_n\le 1 + \frac{1}{1\cdot1\cdot1}\frac{1}{2} = \frac{3}{2} $$ for all $n$. Since $c_n\rightarrow\infty$, for every $\epsilon>0$ there exists $N$ such that if $n>N$, then $\frac{\lfloor\frac{c_{n-4}}{2}\rfloor}{c_{n-4}}\ge\frac{1}{2}-\epsilon$, and hence for $n>N$ we have $$ x_n\ge\frac{1}{\frac{3}{2}\frac{3}{2}\frac{3}{2}}\left(\frac{1}{2}-\epsilon\right) = 1 + \left(\frac{2}{3}\right)^3\left(\frac{1}{2}-\epsilon\right). $$ Letting $\alpha$ be the constant on the right-hand side, we again have $$ x_n \le 1 + \frac{1}{\alpha\alpha\alpha}\frac{1}{2} = 1 + \frac{1}{2\alpha^3} $$ for $n>N$. We continue with the bounds similarly, hoping that the lower and upper bounds converge.
Specifically, we make the following claim:
Claim: Let $\alpha_0 = 1$, and let $\{\epsilon_m\}$ be a decreasing sequence converging to $0$. Define the sequences $\{\alpha_m\}$ and $\{\beta_m\}$ as follows: \begin{align*} \beta_m &= 1 + \frac{1}{2a_m^3} \\ \alpha_{m+1} &= 1 + \frac{1}{\beta_m^3}\left(\frac{1}{2}-\epsilon_m\right) \end{align*} Then, for each $m$, there exists $N_m$ such that if $n>N_m$, then $$ \alpha_m\le x_n\le \beta_m. $$
Proof: Suppose $\alpha_m\le x_n\le\beta_m$ for $n>N_m$. Let $N$ satisfy $\frac{\lfloor\frac{c_{n-4}}{2}\rfloor}{c_{n-4}}\ge\frac{1}{2}-\epsilon_m$ for $n>N$ and $N\ge N_m+3$. Then, for $n>N$, we have $$ x_n = 1 +\frac{1}{x_{n-1}x_{n-2}x_{n-3}}\frac{\lfloor\frac{c_{n-4}}{2}\rfloor}{c_{n-4}} \ge 1+\frac{1}{\beta_m^3}\left(\frac{1}{2}-\epsilon_m\right) = \alpha_{m+1}. $$ If we let $N_{m+1} = N+3$, then for $n>N_{m+1}$ we also have $$ x_n = 1 +\frac{1}{x_{n-1}x_{n-2}x_{n-3}}\frac{\lfloor\frac{c_{n-4}}{2}\rfloor}{c_{n-4}}\le 1 + \frac{1}{\alpha_{m+1}^3}\frac{1}{2} = \beta_{m+1} $$ as desired. $\square$
Now, we wish to show that $\{\alpha_m\}$ and $\{\beta_m\}$ are increasing and decreasing, respectively. Suppose $\alpha_m\ge\alpha_{m-1}$ and $\beta_m\le\beta_{m-1}$ (this is easily to be seen to be true for $m=1$). Then $$\alpha_{m+1} = 1 + \frac{1}{\beta_m^3}\left(\frac{1}{2}-\epsilon_m\right) \ge 1 + \frac{1}{\beta_{m-1}^3}\left(\frac{1}{2}-\epsilon_{m-1}\right) = \alpha_{m}$$ since $\beta_m\le\beta_{m-1}$ and $\epsilon_m\le\epsilon_{m-1}$. Similarly, we have $$\beta_{m+1} = 1 + \frac{1}{2\alpha_{m+1}^3}\le 1+\frac{1}{2\alpha_m^3} = \beta_m.$$ It follows that $\{\alpha_m\}$ and $\{\beta_m\}$ converge to the limits $\alpha$ and $\beta$, respectively, and these limits satisfy \begin{align*} \beta &= 1 + \frac{1}{2\alpha^3} \\ \alpha &= 1 + \frac{1}{2\beta^3} \end{align*} (the second equality follows from the fact that $\epsilon_m\rightarrow 0$). This implies that $$ \alpha\left(1+\frac{1}{2\alpha^3}\right) = \left(1 + \frac{1}{2\beta^3}\right)\beta\implies \alpha+\frac{1}{2\alpha^2} = \beta + \frac{1}{2\beta^2}. $$ Since $x\mapsto x + \frac{1}{2x^2}$ is strictly increasing on $(1,\infty)$, and $\beta\ge\alpha>1$, it follows that $\alpha = \beta$. Thus, by the sandwich property, we have $$\lim\limits_{n\rightarrow\infty}{x_n} = \alpha$$ where $\alpha$ satisfies $$\alpha = 1 + \frac{1}{2\alpha^3}\iff \alpha^4 - \alpha^3 - \frac{1}{2} = 0.$$