# Recurrence relation chip and conquer

Can anyone explain how to find the $\Theta()$ of this equation... $$T(n) = 3T(n-4) + cn$$ When I solve this problem I get this using the $k$ -th iteration... $$T(n) = 3^{k}T(n-4k) + 3^{k-1}c(n-2(k-1)) + 3^{k-2}c(n-2(k-2)) + ... + cn$$ I factor out c and get this... $$T(n) = 3^{k}T(n-2k) + c(3^{k-1}(n-2(k-1)) + 3^{k-2}(n-2(k-2)) + ... n)$$ I'm not sure if we need to find an upper and lower bounds or solve the geometric series. Any suggestions? I need to find $\Theta()$ and we didn't cover master theorem so this is how my class was taught to approach these.

The answer should be $\Theta(3^{n/4})$. You can go both ways you suggest – find an exact formula, or estimate the sum, using an integral or in more devious ways. There is no loss in generality if you take $c = 1$. If you replace $n$ with $1$ (so we get a lower bound), then we have $$1 + 3 + 3^2 + \cdots + 3^{n/4} = \Theta(3^{n/4}),$$ using the formula for summing a geometric series. If you bring back the $n$, the calculation becomes a bit more difficult, but you should still be able to get a matching upper bound: $$n + 3(n-4) + 3^2(n-8) + \cdots + 3^{n/4}(0) = O(3^{n/4}).$$ There are in fact closed formulas for this kind of sum (try Wolfram alpha), but you can also try to bound without them, say by looking at ratios of consecutive terms and comparison to a geometric series: $$3^{n/4} \left(0 + 4\frac{1}{3} + 8\frac{1}{9} + 12\frac{1}{27} + \cdots \right) = O(3^{n/4}),$$ since the infinite series $4\sum_{m=0}^\infty \frac{m}{3^m}$ converges.
• The constant could depend on the residue of $n$ module 4. – Yuval Filmus Apr 27 '15 at 5:59
If that isn't a typo, you can separate that into 4 recurrences (for starting points 0, 1, 2, 3) by the change of variables $$r = \lfloor n / 4 \rfloor$$, $$k = n \bmod 4$$:
$$\begin{equation*} t_k(r + 1) = 3 t_k(r) + 4 r + k \qquad t_k(0) = T(k) \text{ for } 0 \le k < 4 \end{equation*}$$
\begin{align*} t_k(r) &= t_k(0) \cdot 3^r + \frac{r + 2}{2} \cdot 3^r - \frac{4 r + k + 2}{2} \\ &= \Theta(r \cdot 3^r) \\ T(n) &= \Theta(n \cdot 3^{n/4}) \end{align*}