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

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

我想知道是否有任何方法可以证明这一点.我google了一下,但没有找到任何简单的理解.我已经知道生成函数可能解决了它,它们太复杂了,我宁愿不进入它们.我正在寻找一种更简单的方法.

PS如果它有帮助我记得这样的东西解决了它:

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

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

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

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

1. 如果你的重复是线性的(或多项式),wikihow有逐步说明(有和没有GF)
2. 如果你想阅读有关GF的内容,请访问这个wiki,但在我开始做示例之前我没有得到它(见下)
3. Fibonacci上的GF用法示例
4. 如果上一个例子没有意义,请下载GF书并阅读最简单的GF示例(第1.1节,即a [n + 1] = 2 a [n] +1,然后1.2,a [n + 1] = 2 a [n] +1,然后是1.3 - Fibonacci)
5. (虽然我在书的主题上)templatetypedef提到了具体数学,在这里下载,但我不太了解它,除了它有一个重复,总和,和GF章节(以及其他)和一个简单的GF页面在页面上335
6. 当我深入研究非线性的东西时,我看到了这个页面,使用了我在z变换方法中失败并且没有尝试线性代数,但是理性差异eqn的链接是最好的(见下一步)
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)}}.所以我想我会回去查找手工计算中的错误(它们有助于理解整个转换过程的工作原理).

无论如何,希望这会有所帮助.