How to solve these recurrence relations

Question

How do I solve the following recurrence?

$$T(n) = 2T(n-2) + 4$$

I've looked online and there are only examples for how to do it without the constant at the end, and I've tried leaving it in to get a characteristic equation of $r^2 = 6$ but that didn't work either.

Also, how would I solve something like the following,

$$T(n) = T(n / 2) + c$$

where $c$ is some arbitrary constant? Note that the second one is easy to solve by inspection, but i wanted to know if there is a systematic way.

Answer 1

$$T(n)=2T(n-2)+4\\ =2(2T(n-4)+4)+4=2^2T(n-4)+(2+1)4\\ =2^2(2T(n-6)+4)+(2+1)4=2^3T(n-6)+(2^2+2+1)4\\ =2^3(2T(n-8)+4)+(2^2+2+1)4=2^4T(n-8)+(2^3+2^2+2+1)4\\ \vdots\\ =2^{n/2}T(n-n)+(2^{n/2}-1)4.$$

---

Let $n=2^k$.

Then $$T(2^k)=T(2^{k-1})+c=T(2^{k-2})+2c=\cdots T(2^{k-k})+kc.$$

Answer 2

Hint 1

Define $$ T(n) = a_n -4 $$ Then you have $$ a_n = 2a_{n-2} $$

Hint 2

You combine for $n=n/2$, $n=n/4, \dots$ $$ T(n) = T\Big(\frac{n}{2^k}\Big) + kc $$

Answer 3

for $$a_n=2a_{n-2}+4$$ solve the equation $$a_n=2a_{n-2}$$ with the ansatz $$a_n=q^n$$ and add a particular solution of the inhomogenous equation. Hint: $-4$