Given a recurrence relation of the form , its characteristic polynomial is . Let be the roots of that characteristic polynomial. If the roots are all distinct, then . If the roots are not distinct, the formula is a bit more complex, and not necessary for this problem. The proof of this requires differential equations, but the process is frequently taught without proof in discrete mathematics classes.
To solve for , you plug in the initial values . . Etc.
So, in this case, I used the characteristic polynomial to find . Plugging in and . This gave me a system of two equations in two variables. I solved for and , and plugged them in.