证明 k + 1 情况下的棘手递推关系

Question

我完全被这个难住了。

T(n) = { 3, if n = 2 || T(n - 1) + (n/4), if n > 2

Prove by induction that T(n) = (n^2 + n + 18) / 8  [V n >= 2]

我知道如何通过归纳法执行证明，但出于某种原因我无法解决 k + 1 情况下的这个表达式。

任何帮助都将是最好的。

Answer 1

首先我们选择n = 2:

T(n = 2) = (2^2 + 2 + 18) / 8 = 24 / 8 = 3

太好了，行得通。现在我们知道有一个数k >= 2满足T(n)的定义。然后，让我们为任意 k >= 2:

设置 n = k+1

T(n = k+1) = ((k+1)^2 + k + 1 + 18) / 8
           = (k^2 + 2k + 1 + k + 1 + 18) / 8
           = (k^2 + k + 18) / 8 + (2 + 2k) / 8
           = T(k) + k/4

这正是 T(n) 的定义所说的。

∎

证明 k + 1 情况下的棘手递推关系

Proving a tricky Recurrence Relation for the k + 1 case

math

recurrence