How do I find an explicit formula, using backtracking, for $C_n =3C_{n-1} -2C_{n-2}$ with initial values $C_1=5$ and $C_2=3$? I have the recurrence $C_n =3C_{n-1} -2C_{n-2}$ with initial values $C_1=5$ and $C_2=3$, and want to find an explicit formula for $C_n$.
I made a table with the terms up to the $6$th term and noticed:
\begin{align}
C_3 &= C_2-4\\
C_4 &= C_3-8\\
C_5 &= C_4-16\\
C_6 &= C_5-32
\end{align}
But I still can't find the correct formula.
 A: Those four equations you wrote mean: $$C_n = C_{n-1} -2^{n-1}.$$
Then you can use the recurrence directly: \begin{align} C_n &= C_{n-1} -2^{n-1}\\ &=C_{n-2} -2^{n-2} -2^{n-1}\\ &=C_{n-3} -2^{n-3} -2^{n-2} -2^{n-1}\\ &\vdots\\ &= C_1 -\sum_{k=1}^{n-1} 2^k\\ &= C_1 \bbox[yellow]{+1} -\sum_{k=\bbox[yellow]{0}}^{n-1} 2^k\\ &= C_1 +1 -(2^n -1)\\ &= C_1 +2 -2^n \qquad\qquad(C_1=5)\\ &=7 -2^n.\end{align} 
A: The characteristic equation $x^2=3x-2$ has distinct roots $2,1$ so there is an answer of the form $x_n=a \cdot 2^n +b \cdot 1^n.$ Find $a,b$ by matching the first two terms.
I got $a_n=7-2^n,$
A: I present to you the overkill method.
Suppose we have the general recurrence $f_n$ given by $$f_{n+2}=af_{n+1}+bf_n,\tag1$$
where $f_0,f_1,a,b$ are known constants. Define the generating function
$$f(x)=\sum_{n\ge0} f_nx^n=f_0+f_1x+f_2x^2+\dots$$
Multiply $(1)$ by $x^{n+2}$ and sum over $n\ge0$:
$$
\begin{align}
\sum_{n\ge0}f_{n+2}x^{n+2}&=ax\sum_{n\ge0}f_{n+1}x^{n+1}+bx^2\sum_{n\ge0}f_nx^n\\
\sum_{n\ge2}f_nx^n &=ax\sum_{n\ge1}f_nx^n+bx^2f(x)\\
f(x)-f_1x-f_0&=ax(f(x)-f_0)+bx^2f(x)\\
f(x)&=\frac{f_0+(f_1-af_0)x}{1-ax-bx^2}.\tag2
\end{align}
$$
We then write
$$
\frac{f_0+(f_1-af_0)x}{1-ax-bx^2}=\frac{\xi_1}{1-\zeta_1x}+\frac{\xi_2}{1-\zeta_2x},\tag3
$$
for constants $\zeta_1,\zeta_2,\xi_1,\xi_2$. Adding together the rational functions on the right hand side of $(3)$ and comparing coefficients on the numerator and denominator of each side, we get
\begin{align*}
    f_0&=\xi_1+\xi_2, \qquad \qquad &a&=\zeta_1+\zeta_2,\\
    af_0-f_1&=\xi_1\zeta_2+\xi_2\zeta_1, \qquad \qquad &b&=-\zeta_1\zeta_2.
\end{align*}
The solution to this system is
\begin{equation}
\begin{bmatrix} 
\zeta_1 \\
\zeta_2 \\
\xi_1 \\
\xi_2 \\
\end{bmatrix}
=
\begin{bmatrix}
\tfrac{a+\sqrt{D}}{2}\\
\tfrac{a-\sqrt{D}}{2}\\
\tfrac{1}{\sqrt{D}}\left(f_1+\tfrac{-a+\sqrt{D}}{2}f_0\right)\\
\tfrac{1}{\sqrt{D}}\left(-f_1+\tfrac{a+\sqrt{D}}{2}f_0\right)
\end{bmatrix},\qquad D=a^2+4b.
\end{equation}
Then from $(3)$ we can write $$f(x)=\xi_1\sum_{n\ge0}(\zeta_1x)^n+\xi_2\sum_{n\ge0}(\zeta_2x)^n=\sum_{n\ge0}(\xi_1\zeta_1^n+\xi_2\zeta_2^n)x^n, \qquad |x|\le 1/\min(|\zeta_1|,|\zeta_2|),$$
so that $$f_n=\xi_1\zeta_1^n+\xi_2\zeta_2^n,\qquad n\ge0.$$
Noticing that we have $C_n=f_{n-1}$, with $(f_0,f_1,a,b)=(5,3,3,-2)$ we get
\begin{equation}
\begin{bmatrix} 
\zeta_1 \\
\zeta_2 \\
\xi_1 \\
\xi_2 \\
\end{bmatrix}
=
\begin{bmatrix}
2\\
1\\
-2\\
7
\end{bmatrix}.
\end{equation}
Hence $$C_n=-2\cdot2^{n-1}+7\cdot1^{n-1}=7-2^n.$$
