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

さて、あなたが関数（これからはGF）やすべての複雑なものを生成したくないことは知っていますが、私の問題は非線形であることが判明し、単純な線形メソッドは機能しないようでした。ですから、丸一日検索した後、私は答えを見つけました。うまくいけば、これらの発見が他の人の助けになるでしょう。

私の問題：a [n + 1] = a [n] /（1 + a [n]）（つまり、線形（または多項式）ではありませんが、完全に非線形ではありません-有理数の差分方程式です）

  1. 漸化式が線形（または多項式）の場合、ウィキハウにはステップバイステップの説明があります（GFありとなし）
  2. GFについて何か読みたい場合は、このwikiにアクセスしてください。ただし、例を実行し始めるまでわかりませんでした（次を参照）。
  3. フィボナッチでのGFの使用例
  4. 前の例が意味をなさなかった場合は、GFブックをダウンロードして、最も単純なGFの例を読んでください（セクション1.1、つまりa [n + 1] = 2 a [n] + 1、次に1.2、a [n + 1] = 2 a [n] +1、次に1.3-フィボナッチ）
  5. （私が本のトピックにいる間）templatetypedefはConcrete Mathematicsについて言及しました、ここからダウンロードしてください、しかしそれが繰り返し、合計、そして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)}}。だから私は戻って手計算の間違いを探すつもりだと思います（それらは変換プロセス全体がどのように機能するかを理解するのに役立ちます）。

とにかく、これが役立つことを願っています。

于 2012-07-19T20:11:10.817 に答える
2

一般に、再帰形式を反復形式に変換するためのアルゴリズムはありません。この問題は決定不可能です。例として、Collat​​zシーケンスを定義するこの再帰関数の定義を考えてみましょう。

f(1) = 0
f(2n) = 1 + f(n)
f(2n + 1) = 1 + f(6n + 4)

これが明確に定義された関数であるかどうかは不明です。これを閉じた形に変換できるアルゴリズムが存在する場合、それが明確に定義されているかどうかを判断できます。

ただし、多くの一般的なケースでは、再帰的定義を反復定義に変換することができます。優れた教科書ConcreteMathematicsは、そのページの多くをその方法を示しています。答えが何であるかを推測するときに非常にうまく機能する一般的な手法の1つは、誘導を使用することです。ケースの例として、再帰的定義が実際に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 に答える