Solve recurrences by obtaining a θ bound for T(N) given that T(1) = θ(1) $T(N) = N + T(N-3)$
This is what I got so far
$$\begin{align}&= T(N-6) + (N-3)+N\\
&= T(N-9) + (N-6) + (N-3)+N \\
&= T(N-12) + (N-9) + (N-6) + (N-3)+ N\end{align}$$
I think I should use  $(n^2 + n) / 2$.
im not sure if im doing it right or not! 
Thanks :)
 A: Note: we generally express functions of integer arguments with subscripts, i.e. $T_n$ rather than $T(n)$.
This is a constant-coefficient difference equation.  To specify the solution, you need three initial conditions, say, $T_1$, $T_2$, and $T_3$.  In general, the solution takes the form
$$T_n = T_n^{(H)} + T_n^{(I)}$$
where $T_n^{(H)}$ is a homogeneous solution satisfying
$$T_n^{(H)} - T_{n-3}^{(H)} = 0$$
and the initial conditions, and $$T_n^{(I)}$ is an inhomogeneous solution satisfying
$$T_n^{(I)} - T_{n-3}^{(I)} = n$$
The homogeneous piece takes the form $a r^n$ for some (potentially complex) value of $r$.  When we plug this into the homogeneous equation, we get
$$r^3-1=0$$
which has solutions $r=1$, $r=\omega = e^{i 2 \pi/3}$, and $r=\omega^2 = e^{i 4 \pi/3}$.  The homgeneous solution is then a linear combination of the solutions corresponding to these roots, i.e.,
$$T_n^{(H)} = A + B \omega^n + C \omega^{2 n}$$
where the constants $A$, $B$, and $C$ are determined by the initial conditions.
The inhomogeneous solution is determined by the factor of $n$, and because of the nature of the equation (a difference), we guess it takes the form $T_n^{(I)} = P n + Q n^2$.  Plugging this into the equation, we see that
$$3 P + (6 n-9) Q = n$$
which implies that $Q = 1/6$ and $P = 1/2$. The general solution to the equation is then
$$T_n = A + B \omega^n + C \omega^{2 n} + \frac{1}{6} n (n+3)$$
