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.$$
Just adding some results from a numerical computation of the first $n = 4000$ $a_n$'s in case anyone is interested to see how the sequence grows. The Mathematica code used (probably not very efficient) is given at the end. I compute $f_n(x)$ by solving the reccurence: $g_{i+1} = (x + g_i)^{n-i}$ with $g_1 = x^n$. This way we have $f_n(x) = g_n$.
Here you can see $\frac{\log(a_n)}{n}$,
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$
and here you can see the ratio $\frac{a_{n+1}}{a_n}$
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$
and here is a plot of $f(x)$ (well $f_{15}(x)$ however the plot below looks the same for larger $n$). The vertical line denotes $x = \frac{1}{\sqrt{2}}$ which seems to be a vertical asymptote for $f(x)$.
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$
(* Define the function f_n(x) *)
f[n_, x_] := Module[{res, i},
res = x^n;
Do[ res = (x + res)^(n - i); , {i, 1, n - 1}];
res
];
(* How many an's to compute? *)
numterms = 1000;
(* am stabilize for m > n(n-1)/2 so we only need to compute fn for n = nmax *)
nmax = Ceiling[Sqrt[2 numterms]];
(* Extract the coefficients *)
powerseries = Normal[Series[f[nmax, x], {x, 0, numterms}]];
an = Coefficient[powerseries, x, #] & /@ Range[0, numterms];
bn = Table[{i, Log[an[[i]]]/i}, {i, 1, Length[an]}];
cn = Table[{i, an[[i + 1]]/an[[i]]}, {i, 1, Length[an] - 1}];
(* Plot it up *)
ListLogLinearPlot[bn]
ListLogLinearPlot[cn]
Best Answer
$c_n$ is the coefficient of $x^n$ in $(1 + x + x^2)^n$. It follows that its generating function is the diagonal of the rational generating function
$$F(x, y) = \frac{1}{1 - y(1 + x + x^2)} = \sum_{n \ge 0} y^n (1 + x + x^2)^n = \sum f_{n, m} x^n y^m$$
in the sense that $c_n = f_{n, n}$. It's a general fact (which you can find stated, for example, as Theorem 6.3.3 in Stanley's Enumerative Combinatorics, Vol. II) that the diagonal of a bivariate rational generating function is algebraic and can be computed using contour integration, as explained in Stanley, and you can also see my blog post Extracting the diagonal. We can do the computation as follows. Write $C(r) = \sum c_n r^n$. Then for sufficiently small $r$ we have
$$\frac{1}{2 \pi i} \int_{\gamma} \frac{F(rz, rz^{-1})}{z} \, dz = C(r^2)$$
where $\gamma$ is the contour given by the unit circle. In our case the integrand is
$$\frac{F(rz, rz^{-1})}{z} = \frac{1}{z - r - r^2 z - r^3 z^2}$$
which, as a meromorphic function of $z$, has poles given by the zeroes of the denominator. These are the zeroes of a quadratic $r^3 z^2 + (r^2 - 1) z + r$, which are then
$$z_0, z_1 = \frac{(1 - r^2) \pm \sqrt{1 - 2r^2 - 3r^4}}{2r^3}$$
by the quadratic formula. We only need to consider the residue at a pole inside our contour for small $r$, and as $r \to 0$ the $+$ zero goes to infinity so we only need to consider the $-$ zero
$$z_0 = \frac{(1 - r^2) - \sqrt{1 - 2r^2 - 3r^4}}{2r^3}.$$
The residue at this pole is
$$\lim_{z \to z_0} \frac{z - z_0}{-r^3(z - z_0)(z - z_1)} = \frac{1}{-r^3(z_0 - z_1)} = \frac{1}{\sqrt{1 - 2r^2 - 3r^4}}$$
so the residue theorem gives
$$C(r^2) = \frac{1}{\sqrt{1 - 2r^2 - 3r^4}}$$
as desired.
Now some more general facts can be used to deduce asymptotics. The dominant singularity of $C(z) = \frac{1}{\sqrt{1 - 2z - 3z^2}} = \frac{1}{\sqrt{(1 - 3z)(1 + z)}}$ occurs at $z = \frac{1}{3}$. Around this singularity $C(z)$ looks like $\frac{1}{\sqrt{\frac{4}{3}(1 - 3z)}}$ which gives (using e.g. binomial expansion together with Stirling's formula) that the leading order asymptotic of $c_n$ is
$$\boxed{ c_n \sim \sqrt{\frac{3}{4 \pi n}} \, 3^n }.$$
This is in agreement with the comment left by Vaclav Kotesovec on the OEIS page, and in particular implies that the true value of $\lim_{n \to \infty} \frac{c_{n+1}}{c_n}$ is $3$ exactly. For much more on this topic see Chapter VI.1 of Flajolet and Sedgewick's Analytic Combinatorics.