Iterative recurrence.. Iteration method

Question

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?

Answer 1

Hint: $T(n)-7.5 = 3 [ T(n-1) - 7.5) ]$

Hint: Set $S(n) = T(n) - 7.5$. What is $S(1)$? How does $S(n), S(n-1)$ relate?

Answer 2

It's maybe easier to see the pattern if you split up your expressions like this:

$$T(2) = 3\cdot T(1) - 15\\ T(3) = 3\cdot 3\cdot T(1) - 3\cdot 15 - 15 = 3^2 T(1) - 15 (3^0+3^1)\\ T(4) = 3\cdot 3\cdot 3\cdot T(1) - 3\cdot 3\cdot 15 - 3\cdot 15 - 15 = 3^3 T(1) - 15 (3^0+3^1+3^2)\\\vdots$$

Can you see it now?

Answer 3

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} $$

Answer 4

Assuming your work is correct, the final step is easy: you're just overthinking it. You know:

• $T(1) = 8$
• $T(n) = 3^i \cdot T(n - (i+1)) - 15$

There is an infinite amount of 'information' in that second equation! You can plug in (more or less) any value of $n$ and $i$ you want!

You want to know something about $T(n)$ so it may be best to leave $n$ as is. But that still leaves you free to choose a value for $i$ if you want, and there are some obvious choices for $i$ that are worth experimenting with.

It may help to think not in terms of choosing a value for $i$, but in terms of choosing a value for $n-(i+1)$. Once you've chosen what value you want $n-(i+1)$ to have, you can then solve for the correct value of $i$ to make it happen.

Unfortunately you made an error in your derivation, and so that needs to be redone (see the other answers if you need help on that). But once that's fixed, you will still be able to use the method I describe above.