I'll have n-3 terms and max of n^3 at each one, so is this Theta(n^4) ?
Yes (assuming you have suitable initial conditions), though I'm note sure the explanation of why its is acceptable. I would use upper and lower bounds derived from an integral approximation to the sum.