如何找到T（n）= T（n-1）+ n + 2的递推方程？

Question

好吧，我应该找到T（n）= T（n-1）+ n + 2的递推方程，其中T（1）= 1。我知道答案应该是1/2 n（n + 5）-4）但我不明白如何得到答案。我不需要它用任何计算机语言，这只是一个离散的数学问题。

Answer 1

如果你已经知道的表情，你能证明它的正确性与mathematical induction principle

声称：

T(n) = 1/2 * n^2 + 5/2 * n - 2 

检查对于某个n值

T(1) = 1/2 + 5/2 - 2 = 1 => TRUE 

然后检查公式的工作，当你去从T（n）到T（n + 1）

T(n+1) = 1/2 * (n+1)^2 + 5/2 * (n+1) - 2 = 
     1/2 * n^2 + n + 1/2 + 5/2 * n + 5/2 - 2 = 
     1/2 * n^2 + 5/2 * n - 2 + n + 1/2 + 5/2 = 
     (1/2 * n^2 + 5/2 * n - 2) + (n + 1) + 2 = 
     T(n) + (n+1) + 2 => TRUE 

Answer 2

使用标准计算一下，您得到

T(n) = T(1) + sum(k=2 to n) (k+2) 
    = 1 +sum(k=1 to n) k - 1 + 2*(n-1) 
    = n*(n+1)/2 + 2*(n-1) 

现在可以以不同的方式进行组合。