使用特征方程求解递归
Solving recurrence using characteristic equation
我最近正在学习如何使用各种方法来解决递归问题。到目前为止，我已经熟悉了 Master 定理和替换方法。我似乎无法理解的一种方法是以下需要通过特征方程求解的问题：
T(n)=2T(n/3)+1,T(1)=1
我看过某些教程和读物，我想我需要从中推导出某种度数和联立方程？
这种情况下我该怎么做？
抱歉，我是业余爱好者。
首先我们必须以更标准的形式放置循环。令 U(k) = T(3k)。那么
U(0) = 1
U(k) = 2 U(k−1) + 1
U 由非齐次线性递推方程定义。下一步是获取齐次部分的非平凡解：
V(k) = 2 V(k−1)
特征多项式为 x − 2，单根 x = 2，因此对每个 c 的解为 c 2k。 （如果有多个根，我们会考虑每个根的指数函数的每个线性组合。）
现在我们必须得到任何满足 U(k) = 2 U(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) = 2k+1 − 1，因此
T(n) = 2log3(n)+1 − 1 = 2log2(n)/log2(3)+1 − 1 = 2 n1/log2(3) − 1.
我最近正在学习如何使用各种方法来解决递归问题。到目前为止，我已经熟悉了 Master 定理和替换方法。我似乎无法理解的一种方法是以下需要通过特征方程求解的问题：
T(n)=2T(n/3)+1,T(1)=1
我看过某些教程和读物，我想我需要从中推导出某种度数和联立方程？
这种情况下我该怎么做？
抱歉，我是业余爱好者。
首先我们必须以更标准的形式放置循环。令 U(k) = T(3k)。那么
U(0) = 1
U(k) = 2 U(k−1) + 1
U 由非齐次线性递推方程定义。下一步是获取齐次部分的非平凡解：
V(k) = 2 V(k−1)
特征多项式为 x − 2，单根 x = 2，因此对每个 c 的解为 c 2k。 （如果有多个根，我们会考虑每个根的指数函数的每个线性组合。）
现在我们必须得到任何满足 U(k) = 2 U(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) = 2k+1 − 1，因此
T(n) = 2log3(n)+1 − 1 = 2log2(n)/log2(3)+1 − 1 = 2 n1/log2(3) − 1.