# Linear recurrence solving for tighest possible big O bounds

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?

• Do you know how to solve recurrence of this type? It is fairly straightforward – Shubham Johri Dec 15 '18 at 22:13
• I think the best constant is $\frac{3+\sqrt{17}}{2} \approx 3.55$ instead of $4$. – Mindlack Dec 15 '18 at 22:28
• Do not change your question after it has been answered. – Joel Reyes Noche Dec 18 '18 at 13:13

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$$