$T(n) = T(n − 4) + 1$

Question

Solve the following recurrence relation and give a $\Theta$ bound for it: $T(n) = T(n − 4) + 1$

Answer 1

If you ignore the term $+1$ for a second,

$$T'(n)=2T'(n-2)=4T'(n-4)=\cdots2^{n/2}T'(0)$$ gives you a solution for all even $n$. Similarly for odd $n$,

$$T'(n)=2T'(n-2)=4T'(n-4)=\cdots2^{(n-1)/2}T'(1).$$

This is the solution of the homogeneous equation. For the non-homogeneous equation, we have to find a particular solution. Let us try a constant term $T''$.

$$T''=2T''+1$$ is solved by $T''=-1$.

Hence the full solution,

$$T(n)=2^{n/2}T'(0)-1=2^{n/2}(T(0)+1)-1,$$ $$T(n)=2^{(n-1)/2}T'(1)-1=2^{(n-1)/2}(T(1)+1)-1.$$