Here's the question: Solve the recurrence by obtaining a $\theta$ bound for $T(n)$ given that $T(1) = \theta(1)$.
$T(n) = n + T(n-3).$
Attempted Solution:
\begin{align*} T(n) &= T(n-6) + (n-3) + n \\ &= T(n-9) + (n-6) + (n-3) + n \\ &= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + \cdots + n]\\ &= T(1) + [0 + 3 + 6 + \cdots + n]\\ &= \theta(1) = 3[1 + 2 + 3 + \cdots + n/3]\\ &= \theta(1) + \frac{(n/3)(n/3 + 1)}{2}\\ &= \theta(1) + \frac{n^2+3n}{6}. \end{align*} When I double check to see if the solution fits the recurrence, it doesn't work. I can solve these fairly easily when it involves the previous term, but this $T(n-3)$ is throwing me off. Been at this one for a while now; please help T__T