it is already well explained . I think you should go through some theory about it then you will get the solution.

First how to generate characteristic equation :-

https://math.stackexchange.com/questions/166743/how-to-get-the-characteristic-equation

some theory about it:-

http://courses.ics.hawaii.edu/ReviewICS241/morea/counting/RecurrenceRelations2-QA.pdf

MIT video lecture Reference :-

You can also kenneth rosen book for this as well.