查找递归函数的闭合形式

Question

请考虑以下递归关系。

T(n) = 5 if n <= 2
T(n-1) + n otherwise

T(n)封闭式解决方案

我得到了所有值n(n+1)/2 + 7的解决方案。但是在我的大学考试中，他们给出了解决方案n(n+1)/2 + 2.但是，对于值n<2，此解决方案不会在5处终止。有人可以解释一下吗？

Answer 1

让我们解决它;首先让我们扩展伸缩式总和：

T(k)     = T(k)
T(k + 1) = T(k) + k + 1
T(k + 2) = T(k + 1) + k + 2 = T(k) + k + 1 + k + 2
...
T(k + m) = T(k) + k + 1 + k + 2 + ... + k + m =
= T(k) + mk + 1 + 2 + ... + m =
= T(k) + mk + (1 + m) * m / 2
...

现在我们有

T(k + m) = T(k) + mk + (1 + m) * m / 2

让我们k = 2：

T(m + 2) = T(2) + 2m + (1 + m) * m / 2 = 5 + 2m + (1 + m) * m / 2

最后，让我们m + 2 = n或m = n - 2：

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

我们有

T(n) = n * (n + 1) / 2 + 2 when n  > 2
T(n) = 5                   when n <= 2

Answer 2

作为一个简单的非严格推理练习，我们知道T(n) = T(n-1) + n产生前n个数字的总和：S(n) = n * (n + 1) / 2

现在，当n=2时，S(2) = 3，所以5的值实际上是递增5 - S(2) = 2。所以我们可以说：

T(n) = S(n) + (5 - S(2)) for n >=2

或

T(n) = S(n) + 2 for n >= 2
T(n) = 5 for n <= 2

注意，在n=2，这两个关系是相同的。