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

-
I really encourage you to take a look at the MathJax tutorial –  sonystarmap Feb 26 '13 at 20:37
I tried to edit your question, but there are just too many situations where I am not sure what you mean. Please consider rewriting your question. Instead of an write $a_{n}$ which looks like $a_n$ and $3^{k}$ which looks like $3^k$. –  sonystarmap Feb 26 '13 at 20:43
@gt6989b is it supposed to be $n_K+1$ or $n_{K+1}$ or $n_{k+1}$ that was the point when I stopped editing as I wasn't sure about that. –  sonystarmap Feb 26 '13 at 20:44
@macydanim I just kept his original question to the bes tof my understanding ability :), not sure what he meant... –  gt6989b Feb 26 '13 at 20:47
Thanks, the MathJax tutorial was really helpful. Will definitely use that going forward. –  user56763 Feb 26 '13 at 22:11

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

-
awesome explanation. this is great, cleared up my confusion. thanks. –  user56763 Feb 26 '13 at 22:04
@user56763: You’re welcome; glad to help. –  Brian M. Scott Feb 26 '13 at 22:05

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

-
Note that It’s unlikely that the OP has seen generating functions at this point. –  Brian M. Scott Feb 26 '13 at 20:45
@BrianMScott, OP surely has seen power series? –  vonbrand Feb 26 '13 at 20:46
If the OP is taking a discrete math course in the U.S., it’s even possible that the OP hasn’t had calculus, though it’s fairly unlikely. It’s unlikely, however, that a student in such a course has encountered generating functions at all, and the bit of power series in the typical first-year calculus course isn’t going to help: generating functions are a wholly new idea. –  Brian M. Scott Feb 26 '13 at 20:56
@BrianM.Scott, the bit my answer shows is not that far out... and the technique is broadly applicable. –  vonbrand Feb 26 '13 at 21:04
Of course it is; that’s not the point. The kind of course that I strongly suspect the OP is taking is one that I taught many, many times over the years. It’s a shock to many of the students in it, because it’s the first course that they take that isn’t mostly just a bunch of computational recipes. A tiny handful of the hundreds of students that I taught in such courses could probably have followed your answer on their own; the vast majority would have found it totally incomprehensible. A majority of fourth-year math majors where I taught would have been puzzled by it. –  Brian M. Scott Feb 26 '13 at 21:14

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.

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