Assume $T(1) = 3.$ Recurrence is $T(n)=T(n-3)+3n+1$ and I'm showing $\Theta$ bound by computing the exact running time.
Starting off:
$(Tn-3) + 3n + 1$
$(Tn-9) + 9(n-3) + 3n + 1$
$(Tn-18) + 18(n-9) + 9(n-3) + 3n + 1$
All the recursion trees I've done done so far have used fractions such as $n/3$, so this problem is throwing me off a little bit. Am I headed in the right direction? Once I finish the recurrence tree, where do I go from there?
Do it by induction. Assume that $T(n)\leq cn^2$ for all n, and try to find such an $c>0$.
$T(1)=3\leq c$ gives us a good baseline, so we will choose $c=3$.
For all $n\geq 2$,
Assume $T(n)\leq 3n^2$, then $T(n+3)=T(n)+3(n+3)+1=3n^2+3n+10\leq 3n^2+18n+27= 3(n+3)^2$
So it holds true by induction. This implies that $T(n)=O(n^2)$, which gets you half the way. Try induction for a lower bound.