如何解决以下递归关系

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。但是我该如何解决特定的积分部分呢？我在正确的轨道上吗？上述解决方案还有其他方法吗？

Answer 1

odd n 的重复很容易用你试过的替换来解决：

将其代入 even n:

的递归

尝试 #1

对以下形式进行一般替换：

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

匹配相同类型的词条：

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

尝试#2

原来需要第二个指数项:

和以前一样，其中一个指数项需要匹配 3^(n/2):

最后一个方程有解d = 0, -1；显然只有 non-trivial 一个有用：

全部的最终解n ≥ 2:

替代方法

更长但（可能，至少我发现它）更直观 - 将循环扩展 m 次：

观察模式：

每个扩展添加奇数 m的2 * 3^(n/2-m)因子，并且减它为偶数 m.

每个扩展还添加 f(n-2m) 的一个因子 even m,并且减去得到奇数 m.

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

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

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

与之前相同的结果。

How to solve the following recurence relation