Closed Form Solution for a Recurrence Relation We start out with: $a_n = 3a_{n-1} - 7, a_0 = 2$. Is the following valid?
$$a_{n-1} = 3(3a_{n-2}-7)-7 \\ a_{n-1} = 3^2a_{n-2}-(3\cdot-7) - 7 \\ \vdots \\ a_k = 3^ka_{n-k} -(3^{k-1}\cdot-7) \cdots -7\\ \text{Let $k = n$} \\ a_n = 3^ka_0 - (3^{n-1}\cdot-7)-\cdots-7$$
I don't know where to go from here. I would I make a closed form out of this?
 A: This isn't correct as written. Notice that (the left-hand side of the first line should be $a_n$, and) the right-hand side equals $3\cdot 3a_{n-2} - 3\cdot 7 - 7$. In particular, we subtract $3\cdot7+7$, not just $7+7$. So the $-7n$ in the last line won't be correct.
In general, you don't even have to know whether your algebraic steps were correct or not to test the final answer! Try plugging in the proposed formula $a_n = 2\cdot 3^n - 7n$ to the recurrence: the result is
$$
2\cdot 3^n - 7n = 3(2\cdot 3^{n-1} - 7(n-1)) - 7 = 2\cdot 3^n - 21(n-1) - 7 = 2\cdot 3^n - 21n + 14,
$$
which is incorrect, revealing that something went wrong.
A: As Greg Martin has already pointed out, your closed form cannot be right, because it doesn’t satisfy the recurrence. You could also see whether it generates the right values for $a_1,a_2$, and $a_3$, say, and find that it doesn’t.
There is a slightly better way to organize this sort of ‘unwinding’ of a simple recurrence, but make sure that you do the algebra correctly:
$$\begin{align*}
a_n&=3a_{n-1}-7\\
&=3(3a_{n-2}-7)-7\\
&=3^2a_{n-2}-3\cdot7-7\\
&=3^2(3a_{n-3}-7)-3\cdot7-7\\
&=3^3a_{n-3}-3^2\cdot7-3\cdot7-7\\
&\;\;\vdots\\
&=3^ka_{n-k}-7\sum_{i=0}^{k-1}3^i\\
&\;\;\vdots\\
&=3^na_0-7\sum_{i=0}^{n-1}3^i\\
&=2\cdot3^n-7\cdot\frac{3^n-1}{3-1}\\
&=2\cdot3^n-\frac{7\cdot3^n-7}2\\
&=\frac12(7-3\cdot3^n)\\
&=\frac12(7-3^{n+1})
\end{align*}$$
Note that it’s generally best not to do too much simplification at each stage: too much simplification tends to obscure the pattern. And when you’re done, you should always check to be sure that your closed form satisfies the recurrence:
$$3\left(\frac12(7-3^n)\right)-7=\frac32\cdot7-\frac12\cdot3^{n+1}-7=\frac12(3^{n+1}-7)\,.$$
