- #1

Kine

- 1

- 0

T(n) = 1, n=0

T(n) = T(n-1) + n^2, when n>1

I start by plugging in (n-1) into the function again to get...

T(n)=(T(n-2)+(n-1)^2)+n^2

Which simplifies down to (T(n-2)+2n^2-2n+1.

I then do it again and get this...

T(n)=(T(n-3)+(n-2)^2))+2n^2-2n+1

Which comes out to...

T(n) = T(n-3) + 3n^2 - 6n + 5

By this point I noticed a bit of the pattern and tried to solve the recurrence

T(n) = T(n-k) + kn^2 - (k-1)kn

However, I don't know what to do about the value at the end of the function which more or less halts my progress...

Am I going about this the correct way or am I off base?