你能帮我解决递归关系T(1)=5，对于所有n>=2，T(n)=2T(n-1)+(3*n+1)

Question

T(1)=5,

所有 n>=2: T(n)=2T(n-1)+(3*n+1).

我试图解决这个问题，但我遇到了 3*n+1 的问题。当我放n-1,n-2,...的时候，我不知道这道题的公式怎么确定

Answer 1

因为只有 (3*n+1) 作为术语而不是 T(3*n+1) 这是可以解决的。第一印象：你有 2T(n-1) 作为子项，所以解决方案类似于 2^n.

通过简单的 Excel 数据分析，我找到了解决方案 T(n)=-7-3n+15 * 2^(n-1)，我会尝试每手解决它，如果找到正确的路径，我会更新我的答案。

编辑：这比预期的要难...

解释：

• 第一步是得到 n 的求和公式。你可以从前几个 T(n).
推导出这个模式
• 获得模式后，尝试去掉总和。
• 要求和，请尝试以与 sum_(i=1)^n (1) = n 或 sum_(i=0)^n (2^i) = 2^(n+1)-1
类似的格式求和
• 要做到这一点，您可以操纵索引，例如 sum_(i=2)^n (n-i) = sum_(i=0)^(n-2) (i) 或总和中的 include/exclude 个元素。
• 最棘手的部分是解决 sum_(i=0)^n ((n-i)*(2^i))。这里的想法是将乘法（取决于i）转换为和（也取决于i）。
• 请注意变化 indice-numbers。 sum_(i=0)^n (2^i) 与 sum_(i=1)^n (2^i)
不同
• 路径不是最高效的，想怎么简化就怎么简化。