Derive a homogenous linear recurrence from $x_n=2^n+F_n$ Suppose that the sequence $x_n$ satisfies that $$x_n = 2^n + F_n$$ where $\{F_n \}$ denotes the Fibonacci sequence, I want to derive a homogenous linear recurrence for $x_n$
I can show that $$x_n-x_{n-1}-x_{n-2} = \frac{1}{4}2^n$$ By plug in the relationship of Fib Sequence, however the above is non-homogenous, can anyone help?
 A: The sequence $2^n$ solves the  homogeneous linear recurrence $x_n-2x_{n-1}=0$
and $F_n$ solves the homogeneous linear recurrence $x_n-x_{n-1}-x_{n-2}=0$. Now consider the homogeneous linear recurrence whose characteristic polynomial is the product
$$(x-2)(x^2-x-1)=x^3-3x^2+x+2.$$
Since it has $3$ distinct roots, that is $2$ and $\frac{1\pm\sqrt{5}}{2}$, then all solutions of the homogeneous linear recurrence of order $3$,
$$x_n-3x_{n-1}+x_{n-2}+2x_{n-3}=0$$
are given by
$$x_n=C_1\,2^n+C_2\,\left(\frac{1+\sqrt{5}}{2}\right)^n+C_3\,\left(\frac{1-\sqrt{5}}{2}\right)^n.$$
Your sequence $2^n + F_n$ is just one of them: $C_1=1$, $C_2=\frac{1}{\sqrt{5}}$ and $C_3=-\frac{1}{\sqrt{5}}$.
A: The following fills in the missing step in OP's approach.

I can show that $\;x_n-x_{n-1}-x_{n-2} = \frac{1}{4}2^n$

You are almost done at this point. All that's left to do is eliminate the power terms between two consecutive relations:
$$
\begin{align}
x_n-x_{n-1}-x_{n-2} &= \frac{1}{4}2^n \tag{1}
\\ x_{n+1}-x_{n}-x_{n-1} &= \frac{1}{4}2^{n+1} \tag{2}
\end{align}
$$
Multiplying and subtracting $(2) - 2 \times (1)$ gives:
$$
\require{cancel}
x_{n+1}-x_{n}-x_{n-1} - 2\left(x_n-x_{n-1}-x_{n-2}\right) = \cancel{\frac{1}{4}2^{n+1}} - \cancel{2 \cdot \frac{1}{4}2^n}
\\ \iff\;\;\;\; x_{n+1}-3x_n+x_{n-1}+2x_{n-2} = 0
$$
A: You can rewrite it considering $\begin{cases}b_{n+1}=2b_n\\F_{n+2}=F_{n+1}+F_n\end{cases}\quad$ to $\quad x_n=b_n+F_n$
Since we have $x_{n+2}-x_{n+1}-x_{n}=\underbrace{\Big(F_{n+2}-F_{n+1}-F_n\Big)}_0+\underbrace{\Big(b_{n+2}-b_{n+1}-b_n\Big)}_{b_n}=b_n$
Then $b_{n+1}=2b_n$ gives you the relationship between $x_{n+3},\ x_{n+2},\ x_{n+1},\ x_n$
