Solve recursion with constant added I have the following problem:
Define a sequence $(a_n)$ where $a_1 = 4$ and $a_n = 4a_{n-1} - 4$.  Find a closed form for $a_n$.
So basically I usually know how to deal with recursions like $a_n = a_{n-1}+ a_{n-2}$ or things like that, but since this one has a constant I can't seem to get the correct characteristic equation.
Could anybody help me?
 A: Let $a_n=b_n+c$. We want to choose a constant $c$ so that the recurrence for $b_n$ is "nice."
Substituting, we get
$$b_n+c=4b_{n-1}+4c-4.$$
The choice $c=\frac{4}{3}$ gives
$$b_n=4b_{n-1}.$$
Find $b_1$, and you will be able to write down a formula for $b_n$ immediately, and therefore a formula for $a_n$. 
A: $$\begin{align} a_n &= 4a_{n-1}-4 \\&=4\left(4a_{n-2}-4\right)-4=4^2a_{n-2} - (4^2+4) \\&=4^2\left(4a_{n-3}-4\right)-(4^2+4) = 4^3a_{n-3} - (4^3+4^2+4)\\ &\cdots\\&= 4^{n-1}a_1 -  (4^{n-1}+ \cdots + 4^2+4) \end{align}$$
A: For that particular sequence:
  a(n) = 4^n - sum (i = 1 to n-1) of 4^i   ....   valid for n > 1

A: One approach:
$$a_n = 4a_{n-1}-4 \implies a_n - 4a_{n-1} = -4 \\ \implies a_{n+1} = 4a_n - 4 \\[12pt] a_{n+1}= 5a_n -4a_{n-1}$$
This leads to $$a_n = \tfrac43 \left(1 + 2^{2n-1} \right)$$
A: First, let's get some intuition for what's going on by writing out the first few terms:
$$a_n:4,12,44,172,684,\ldots$$
If we take the first differences $a_n-a_{n-1}$ of this sequence, we obtain
$$a_n-a_{n-1}:
8,32,128,512,\ldots $$
Note that each term its four times is predecessor, which is confirmed by observing that
$$a_n -a_{n-1}= (4a_{n-1} - 4)-(4a_{n-2} - 4)=4(a_{n-1} -a_{n-2}).$$
Then the first differences satisfy the formula $a_n-a_{n-1}=2^{2n-1}$ for $n\geq 2$. But then
\begin{align}
a_n&=a_{n-1}+2^{2n-1}\\&=a_{n-2}+2^{2n-3}+2^{2n-1}\\&\cdots\\&=a_1+2^3+2^5+\cdots+2^{2n-1}\\&=4+8(1+4+\cdots +4^{n-2})\\&=4+8\left(\frac{4^{n-1}-1}{3}\right)=\frac{4}{3}\left(2^{2n-1}+1\right)
\end{align}
Both formulas may be confirmed by induction.
