6

次の質問があります。

Big'O'表記を使用して、答えを単純化する漸化式を解きます。

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

これが一次の不均一な漸化式であることを知っており、質問に答えましたが、基本ケース（f（0）= 2）の正しい出力を取得できないようです。

質問は、証明内で等比数列フォーラムラの合計を使用する必要があります。

これが私の答えです-sum（x = y、z）は大文字のシグマ表記の代わりです。ここで、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 に答える