0
$\begingroup$

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?

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

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy