I've been doing a bunch of exercises where I need to find the explicit formula for a given sequence... $$a_{n+2} = 6 a_{n+1} - 9 a_{n}$$ The first were easy with $a_{0} = 1$ and $a_{1} = 3$ i.e.. But now I have these: $$a_{0} = 0$$ $$a_{1} = 3$$
And I can't break down the pattern easily, so I'm thinking that there must be a procedure around it. I'm not looking for the answer to this particular problem, just for hints or suggestions on how to face these sort of exercises. Thanks!
For a linear recurrence relation with constant coefficients, the basic candidates for solutions are $r^n$ where $r$ is any root of the characteristic polynomial. For instance in your example the characteristic polynomial is $p(x)=x^2-6x+9$ which has a root of $3$. Any linear combination of these solutions is also a solution because of linearity.
It can happen that the order of your recurrence relation (2 in your case) is higher than the number of roots of the characteristic polynomial (1 in your case). This happens because the characteristic polynomial has a root of a multiplicity higher than $1$. In this case, in addition to $r^n$, there are solutions $n r^n,n^2 r^n,\dots,n^{m-1}r^n$, where $m$ is the multiplicity. Thus in your case all solutions to the recurrence are of the form $c_1 3^n + c_2 n 3^n$, where $c_1,c_2$ are constants. By finding $c_1,c_2$ matching your initial condition you solve the recurrence. The case $a_0=1,a_1=3$ was easy because you had $c_2=0$, but in your other case you will not have that.