Characteristic equation of a recurrence relation Yesterday there was a question here based on solving a recurrence relation and then when I tried to google for methods of solving recurrence relations, I found this, which gave different ways of solving simple recurrence relations.  
My question is how do you justify writing the recurrence relation in its characteristic equation form and then solving for its roots to get the required answer.
For example, Fibonacci relation has a characteristic equation $s^2-s-1=0$.
How can we write it as that polynomial? 

We aren't writing the Fibonacci relation as $s^2-s-1=0$, we are noting a relation between that equation and the Fibonacci relation. We are noting that if $r$ is a solution of the characteristic equation, then $r^n$ is a solution of the recurrence relation. 
