<s>[INST] Iterative recurrence.. Iteration method Here is the Equation and how far I got into solving this problem using the iteration method:
$$T(1) = 8  \\
T(n) = 3T(n-1) - 15$$
Iterations:
$i=1, $ 
$$T(n) = 3(3T(n-2) - 15) -15$$
$i=2, $ 
$$ 3(3(3T(n-3) - 15) -15) - 15$$
$i=3,$
 $$3(3(3(3T(n-4) - 15) -15) - 15) - 15$$
$i=4,$
$$ 3(3(3(3(3T(n-5) - 15) -15) - 15) - 15) - 15$$
From the iteration pattern I found that
$$T(n) = 3^{i+1} \times T(n-(i+1)) - 15$$
At this point I need to find a summation for this recurrence and make it into closed form... I'm just not sure how.
Can someone explain or help guide me to solving this problem? 
 [/INST] It is easier to use generating functions. Define $g(z) = \sum_{n \ge 0} T(n + 1) z^n$. Write:
$$
T(n + 2) = 3 T(n + 1) - 15 \quad T(1) = 8
$$
Multiply by $z^n$ and add over $n \ge 0$:
$$
\frac{g(z) - T(1)}{z} = 3 g(z) - 15 \frac{1}{1 - z}
$$
From here:
$$
g(z) = \frac{8 - 23 z}{1 - 4 z + 3 z^2}
     = \frac{1}{2} \cdot \frac{1}{1 - 3 z} + \frac{15}{2} \cdot \frac{1}{1 - z}
$$
This gives:
$$
T(n) = \frac{1}{2} \cdot 3^{n + 1} + \frac{15}{2}
     = \frac{3^{n + 1} + 15}{2}
$$
</s>