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$?

Question

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.

Answer 1

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}

Answer 2

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,$

Answer 3

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.$$