That is, indeed, more bark than bite, but the bark is somewhat louder than mlk presented it.

First of all, let us define $X_k=\max(|x_k|,|x_{k-1}|)$ and notice that ${2n+1\choose 2k+1}\ge 2^{\min(k,n-k)}n$ for $1\le k\le n-1$, provided that $n$ is not too small. With all this, we have the recursive inequality
\begin{align}
X_n &\le X_{n-1}+\frac{C}{n^2}\sum_{k=1}^{n-1}2^{-\min(k,n-k)}X_kX_{n-k}
\\
&\le X_{n-1}+\frac{2C}{n^2}\sum_{k=1}^{n-1}2^{-k}X_kX_{n-k} \label{1}\tag{$\ast$}
\end{align}
for large enough $n$.
Our task will be to show that any such sequence $X_n$ is bounded. We'll do it in several steps. We shall also consider the majorant 
$Y_n$ of $X_n$ that is the same as $X_n$ until the recurrent inequality \eqref{1} kicks in and $2C/n$ becomes less than $\frac 12$ and beyond this point is defined by the recurrence
$$
Y_n=Y_{n-1}+\frac 1{2n}\sum_{k=1}^{n-1} 2^{-k}Y_kY_{n-k} \label{2}\tag{$\ast\ast$}
$$
 
We'll start with showing that $Y_n\le A^n$ for all $n\ge 1$ with some $A<+\infty$ 

Indeed, just take any $A>2$ for which the inequality holds for $Y_n$ before \eqref{2} kicks in and then use the trivial induction on $n$.

This makes the function 
$$
f(z)=\sum_{n=0}^\infty Y_nz^n
$$
well-defined and analytic in some neighborhood of $0$. Note now that it satisfies the differential equation
$$
z\frac d{dz}[(1-z)f(z)]=\frac 12[f(z/2)-Y_0]f(z)+P(z)\label{3}\tag{${\ast\ast\ast}$}
$$
where $P(z)$ is some polynomial. This equation allows one to analytically extend $f$ from any open disk to a twice larger one (treating $f(z/2)-Y_0$ as an already known function and thus viewing \eqref{3} as a linear differential equation for $f(z)$ and solving it by the standard formula) until you hit the singularity at $1$. For that last step (extending to the whole unit disk), we have the linear differential equation of the sort
$$
f'(z)=\frac{Q(z)}{1-z}f(z)+\frac{R(z)}{1-z}
$$
where $Q$ and $R$ are analytic up to the boundary ($f(z/2)$ is incorporated in $Q$), so the standard solution formula shows that $f$ can grow at most like $(1-|z|)^p$ for some large $p$ near the boundary, which, by Cauchy formulae, implies that $Y_n=O(n^p)$ and so is $X_n$.

Now it is time to use the full strength of \eqref{1}. Without loss of generality, we may assume that our initial $p$ is half-integer. Then, if $p\ge 3/2$, we can say that
$$
X_n-X_{n-1}\le \frac{C'}{n^2}\sum_{k=1}^{n-1}2^{-k}k^p(n-k)^p=O(n^{p-2})\,.
$$ 
which implies that $X_n=O(n^{p-1})$. Once we reach $O(n^{1/2})$ in this way, the next conclusion is that $X_n-X_{n-1}=O(n^{-3/2})$ and after that we conclude that $X_n$ is actually bounded.

But once it is bounded, the bark loudness reduces to the level described by mlk except there is one term in the sum where the coefficient is actually of order $n^{-2}$ rather than $n^{-3}$ (look at $k=0$). However, since it is just one, it is harmless.

The end.