利用特征方程求解递归

Question

我最近正在学习如何使用各种方法求解递归。到目前为止，我已经熟悉了主定理和代换法。有一个方法我似乎就是不明白，那就是下面这个问题，需要用特征方程来解决:

T (n) = 2 T (n/3) + 1, T (1) = 1

我看了一些教程和阅读材料，我想我需要从中推导出某种程度和联立方程?

在这种情况下我该怎么做?

很抱歉我在这方面很业余。

Answer 1

首先，我们必须把递归式写成更标准的形式。设U(k) = T(3^k)

U(k) = 2 U(k−1)+ 1

U由一个非齐次线性递推方程定义。下一步是得到齐次部分的非平凡解:

V(k) = 2v (k−1)

特征多项式为x−2，有一个单根x = 2，因此对于每个c的解为c2^k(如果有多个根，我们将考虑每个根的指数函数的每一个线性组合)

现在我们要得到满足U(k) = 2u (k−1)+ 1的解，别管基本情况。如果额外的项是一个多项式，我们可以找到一个多项式。在这种情况下，我们可以尝试一个常数函数，解出x = 2 x + 1，得到x = - 1，并验证U(k) = - 1确实成立。

最后，我们必须写出U(k) = - 1 + c V(k)并通过求解c来固定基本情况。由于U(0) = 1 = - 1 + c V(0) = - 1 + c，我们得到c = 2。

整体解为U(k) = 2^k+1−1，因此

T (n) = 2<一口>日志<子>3(n) + 1> 志<子>2子> 2(3)+ 1> 1/日志<子>2(3)−1。