How to deal with linear recurrence that it's characteristic polynomial has multiple roots? example ,
$$
a_n=6a_{n-1}-9a_{n-2},a_0=0,a_1=1
$$
what is the $a_n$?
In fact, I want to know there are any way to deal with this situation.
 A: We assume that you are dealing with linear homogeneous recurrences with constant coefficients. 
When the characteristic equation has degree $2$ and a double root $r$, the general solution is $Ar^n +Bnr^n$.
If the equation has degree $3$, a double root $r$ and a single root $s$, use $Ar^n+Bnr^n+Cs^n$.
If there is a triple root $r$, use $Ar^n+Bnr^n+Cn^2r^n$.
And so on.
Remark: The situation is analogous to what we do with linear homogeneous differential equations with constant coefficients when the characteristic equation has multiple roots. 
A: Here is a fun way to get to the answer:
Suppose we have a recursion $A_n = c_1A_{n-1} + c_2A_{n-2} + \dots + c_kA_{n-k}$.  When you are doing the usual approach, you are looking for geometric sequences that satisfy this recursion, and you end up looking for nonzero roots $r$ of:
$$x^n = c_1x^{n-1} + c_2x^{n-2} + \dots + c_k x^{n-k}$$
Now remember that when we have a double root of a polynomial, then it is also a root of the derivative of that polynomial. So if we are in that case and $r$ is a double root of this let's differentiate the above equation, and then multiply by $x$ to keep it looking nice:
$$nx^n = c_1(n-1)x^{n-1} + c_2(n-2)x^{n-2} + \dots + c_k(n-k) x^{n-k}$$
We know $r$ must still must be a root of this, so we plug in $r$ and look carefully this says that the sequence $A_n = nr^n$ satisfies our original recursion. Hooray!
If $r$ is a root of multiplicity more than 2, then we can differentiate the equation more times to get more sequences of the form $A_n = n^kr^n$ for $k$ less than the multiplicity of $r$.
I know another way to get at this using linear algebra that I think is a bit more enlightening as to why these are the answers, and why you never get anything else, but in my opinion this differentiation trick is pretty slick.
A: A bare-hands method would be as follows:
$$a_n - 3 a_{n-1} = 3 ( a_{n-1} - 3 a_{n-2} )$$
$$a_n - 3 a_{n-1} = 3^{n-1} ( a_1 - 3 a_0 )$$
$$\sum_{k=1}^n 3^{n-k} ( a_k - 3 a_{k-1} ) = \sum_{k=1}^n 3^{n-k} \left( 3^{k-1} ( a_1 - 3 a_0 ) \right)$$
$$\sum_{k=1}^n 3^{n-k} a_k - 3^{n-(k-1)} a_{k-1} = \sum_{k=1}^n 3^{n-1} ( a_1 - 3 a_0 )$$
$$a_n - 3^n a_0 = n 3^{n-1} ( a_1 - 3 a_0 )$$
The constants were obtained from the factorization of the quadratic.
Note that the above method works regardless of whether the roots are repeated, although the last step will differ.
