# Solving T(n) = 2*T(n-1)+4 witht the Master Theorem

I am wondering if there is a way to solve a recurrence time function with the master theorem if no $$b$$ exists. Like in this case. $$T(n) = 2\times T(n-1)+4$$

• No b exists and b=0 are different things. – zkutch Nov 29 '20 at 15:11
• The master theorem is useful for many recurrences, but it isn't the correct tool for all of them. – Yuval Filmus Nov 29 '20 at 15:44

By expansion you can see it is $$T(n) = \Theta(2^n)$$ (suppose $$T(1) = 1$$):
$$T(n) = 2T(n-1) +4 = 2(2T(n-2)+4) + 4 = 2^2T(n-2) + 2\times 4 + 4 = \ldots =$$
$$2^{n-1}T(1) + 2^{n-2}4 + \cdots + 4 = 4\left(\sum_{i=1}^{n-1}2^i\right) = 4(2^n - 1)$$
Let $$S(n) = T(n)/2^n$$. Then $$S(n) = S(n-1) + \frac{4}{2^n}.$$ Since the series $$\sum_{n=1}^\infty \frac{4}{2^n}$$ converges, we see that $$S(n) = \Theta(1)$$, and so $$T(n) = \Theta(2^n)$$.