I'm usually good until the first couple of steps, then once you add more and more things I get lost pretty easily. Can somebody give me a step-by-step analysis of this? I'd really appreciate it.
$$T_{n} = 4T_{n-1} - 2, T_{0} = 1$$
$$T_{n} = 4[4T_{n-2} - 2] - 2$$
$$T_{n} = 4^2 T_{n-2} - 4 * 2 - 2$$
$$T_{n} = 4^2 T_{n-2} - 2(1+4)$$
$$T_{n} = 4^2[4T_{n-3} - 2] - 2(1+4)$$
$$T_{n} = 4^3 T_{n-3} - 2 * 4^2 - 2(1+4)$$
$$T_{n} = 4^3 T_{n-3} - 2(1 + 4 + 4^2$$
$$T_{n} = 4^3 [T_{n-4} - 2] - 2(1 + 4 + 4^2)$$
$$T_{n} = 4^4 T_{n-4} - 4^3 * 2 * 2(1+4+4^2)$$
$$T_{n} = 4^4 T_{n-4} - 2(1+4+4^2 + 4^3) \\ \vdots \\ T_{n} = 4^k T_{n-k} - 2(1+4+4^2 +...+ 4^{k+1})$$
The basic idea is that you do successive substitutions until you see a pattern. Then, you prove the pattern by induction.
Your case:
$T_{n} = 4T_{n-1} - 2, T_{0} = 1 $.
First step is to substitute for $T_{n-1}$ using the recurrence. Since $T_{n-1} = 4T_{n-2} - 2 $, we get $T_{n} = 4T_{n-1} - 2 = 4(4T_{n-2} - 2) - 2 = 16T_{n-2} - 8 - 2 $.
Do the same for $T_{n-2}$. we get $T_{n} = 16T_{n-2} - 8 - 2 = 16(4T_{n-3} - 2) - 8 - 2 = 64T_{n-3} - 32 - 8 - 2 $.
Now we begin to see a pattern. Writing the constants as power of $2$, we have $T_{n} = 2^6T_{n-3} - 2^5 - 2^3 - 2^1 $. With a little bit of manipulation, this becomes $T_{n} = 2^6T_{n-3} - 2(2^4 + 2^2 + 2^0) $. Since all the exponents are even, we can write this using powers of $4$ (instead of powers of $2$) as $T_{n} = 4^3T_{n-3} - 2(4^2 + 4^1 +4^0) $.
Looking at this, the pattern seems to be, for integer $k$, $T_{n} = 4^kT_{n-k} - 2(4^{k-1} + 4^{k-2}+...+4^1 +4^0) $.
Using the recurrence, and writing $T_{n-k}$ in terms of $T_{n-k-1}$, this is easy to prove.
If we set $n=k$, this becomes
$\begin{array}\\ T_{n} &= 4^nT_{0} - 2(4^{n-1} + 4^{n-2}+...+4^1 +4^0)\\ &= 4^n - 2\frac{4^n-1}{4-1}\\ &= \frac{3\cdot4^n-2(4^n-1)}{3}\\ &= \frac{4^n+2}{3}\\ \end{array} $.
You can easily verify this. $T(0) =\frac{1+2}{3} =1 $.
$\begin{array}\\ 4T_{n-1}-2 &=4\frac{4^{n-1}+2}{3}-2\\ &=\frac{4(4^{n-1}+2)-3\cdot2}{3}\\ &=\frac{4^{n}+8-6}{3}\\ &=\frac{4^{n}+2}{3}\\ &=T_{n}\\ \end{array} $.
And we are done.