如何计算递归函数的显式形式？

Question

我有这个递归函数：

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4
f(1) = 2
f(2) = 8

我从经验中知道它的明确形式是：

f(n) = 3 ^ n - 1  // pow(3, n) - 1

我想知道是否有任何方法可以证明这一点。我用谷歌搜索了一下，但没有找到任何简单易懂的东西。我已经知道生成函数可能可以解决这个问题，它们太复杂了，我不想深入研究它们。我正在寻找一种更简单的方法。

聚苯乙烯 如果它有帮助，我记得这样的事情解决了它：

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4
// consider f(n) = x ^ n
x ^ n = 2 * x ^ (n-1) + 3 * x ^ (n-2) + 4

然后你以某种方式计算了 x ，导致递归公式的显式形式，但我不太记得

Answer 1

好吧，我知道你不想要生成函数（从现在开始）和所有复杂的东西，但我的问题结果是非线性的，简单的线性方法似乎不起作用。经过一整天的搜索，我找到了答案，希望这些发现对其他人有帮助。

我的问题： a[n+1]= a[n]/(1+a[n]) （即不是线性的（也不是多项式），但也不是完全非线性的 - 它是一个有理差分方程）

1. 如果你的递归是线性的（或多项式），wikihow 有分步说明（有或没有 GF）
2. 如果你想读点什么关于 GF，请访问 这个 wiki，但直到我开始做示例时我才明白（见下）
3. 斐波那契GF使用示例
4. 如果前面的示例没有意义，请下载GF 书 并阅读最简单的 GF 示例（第 1.1 节，即 a[n+1 ]= 2 a[n]+1，然后 1.2，a[n+1]= 2 a[n]+1，然后 1.3 - 斐波那契）
5. （当我在讨论书本主题时） templatetypedef提到了具体数学，下载这里，但我对此了解不多，除了它有递归、求和和 GF 章节（其中其他）和第 335 页上的简单 GF 表
6. ，当我更深入地研究非线性内容时，我看到 这个页面，使用它我在 z 变换方法上失败了，并且没有尝试线性代数，但是到有理差分方程的链接是最好的（参见下一步）
7. 因此，根据此页面，有理函数很好，因为您可以将它们转换为多项式并使用线性方法上面的步骤 1.3. 和 4. 是我手写的，可能犯了一些错误，因为（参见 8）
8. Mathematica （甚至是免费的 WolframAlpha) 有一个递归求解器，其中 RSolve[{a[n + 1] == a[n]/(1 + a[n])， a[1] == A}, a[n], n] 给了我一个简单的 {{a[n] -> A/(1 - A + A n)}}。所以我想我会回去寻找手工计算中的错误（它们有助于理解整个转换过程的工作原理）。

无论如何，希望这会有所帮助。

Answer 2

一般来说，没有一种算法可以将递归形式转换为迭代形式。这个问题是无法判定的。作为一个例子，考虑这个递归函数定义，它定义了 Collat​​z 序列：

f(1) = 0
f(2n) = 1 + f(n)
f(2n + 1) = 1 + f(6n + 4)

甚至不知道这是否是一个定义良好的函数。如果存在一种可以将其转换为封闭形式的算法，我们就可以决定它是否定义良好。

然而，对于许多常见情况，可以将递归定义转换为迭代定义。优秀的教科书《具体数学》用了很多篇幅来展示如何做到这一点。当您猜测答案是什么时，一种非常有效的常用技术是使用归纳法。作为您的案例的示例，假设您相信您的递归定义确实给出了 3^n - 1。为了证明这一点，请尝试证明它对于基本情况成立，然后证明这些知识可以让您向上推广解决方案。您没有在帖子中添加基本案例，但我假设

f(0) = 0
f(1) = 2

鉴于此，让我们看看您的预感是否正确。对于 0 和 1 的特定输入，您可以通过检查来验证该函数是否计算了 3^n - 1。对于归纳步​​骤，我们假设对于所有 n' < n f(n) = 3^n - 1。那么我们就得到了

f(n) = 2f(n - 1) + 3f(n - 2) + 4
     = 2 * (3^{n-1} - 1) + 3 * (3^{n-2} - 1) + 4
     = 2 * 3^{n-1} - 2 + 3^{n-1} - 3 + 4
     = 3 * 3^{n-1} - 5 + 4
     = 3^n - 1

所以我们刚刚证明了这个递归函数确实产生了 3^n - 1。

Answer 3

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4
f(n+1) = 2 * f(n) + 3 * f(n-1) + 4

f(n+1)-f(n) = 2 * f(n) - 2 * f(n-1) + 3 * f(n-1) - 3 * f(n-2)
f(n+1) = 3 * f(n) + f(n-1) - 3 * f(n-2)

现在4已经没了。
正如您所说，下一步是让 f(n) = x ^ n

x^(n+1) = 3 * x^n + x^(n-1) - 3 * x^(n-2)

除以 x^(n-2)

x^3 = 3 * x^2 + x - 3
x^3 - 3 * x^2 - x + 3 = 0

因式分解来找到 x

(x-3)(x-1)(x+1) = 0
x = -1 or 1 or 3

f(n) = A * (-1)^n + B * 1^n + C * 3^n
f(n) = A * (-1)^n + B + C * 3^n

现在使用您求解 A、B 和 C 的值找到

f(1) = 2; f(2) = 8; f(3) = 26

f(1) = 2 = -A + B + 3C
f(2) = 8 = A + B + 9C
f(3) = 26 = -A + B + 27C

A、B 和 C：

f(3)-f(1) = 24 = 24C      => C = 1
f(2)-f(1) = 6 = 2A + 6    => A = 0
2 = B + 3                 => B = -1

最后

f(n) = 3^n - 1