16

我有这个递归函数：

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

我想知道有没有办法证明这一点。我用谷歌搜索了一下，但没有发现任何简单易懂的东西。我已经知道生成函数可能会解决它，它们太复杂了，我不想进入它们。我正在寻找一种更简单的方法。

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 导致递归公式的显式形式，但我不太记得

4

3 回答 3

12 
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
于 2012-05-29T07:18:20.743 回答
5

Ok, I know you didn't want generating functions (GF from now on) and all the complicated stuff, but my problem turned out to be nonlinear and simple linear methods didn't seem to work. So after a full day of searching, I found the answer and hopefully these findings will be of help to others.

My problem: a[n+1]= a[n]/(1+a[n]) (i.e. not linear (nor polynomial), but also not completely nonlinear - it is a rational difference equation)

  1. if your recurrence is linear (or polynomial), wikihow has step-by-step instructions (with and without GF)
  2. if you want to read something about GF, go to this wiki, but I didn't get it till I started doing examples (see next)
  3. GF usage example on Fibonacci
  4. if the previous example didn't make sense, download GF book and read the simplest GF example (section 1.1, ie a[n+1]= 2 a[n]+1, then 1.2, a[n+1]= 2 a[n]+1, then 1.3 - Fibonacci)
  5. (while I'm on the book topic) templatetypedef mentioned Concrete Mathematics, download here, but I don't know much about it except it has a recurrence, sums, and GF chapter (among others) and a table of simple GFs on page 335
  6. as I dove deeper for nonlinear stuff, I saw this page, using which I failed at z-transforms approach and didn't try linear algebra, but the link to rational difference eqn was the best (see next step)
  7. so as per this page, rational functions are nice because you can transform them into polynomials and use linear methods of step 1. 3. and 4. above, which I wrote out by hand and probably made some mistake, because (see 8)
  8. Mathematica (or even the free WolframAlpha) has a recurrence solver, which with RSolve[{a[n + 1] == a[n]/(1 + a[n]), a[1] == A}, a[n], n] got me a simple {{a[n] -> A/(1 - A + A n)}}. So I guess I'll go back and look for mistake in hand-calculations (they are good for understanding how the whole conversion process works).

Anyways, hope this helps.

于 2012-07-19T20:11:10.817 回答
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。

于 2011-04-23T21:02:07.477 回答