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?