Как решить T (n) = T (n-1) + n^2?

Question

См. Название. Я пытаюсь применить метод из этого вопроса: Easy: Solve T(n)=T(n-1)+n by Iteration Method. То, что я до сих пор, но я не знаю, как поступить здесь на:

Т (п) = Т (п-1) + п

Т (п-1) = Т (п-2) + (N-1) = Т (п-2) + п - 2n + 1

Т (п-2) = Т (п-3) + (N-2) = Т (п-3) + п - 4n + 4

Т (п-3) = Т (п-4) + (N-3) = Т (п-4) + п - 6n + 9

Подставляя значения Т (п-1), Т (п-2) и Т (п-3) в Т (п) дает:

Т (п) = Т (п-2) + 2n - 2n + 1

Т (п) = Т (п-3) + 3n - 6n + 5

Т (п) = Т (п-4) + 4n - 12n + 14

Теперь я должен найти шаблон, но я действительно не знаю, как это сделать. Я получил:

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

Answer 1

Я бы предположил, что, поскольку каждый T (n) равен предыдущему плюс квадрат, T (n) является чем-то кубическим.

Записать T (n) = an^3 + bn^2 + cn + d.

Замените это на T (n) = T (n - 1) + n^2 и решите для a, b, c.

И, очевидно, T (0) = d.

Answer 2

Если объединить уравнения вы сами пишете:

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)