Repeated Substitution to solve a recurence.

[Kine]

I have to solve the following recurrence but I keep getting stuck.


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?

 

[HallsofIvy]

So far you have changed from one recurance to another but you haven't "solved" the equation.

If $T(0)= 1$ then $T(1)= T(0)+ 1^2= 1+ 1= 2$, $T(2)= T(1)+ 2^2= 2+ 4= 6$, $T(3)= T(2)+ 3^2= 6+ 9= 15$, $T(4)= T(3)+ 4^2= 15+ 16= 31$, $T(5)= T(4)+ 5^2= 31+ 25= 56$. If you do not recognize that sequence, try fitting a third degree polynomial to it.

Let $p(x)= ax^3+ bx^2+ cx+ d$.
Taking x= 0, 1, 2, 3 will give 4 linear equations to solve for a, b, c, and d. Check to see if that also workds for x= 4 and x= 5.