discrete mathematics - Having a lot of trouble solving this recurrence with iteration and finding a closed form...

I'm learning discrete math and didn't have any trouble with any recurrences in the examples I went over through the chapters on it, but this one problem at the end of the first chapter is killing me, and there's no solution in the book. There's got to be some trick to it that I'm just not seeing. Below is the recurrence and how I'm trying to solve it.

So, right off the bat this one confuses me because $a_0=1$. So, if I try to solve for $a_1$ just by plugging in $a_0$, I get 1. This continues on and and on and on for an as $n$ increases. So, I tried using iteration to go up to $a_5$ to find a pattern.

I get:
$a_5 = 3(a_4)-2 = 3a_0^5-2(3^4)-2(3^3)-2(3^2)-2(3)-2$. Now, this kind of looks like a geometric sequence, but it's all subtracting vs adding, and if I plug one in for $a_0$, I get $1-2(3^4)-2(3^3)-2(3^2)-2(3)-2$. Is my closed form then $a_n=1-2(3^n-1)$? This just doesn't seem right to me.

Then if I try to solve by induction to try and check my answer, I get:
Basis: (used 0 since I don't know 1) for $n=0$, $a_n=1-2(3^{n-1}) = 1-2(3^{0-1}) = 1$ which is true.

NTS: $n_K+1=1-2(3^{k+1-1})$
so, $n_k+1=3a_k-1-2
=3(1-2(3^k-1))-2$ <-- and then I get stuck here, so I can't verify by induction.

Thanks, any input is highly appreciated. I'm ripping my hair out over this.

Answer

Just iterate:

$$\begin{align*}
a_n&=3a_{n-1}-2\\

&=3(3a_{n-2}-2)-2\\
&=3^2a_{n-2}-3\cdot2-2\\
&=3^2(3a_{n-3}-2)-3\cdot2-2\\
&=3^3a_{n-3}-3^2\cdot2-3\cdot2-2\\
&\;\vdots\\
&=3^ka_{n-k}-3^{k-1}\cdot2-3^{k-2}\cdot2-\ldots-3\cdot2-2\\
&\;\vdots\\
&=3^na_0-3^{n-1}\cdot2-3^{n-2}\cdot2-\ldots-3\cdot2-2\\
&=3^n-3^{n-1}\cdot2-3^{n-2}\cdot2-\ldots-3\cdot2-2\\
&=3^n-2\sum_{k=0}^{n-1}3^k\\

&\overset{*}=3^n-2\cdot\frac{3^n-1}{3-1}\\
&=3^n-(3^n-1)\\
&=1\;.
\end{align*}$$

The starred step just used the formula for the sum of a geometric series.

Of course properly speaking you should now go back and prove by induction that $a_n$ really is $1$ for all $n$.

Note that you really didn’t need to unravel the recurrence in order to solve it: once you calculate $a_1$ and $a_2$, say, it should be obvious that the calculation is identical each time and that you’re going to get $a_n=1$ for all $n$. Once you make that easy guess, you can go ahead and prove by induction on $n$ that it’s correct.

Another elementary technique that you can use on recurrences of the form $x_n=ax_{n-1}-b$ is to make a substitution, shifting the variable by a constant amount. I’ll illustrate with your example

Let $b_n=a_n-d$ for some constant $d$ that will be determined in a bit. Then $a_n=b_n+d$, and the recurrence $a_n=3a_{n-1}-2$ can be rewritten as $b_n+d=3(b_{n-1}+d)-2=3b_{n-1}+3d-2$, which simplifies to $b_n=3b_{n-1}+2d-2$. If we set $d=1$, this becomes simply $b_n=3b_{n-1}$. You probably recognize at once that the solution to this recurrence is just $b_n=3^nb_0$. And since $a_n=b_n+1$, we’ll have the solution $a_n=3^nb_0+1$ as soon as we determine $b_0$. But that’s easy: $b_0=a_0-d=a_0-1=0$, so $a_n=1$ for all $n$.