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

Question

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 1

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

Answer 2

Using the methods from Wilf's "generatingfunctionology", define the ordinary generating function $A(z) = \sum_{n \ge 0} a_n z^n$. If you write the recurrence as: $$ a_{n + 1} = 3 a_n - 2 $$ you see that the recurrence is valid for $n \ge 0$. Multiply by $z^n$ and sum for $n \ge 0$: $$ \sum_{n \ge 0} a_{n + 1} z^n = 3 \sum_{n \ge 0} a_n z^n - 2 \sum_{n \ge 0} z^n $$ The first sum is $\frac{A(z) - a_0}{z}$, the second is $A(z)$, the third a geometric series: $$ \frac{A(z) - 1}{z} = 3 A(z) - 2 \frac{1}{1 - z} $$ This gives: $$ A(z) = \frac{1}{1 - z} $$ and so $a_n = 1$.

Answer 3

Consider $a_n = 3a_{n-1} -2$ for $n \geq 1$. Note that

$$\begin{split} a_n &= 3a_{n-1} -2 = 3 (3a_{n-2}-2) -2 = 3^2 a_{n-2} -3 \cdot 2 -2 \\ &= 3^2 (3a_{n-3} - 2) -3 \cdot 2 -2 = 3^3 a_{n-3} -3^2 \cdot 2 - 3 \cdot 2 -2 \\ &= 3^3 a_{n-3} -2 \sum_{k=0}^{2} 3^k \\ &= \ldots \\ &= 3^n a_{n-n} - 2 \sum_{k=0}^{n-1} 3^k = 3^n a_0 - 2 \frac{3^n-1}{3-1}\\ &= 3^n (a_0 - 1) + 1. \end{split} $$

Now with $a_0 = 1$, you have $a_n \equiv 1$ as you have correctly suspected.

Answer 4

On this one, $a_n=1 \; \forall n \ge 0$. You can see this from just plugging in values and getting $1$ repeatedly, or you can actually solve the equation by breaking up the solution into homogeneous and inhomogeneous parts. The homogeneous part is

$$a_n^{(H)} = 3 a_{n-1}^{(H)} \implies a_n^{(H)} = A \cdot 3^n$$

for some constant $A$. The inhonogeneous part is just $1$ found through substitution. Therefore

$$a_n = A \cdot 3^n + 1$$

$$a_0=1 \implies A=0$$.