Linear recurrence solving for tighest possible big O bounds

Question

I am dealing with the following linear recurrence:

X₀ = 1

X₁ = 2

X_n = 3X_n-1 + 2X_n-2

I have proven that this has an upper bound of O(4ⁿ)

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$. — Aphelli, Dec 15 '18 at 22:28

score 1 · Answer 1 · answered Dec 15 '18 at 22:28

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$

Linear recurrence solving for tighest possible big O bounds

1 Answers1