Finding a closed formula for recurrence relation

Question

I'm trying to find a closed formula for the below recurrence relation:

For the first one, $n$ is some power of 2

$$T(n) = \begin{cases} 4 & \text{if $n=1$} \\ 2T(\frac{n}{2}) +4 & \text{else} \end{cases}$$

$$T(n) = \begin{cases} 1 & \text{if $n=0$} \\ T(n-1) +3^n & \text{else} \end{cases}$$

I tried to use the substitution and tree methods but I'm not sure what I'm doing and I think I get the wrong answer.

Answer 1

When you are not sure of whether you get the right answer, you can write a simple program in any of your favorite languages to double check.

For example, for the first function, I became pretty confident that I got the right answer once I had run the following script in Python.

def T(n):
    if n == 1: return 4
    return 2 * T(n // 2) + 4

for i in range(1, 20):
    print(T(2 ** i), 2 ** (i + 3) - 4)

Similarly, I ran the following script for the second function.

def S(n):
    if n == 0: return 1
    return S(n - 1) + 3 ** n


for i in range(20):
    print(S(i), (3 ** (i + 1) - 1) // 2)