This can be also solved using transtion matrix and approach similar to fibonacci series etc. problems. Transition matrix:

(0 1 0 2 1 0) - i^2

(0 0 0 1 0 0) - i-1

(0 0 0 1 1 0) - i

(0 0 0 0 1 0) - const 1

(0 1 0 2 1 1) - Sum(1 to i inclusive)

Initial vector for i=1: (1, 0, 1, 1, 1)

Then use efficient exponentitation to find relevant matrices and multiple. O(log n)