I am dealing with the following linear recurrence:
X0 = 1
X1 = 2
Xn = 3Xn-1 + 2Xn-2
I have proven that this has an upper bound of O(4n)
However, I have been asked to come up with tighter bounds for this linear recurrence, but I dont know how to begin this. Does this involve solving the recurrence?
Write the solution as
$$ x_n = a \lambda^n $$
If you replace that in your original expression you get
$$ a \lambda^n = 3 a \lambda^{n - 1} + 2 a\lambda^{n-2} $$
Which reduces to
$$ \lambda^2 = 3 \lambda + 2 $$
Solutions are
$$ \lambda = \frac{3}{2} \pm \frac{\sqrt{13}}{2} $$
So the solution is
$$ x_n = a \left( \frac{3}{2} + \frac{\sqrt{13}}{2} \right)^n + b\left( \frac{3}{2} - \frac{\sqrt{13}}{2} \right)^n $$
The constants $a$ and $b$ you can determine by setting $n=0$ and $n=1$ and using the conditions $x_0 = 1$ and $x_1 = 2$