Consider the sequence defined by $$ \begin{cases} r_0=1\\ r_1=3\\ r_n=6r_{n-1}-9r_{n-2} & \text{if }n\ge 2 \end{cases} .$$ Find a closed form for $r_n$.
The characteristic equation of the recurrence is $c^2-6c+9=0.$ But I don't know how to proceed. Solutions are greatly appreciated.
On
If you calculate the first few terms, you should notice a pattern:
$$\{1,3,9,27,81,243,729,\ldots\}$$
These are the powers of $3$. That is, $r_n = 3^{n}$.
To prove this, we can use induction. The base case is already covered.
Suppose $r_k = 3^k$ for all $k \le n$ and prove $r_{n+1} = 3^{n+1}$.
$$r_{n+1} = 6 r_{n} - 9 r_{n-1} = 6 \cdot 3^n - 9 \cdot 3^{n-1} = 3(2 \cdot 3^n - 3 \cdot 3^{n-1}) = 3\cdot3^n = 3^{n+1}$$
You are using the characteristic equation because you think that the solution could be of the form $r_n=c^n$.
Indeed, plugging this in the recurrence, you get
$$c^n=6c^{n-1}-9c^{n-2},$$ which is equivalent to the characteristic equation.
Now this equation gives you possible values of $c$, namely the double root $c=3$, so that $3^n$ is a solution. As it turns out that $3^0=1$ and $3^1=3$, the initial conditions are fulfilled and you are done.
Note that the theory establishes that a second order recurrence has a quadratic characteristic polynomial, which usually has two distinct roots (real or complex conjugate). These generate two linearly independent solutions which are able to deal with two arbitrary initial conditions.
In your case we were only able to find one root, hence one solution and it fitted both initial conditions by chance. A second, linearly independent solution is $nc^n$. Indeed, when plugging it in the recurrence equation,
$$n3^n=6(n-1)3^{n-1}-9(n-2)3^{n-2}$$ i.e. $$n3^n=2(n-1)3^{n}-(n-2)3^{n}$$ is an identity.
So the general solution of the equation is
$$r_n=(\alpha n+\beta)3^n,$$ where $\alpha,\beta$ are coefficients chosen to realize the initial conditions.