Direction in closed form of recurrence relation

Question

I have the recurrence relation as follows:
$T(n) = 3T(n-1) - 15$
$T(1) = 8$

In looking for the closed form, I decided to expand try it out a few times.
$T(1) = 8$
$T(2) = 3T(1) - 15 == 3(8) - 15 = 9$
$T(3) = 3T(2) - 15 == 3(9) - 15 = 12$
$T(4) = 3T(3) - 15 == 3(12) - 15 = 21$
$T(5) = 3T(4) - 15 == 3(21) - 15 = 48$

At this point in time, I start to see if I notice any patterns that I might be able to pick apart. The only pattern I notice is in the $3(8),3(9),3(12),3(21)$ part of the equation.
T=2 The difference between 8 and 9 is $1 = 3^0$
T=3 The difference between 9 and 12 is $3 = 3^1$
T=4 The difference between 12 and 31 is $9 = 3^2$
T=5 The difference between 21 and 48 is $27 = 3^3$

Now that I've found a pattern, I struggle to relate it to a closed form expression. Using this knowledge, what would be my next step?

Answer 1

$T(n) = 3T(n-1) - 15$, so also $T(n-1) = 3T(n-2) - 15$, thus $$T(n) = 3(3T(n-2) - 15) - 15=3^2T(n-2)-(1+3)\cdot 15$$

Again: $T(n-2) = 3T(n-3) - 15$, so $$T(n) = 3^2(3T(n-3) - 15)-(1+3)\cdot 15=3^3T(n-3)-(1+3+3^2)\cdot 15$$

Go on like this (possibly use induction) to obtain $$T(n) = 3^kT(n-k)-15\sum_{i=0}^{k-1}3^i$$

This stops as soon as $k=n-1$, so $$T(n) = 3^{n-1}T(1)-15\sum_{i=0}^{n-2}3^i=8\cdot 3^{n-1}-15\frac{1-3^{n-1}}{1-3}=\frac{1}{6}(3^n+45)$$

Answer 2

hint

Look for the real $a $ such that

$$T_n-a=3 (T_{n-1}-a) $$

Answer 3

You have that $T(n) = 3T(n-1) - 15$ and $T(n-1) = 3T(n-2) - 15$, so we have that:

$$T(n) - 3T(n-1) = -15 = T(n-1) - 3T(n-2) \iff T(n) - 4T(n-1) + 3T(n-2) = 0$$

This reccurence relation has a characteristic equation $x^2 - 4x + 3 = 0$, which has solutions $x=1$ and $x=3$. So the solutions of the equations are of the form:

$$T(n) = a\cdot 1^n + b\cdot 3^n$$

Plugging the values for $n = 1,2$ we have:

$$\begin{cases} 8 = a + 3b \\ 9 = a + 9b \end{cases} \iff \begin{cases} b = \frac 16 \\ a = \frac{15}{2} \end{cases} \iff T(n) = \frac{15}{2} + \frac{3^n}{6}$$

Answer 4

We try to find a number $a$ such that $T(n) - a = 3(T(n-1) - a)$, or $T(n) = 3T(n-1) - 2a$. It is easily seen that $a = \frac{15}{2}$ satisfies this. Therefore $T(n) - \frac{15}{2} = 3\left(T(n-1) - \frac{15}{2}\right)$ and $T(n) - \frac{15}{2}$ is a geometric sequence. You get that $T(n) - \frac{15}{2} = 3^{n-1}\left(T(1) - \frac{15}{2}\right) = \frac{3^{n-1}}{2}$, so $T(n) = \frac{3^{n-1}+15}{2}$.