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?
Best Answer
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}}$.