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.

• 喜欢算法和数学: For the first $T,ドル $T(n)+4=2(T(n/2)+4)$. So $T(n)+4$ is a geometric series with ratio 2. For the second $T,ドル $T(n)=3^n + 3^{n-1} + \cdots + 1$.

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)

• Combinatoric: Yes! I thought about doing so but wasn't sure. Will try now. If you can write in hidden text the formulas you got so I can compare it later it would be great :)
• 喜欢算法和数学: If you can recognize or guess Python, the formulas are right there.