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

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 

我想知道是否有任何的方式来证明这一点。我搜索了一下，但没有发现任何简单的理解。我已经知道生成函数可能会解决它，它们太复杂了，我宁愿不进入它们。我正在寻找更简单的方法。

P.S. 如果它帮助我记得是这样解决的：

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

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 

factorise找到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 

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

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

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

1. 如果你的复发是线性的（或多项式），wikihow有一步一步的指示（有和没有GF）
2. 如果你想阅读一些关于GF，去this wiki，但我没有直到我开始做实例（见下一个）
3. GF usage example on斐波那契
4. 如果前面的例子没有意义，请下载GF book并阅读最简单的GF例子（1.1节，即a [n + 1] = 2 a [n] +1，则1.2，a [n + 1] = 2一个[n] +1，然后1.3 - 斐波那契）
5. （虽然我在书的主题）templatetypedef提到具体数学，下载here，但我不太了解它，除了它有一个循环，总和，和GF章节（除此之外）和一个简单的GF表格在第335页
6. 当我为非线性材料做更深入的研究时，我看到this page，使用它我在z变换方法失败并且没有尝试线性代数，但是链接到合理的区别eqn是最好的（见下一步）
7. 所以根据this page，合理的功能是不错，因为你可以将它们转换成多项式，并使用步骤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)}}。所以我想我会回去查找手工计算中的错误（它们对理解整个转换过程如何工作很有帮助）。

无论如何，希望这有助于。