6

我有以下问题：

求解使用大“O”符号简化答案的递推关系：

f(0) = 2
f(n) = 6f(n-1)-5, n>0

我知道这是一阶非齐次递归关系并且已经解决了这个问题，但我似乎无法获得基本情况的正确输出（f（0）= 2）。

该问题必须在证明中使用几何级数之和。

这是我的答案 -注意 sum(x = y, z) 是大写 sigma 表示法的替代品，其中 x 是初始化为 y 的总和的下限，z 是总和的上限：

1.  *change forumla:*
2.     f(n) = 6^n.g(n)
3.  => 6^n.g(n) = 6.6^(n-1) .g(n-1) -5   
4.  => g(n) = g(n-1)-5/6^n
5.  => g(n) = sum(i=1, n)-5/6^i
6.  => f(n) = 6^n.sum(i=1, n)-5/6^i
7.  => *Evaluate the sum using geometric series forumla*
8.  => sum(i = 1, n)-5/6^i = [sum(i = 1, n)a^i] -------> (a = -5/6)
9.  => *sub a = -5/6 into geometric forumla [a(1-a^n)/(1-a)]*
10. => [(-5/6(1 - (-5/6)^n))/(1-(-5/6))]
11. => g(n) = [(-5/6(1 + (5/6)^n))/(1+5/6)]
12. => f(n) = 6^n . g(n) = 6^n[(-5/6(1 + (5/6)^n))/(1+5/6)]
13. => *sub in n = 0 to see if f(0) = 2*

首先，我确信第 11 行的等式可以进一步简化，其次，在 n = 0 中进行细分应该得到 2 作为结果。到达第 13 行时，我无法获得此答案...

编辑：我需要知道的是为什么在第 12 行将 n = 0 代入方程时我没有得到 f(0) = 2。另外我想知道的是如何简化 f(n) 的方程在第 12 行？

任何人...？

4

1 回答 1

2

不用想太多，我会说 f(n + 1) 是 f(n) 的 6 倍，减去一个常数。因此 f(n) 肯定是 O(6^n)。虽然你可能会发现一个更紧密的界限，但这大约是我在实践中所要走的！

为了好玩，我会试试这个：

f(1) = 6f(0) - 5
     = 6^1.f(0)
f(2) = 6f(1) - 5
     = 6(6f(0) - 5) - 5
     = 6^2.f(0) - 6^1.5 - 5
f(3) = 6f(2) - 5
     = 6^3.f(0) - 6^2.5 - 6^1.5 - 5

我会冒险猜测

f(n) = 6^n.f(0) - 5.(6^0 + 6^1 + ... + 6^(n-1))

我很确定我可以通过几行归纳来证明这一点（练习留给学生练习）。

现在，

sum (k in 0..n-1) 6^k  =  (1 - 6^n) / (1 - 6)

所以

f(n) = 6^n.f(0) - 5.(1 - 6^n) / (1 - 6)
     = 6^n.f(0) + (1 - 6^n)
     = 6^n.(2 - 1) + 1
     = 6^n + 1

证实了我之前的直觉。

让我们做一些快速检查计算：

f(0) = 2 = 6^0 + 1
f(1) = 6.2 - 5 = 7 = 6^1 + 1
f(2) = 6.7 - 5 = 37 = 6^2 + 1
f(3) = 6.37 - 5 = 237 = 6^3 + 1

这对我来说足够做作业了:-)

于 2011-04-12T12:19:27.213 回答