# Finding a closed formula for recurrence relation

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$. – John L. May 15 at 2:51

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)

• 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 :) – Combinatoric May 15 at 7:01
• If you can recognize or guess Python, the formulas are right there. – John L. May 15 at 7:04