Solving a recurrence relation with the characteristic polynomial
Solution 1:
The procedure for handling the roots is similar but not identical to that for differential equations. The repeated root of $3$ gives you basic solutions $x_n=3^n$ and $y_n=n3^n$, and every possible solution to the recurrence is then a linear combination of these. Thus, there are constants $A$ and $B$ such that $a_n=A3^n+Bn3^n$ for each $n\ge 0$. Now you use the initial conditions $a_0=0$ and $a_1=1$ to solve for $A$ and $B$.
More generally, a root $r$ of multiplicity $m$ gives you basic solutions $n^kr^n$ for $k=0,\ldots,m-1$.