I ran into this problem while reviewing linear algebra and got stuck, I am out of prolific ideas to convert $x_n= \lfloor (4+\sqrt{11})^n \rfloor$ into some characteristic polynomial of a recurrence relation. By the way, the problem requests that I prove $x_n$ satisfies a linear recurrence relation, not necessarily to come up with the recurrence's equation itself.
Can $\lfloor (4+\sqrt{11})^n \rfloor$ be described as a linear recurrence relation
recurrence-relations
Related Solutions
It's not correct. A counterexample: $$x_n = \frac43x_{n-1}-\frac43x_{n-2}\quad\text{or}\quad x_n = -\frac43x_{n-1}-\frac43x_{n-2}$$ $$x_n = 1,2,-4,-8,16,32,-64,\dots$$ The sequence grows as $2^n$. The roots of the recurrences are $\dfrac{\pm 2\pm 2\sqrt{2}i}{3}$, each of absolute value $\dfrac{2}{\sqrt{3}} < 2$.
Now, your application to complexity problems should come with some positivity requirements, which would rule out this example. It might be enough to salvage things, but I can't say without further study.
OK, I've come back to it. Assume the sequence $x_n$ is positive (for $n\ge 0$) and the recurrences $x_n^{(j)}=c_1^{(j)}x_{n-1}+c_2^{(j)}x_{n-2}+\cdots+c_{k}^{(j)}x_{n-j}$ have nonnegative coefficients $c_i^{(j)}$.
In this form, each of the characteristic equations $t^k-c_1^{(j)}t^{k-1}-c_2^{(j)}t^{k-2}-\cdots - c_k^{(j)}$ has exactly one positive real root $b_j$, and this $b_j$ has the largest absolute value of any root. Let $B$ be the maximum of the $b_j$. Now, normalize: let $y_n = B^{-n}x_n$, and transform the recurrences to fit the new sequences. The new recurrences are \begin{align*}y_n^{(j)} &= B^{-1}c_1^{(j)}y_{n-1}+B^{-2}c_2^{(j)}y_{n-2}+\cdots+B^{-k}c_k^{(j)}y_{n-k}\\ y_n^{(j)} &= d_1^{(j)}y_{n-1}+d_2^{(j)}y_{n-2}+\cdots+d_k^{(j)}y_{n-k}\end{align*} with $y_n\in \{y_n^{(j)}\}$, naming the new coefficients $d_i^{(j)}$. What's the point? Since $t^k-c_1^{(j)}t^{k-1}-c_2^{(j)}t^{k-2}-\cdots-c_k^{(j)} \ge 0$ for $t\ge b_j$, it's nonnegative for $t = B$ and all $j$. After scaling by those powers of $B$, $$1-d_1^{(j)}-d_2^{(j)}-\cdots-d_k^{(j)}\ge 0$$ for all $j$. Consequently, if each of $y_{n-1},y_{n-2},\dots,y_{n-k}$ is $\le P$ for some constant $P$, so is $y_n^{(j)}$. If we take enough initial conditions to cover all of the recurrences and let $P$ be the maximum of those initial conditions, then, by induction, $y_n\le P$ for all $n$.
Multiply by $B^n$ to go back to the $x_n$, and that's it: $x_n\le PB^n$, where $P$ is some constant depending on initial conditions and $B$ is the largest root of the characteristic equations for the recurrences.
Let $S_k$ be the set of sequences $\langle x_1,\ldots,x_n\rangle$ such that $x_i\in[k]$ for $i=1,\ldots,n$ and $x_i\le\frac{x_{i+1}}2$ for $i=1,\ldots,n-1$; $s_k=|S_k|$. Suppose that $\sigma=\langle x_1,\ldots,x_n\rangle\in S_k$. If $x_n<k$, then $\sigma\in S_{k-1}$. And $S_{k-1}\subseteq S_k$, so there are $s_{k-1}$ sequences in $S_k$ whose last term is less than $k$. If $x_n=k$, then $x_{n-1}\le\frac{x_n}2$, so $\langle x_1,\ldots,x_{n-1}\rangle\in S_{\lfloor k/2\rfloor}$. That is, every sequence in $S_k$ whose last term is $k$ is obtainted from a sequence in $S_{\lfloor k/2\rfloor}$ by appending a term $k$. Conversely, if $\langle x_1,\ldots,x_{n-1}\rangle\in S_{\lfloor k/2\rfloor}$, then $\langle x_1,\ldots,x_{n-1},k\rangle\in S_k$, so there are $s_{\lfloor k/2\rfloor}$ sequences in $S_k$ that end in $k$. Every $\sigma\in S_k$ either does or does not end in $k$, and none does both, so we’ve counted every sequence in $S_k$ once, and $s_k=s_{k-1}+s_{\lfloor k/2\rfloor}$.
We can infer the relationship
$$\frac{F(x)}{F(x^2)}=\frac{1+x}{1-x}\tag{1}$$
directly from the recurrence without determining the generating function $F(x)$ itself. Rewrite the recurrence as $s_k-s_{k-1}=s_{\lfloor k/2\rfloor}$, multiply through by $x^k$, and sum over $k\ge 0$:
$$\sum_{k\ge 0}s_kx^k-\sum_{k\ge 0}s_{k-1}x^k=\sum_{k\ge 0}s_{\lfloor k/2\rfloor}x^k\;.$$
The lefthand side is
$$\begin{align*} \sum_{k\ge 0}s_kx^k-\sum_{k\ge 0}s_{k-1}x^k&=F(x)-x\sum_{k\ge 0}s_{k-1}x^{k-1}\\ &=F(x)-x\sum_{k\ge 0}s_kx^k\\ &=(1-x)F(x)\;, \end{align*}$$
and the righthand side is
$$\begin{align*} \sum_{k\ge 0}s_{\lfloor k/2\rfloor}x^k&=\sum_{k\ge 1}s_k(x^{2k}+x^{2k+1})\\ &=(1+x)\sum_{k\ge 0}s_kx^{2k}\\ &=(1+x)F(x^2)\;, \end{align*}$$
so $(1-x)F(x)=(1+x)F(x^2)$, and $(1)$ follows immediately.
The sequence is OEIS A000123, and the generating function apparently does not have a nice form.
Best Answer
Let $a_n=(4+\sqrt{11})^n, b_n=(4-\sqrt{11})^n$. Because $4\pm \sqrt{11}$ are the roots to the equation $x^2-8x+5$, anything of the form both $r_n=\alpha a_n+\beta b_n$ will satisfy the recurrence $r_{n+1}=8r_n-5r_{n-1}$ (why?). If we can show that $x_n$ is of this form, we will be done. There will be a slight hiccup, but we will deal with it.
Our first observation is that $0<4-\sqrt{11}<1$, so $0<b_n<1$. The second is that $a_n+b_n$ is a whole number, which can be seen by taking conjugates (sending $x+y\sqrt 5$ to $x-y\sqrt 5$), and seeing that it is its own conjugate, which means it must be a whole number.
Put together, this yields that $a_n+b_n=\lceil (4+\sqrt{11})^n\rceil$. Unfortunately, we wanted the floor, not the ceiling. But since the ceiling is simply one more than the floor, this yields
$$x_{n+1}+1=8(x_n +1)-5(x_{n-1} +1).$$
Rearranging, this becomes
$$x_{n+1}=8x_n-5x_{n-1}+2,$$
which is unfortunately not linear because of the $+2$. This can be fixed, however, by finding a linear recurrence that both $x_n+1$ and $r_n=1$ both satisfy, because then $x_n=(x_n+1)-r_n$
The trick is that $(x^2-8x+5)(x-1)=0$ has roots $1$ and $4\pm \sqrt{11}$, and expanding out we get $x^3=9x^2-13x+5$, so $x_n=(4+\sqrt{11})^n+(4-\sqrt{11})^n-1^n$ satisfies $$x_{n+1}=9x_n-13x_{n-1}+5x_{n-2}.$$