我有一个递归函数：
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，这导致了递归公式的显式形式，但我不太记得
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
好吧，我知道你从现在起不想要生成函数(GF(和所有复杂的东西，但我的问题是非线性的，简单的线性方法似乎不起作用。因此，经过一整天的搜索，我找到了答案，希望这些发现能对其他人有所帮助。
我的问题：a[n+1]=a[n]/(1+a[n]((即不是线性的(也不是多项式(，但也不是完全非线性的——这是一个有理差分方程(
- 如果您的递归是线性(或多项式(的，wikihow有分步说明(有GF和没有GF(
- 如果你想读一些关于GF的东西，可以访问这个wiki，但我直到开始做例子才得到它(见下一页(
- 关于Fibonacci的GF使用示例
- 如果前面的例子没有意义，下载GF书并阅读最简单的GF例子(第1.1节，即a[n+1]=2 a[n]+1，然后是1.2，a[n+1]=2 a[n]+1，然后是1.3-斐波那契(
- (当我谈论这本书的主题时(templatepedef提到了具体数学，请在这里下载，但我对它了解不多，除了它有一个递归、求和和和GF章节(以及其他章节(，以及335页上的一个简单GF表
- 当我深入研究非线性问题时，我看到了这一页，我在z变换方法上失败了，也没有尝试线性代数，但与有理差分方程的链接是最好的(见下一步(
- 根据这一页，有理函数是很好的，因为你可以把它们转换成多项式，并使用步骤1的线性方法。3.和4。上面是我亲手写的，可能犯了一些错误，因为(见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)}}。所以我想我会回去寻找手工计算中的错误(它们有助于理解整个转换过程是如何工作的(
无论如何，希望这能有所帮助。
通常，没有将递归形式转换为迭代形式的算法。这个问题是无法决定的。例如，考虑这个递归函数定义，它定义了Collatz序列：
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'<其中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。