math - 如何解决以下递归关系

Question

如何解决以下递归关系？

f(n+2) = 2*f(n+1) - f(n) + 2  where n is even
f(n+2) = 3*f(n)               where n is odd
f(1) = f(2) = 1

对于奇数n，我可以解决递归问题，结果证明它是一个公比为 3 的几何级数。

什么时候n我可以通过替换找到并解决递归关系的齐次部分f(n) = r^n。所以解决方案来了r = 1。因此解决方案是c1 + c2*n。但是如何解决特定的组成部分？我在正确的轨道上吗？上述解决方案还有其他方法吗？

标签： mathdiscrete-mathematicsrecurrence

Answer 1

使用您尝试的替换很容易解决奇数 的递归：n

将其代入even n的循环中：

---

尝试#1

对形式进行一般替换：

^{请注意，指数n/2不是n基于奇数递归，但这纯粹是一个选择问题}

匹配相同类型的术语：

但是这个解决方案不适用于边界条件f(2) = 1：

---

尝试#2

事实证明，需要第二个指数项：

和以前一样，指数项之一需要匹配3^(n/2)：

最后一个方程有解d = 0, -1；显然只有非平凡的有用：

所有人 的最终解决方案n ≥ 2：

---

替代方法

更长但（可能，至少我发现它）更直观 - 扩大重复m时间：

观察模式：

1. 加法因子 2 存在于奇数个展开m，但抵消了偶数 m。

2. 每次展开都会为奇数添加一个因子，并为偶数减去它。2 * 3^(n/2-m) m m

3. 每个扩展还为even添加一个因子，并为奇数减去它。f(n-2m) m m

结合这些观察，为m第 -th 展开写一个通用的封闭形式表达式：

在最后一步中使用几何级数的标准公式。

递归停止于f(2) = 1：

结果和以前一样。