求解递归方程

Question

我的教授给了我一些练习题让我做。但它们不是家庭作业或评分，而是为即将到来的测验练习的。我会问我的教授，但她因不太乐于助人而臭名昭著。但我正在努力解决这个问题，并希望得到一些帮助。

问题如下：

T(n) = 1 如果 n = 1

T(n-1) + n(n-1) 如果 n>=2

她给出了使用求和的提示，并假设 n = 2^k

到目前为止，这是我所拥有的：

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

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

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

因此...

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

这是关于我被难住的时候，但我试图向前推进并猜测要使用哪个求和。

T(n) = T(n-k) + (n(n+1)(2n+1))/6

Answer 1

嗯，通过伸缩系列，T(n) = 1 + sum(i(i-1) for i = 2..n)。那是 n(n-1)(n+1)/3 + 1 根据 Wolfram Alpha.

或者，如果您想手动完成，

sum(i(i-1) for i = 2..n)
= sum(i(i-1) for i = 1..n) 
= sum(i^2 for i = 1..n) - sum(i for i = 1..n)

然后使用众所周知的等式计算连续平方和和连续整数之和。