How to solve T(n) = T(n-1) + n^2?

4.6k views Asked by At

See title. I'm trying to apply the method from this question: Easy: Solve T(n)=T(n-1)+n by Iteration Method. What I have so far is this, but I don't know how to proceed from here on:

T(n) = T(n-1) + n2

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

T(n-2) = T(n-3) + (n-2)2 = T(n-3) + n2 - 4n + 4

T(n-3) = T(n-4) + (n-3)2 = T(n-4) + n2 - 6n + 9

Substituting the values of T(n-1), T(n-2) and T(n-3) into T(n) gives:

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

T(n) = T(n-3) + 3n2 - 6n + 5

T(n) = T(n-4) + 4n2 - 12n + 14

Now I have to find a pattern but I don't really know how to do that. What I got is:

T(n) = T(n-k) + kn2 - ...???

2

There are 2 answers

0
gen-y-s On

If you combine the equations you yourself write:

T(n)=
=n^2+T(n-1)=
=n^2+(n-1)^2+T(n-2)=
=n^2+(n-1)^2+(n-2)^2+T(n-3)=
=n^2+(n-1)^2+(n-2)^2+(n-3)^2+...+2^2+1^2+T(0)=
=n(n+1)(2n+1)/6+T(0)   //based on well known formula for S(x^2, x=1..n)
0
gnasher729 On

I'd start with a guess that since each T (n) is equal to the previous one plus a square, T (n) is something cubic.

Write T (n) = an^3 + bn^2 + cn + d.

Substitute this into T (n) = T (n - 1) + n^2 and solve for a, b, c.

And obviously T (0) = d.