what is the intuition behind treating recurrence relationship as polynomial?
I have seen this method used in discrete maths where we treat the following equation:
an = an-1 + an-2
as:
x^2^ = x + 1
then solve the equation and let's say we got roots r1 and r2 then the recurrence relationship can be written as:
an=c1*(r1)^n^ + c2*(r2)^n^
what do we do to expand that recurrence relation so that this patten emerge?






