How to solve the following recurrence?

Question

I am not familiar with recurrence-solving techniques outside of the master theorem, recursion trees, and the substitution method. I am guessing that solving the following recurrence for a big-O bound does not utilize one of those methods:

T(n) = T(n-1) + 2T(n-2) + 1

Aardwolf

What is the base case for T(n) ? – Trainee

This is a great spot to use the annihilator method... which I don't actually know how to do. :-) – Kendyl

A base case is not provided. I'm guessing it is not needed to achieve a big-O bound? – Aardwolf

Hint: T(n) = 2^n. Additionally, look at this math stackexchange question. – Urethroscope

Answer 1

We can make the substitution U(n) = T(n) + 1/2 and then get a recurrence

U(n) = T(n) + 1/2
     = T(n-1) + 2T(n-2) + 1 + 1/2
     = T(n-1) + 1/2 + 2(T(n-2) + 1/2)
     = U(n-1) + 2U(n-2),

which is a little magic but, as templatetypedef mentions, the magic can be created with the annihilator method. Now we just have to solve the linear homogeneous recurrence. The characteristic polynomial x^2 - x - 2 factors as (x+1)(x-2), so the solutions are U(n) = a(-1)^n + b2^n where a and b are any constants. Equivalently, T(n) = a(-1)^n + b2^n - 1/2, which is Theta(2^n) except in special cases.

Macaroni

Answer 2

This recursion is called non-homogeneous linear recurrence. and it is solved by converting it to a homogeneous one:

T(n) = T(n-1) + 2T(n-2) + 1
T(n+1) = T(n) + 2T(n-1) + 1

Subtracting 1 from 2 and changing the base, you get T(n) = 2 T(n-1) + T(n-2) - 2 T(n-3). The corresponding characteristic equation is:

x^3 - 2x^2 - x + 2 = 0

which has solutions x = {-1, 1, 2}. This means that the recursion looks like:

c1 * (-1)^n + c2 * 2^n + c3 * 1^n = c1 * 2^n + c2 (-1)^n + c3

Where all these constants can be found knowing T(0) and T(1). For your complexity analysis it is clear that this is exponential O(2^n).

Ribera