如何找到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) 

現在可以以不同的方式進行組合。