So berechnen Sie die explizite form einer rekursiven Funktion?

Habe ich diese rekursive Funktion:

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4
f(1) = 2
f(2) = 8

Ich weiß aus Erfahrung, dass explizite form der es wäre:

f(n) = 3 ^ n - 1  //pow(3, n) - 1

Ich will wissen, ob es irgendeine Möglichkeit zu beweisen, dass. Ich habe ein wenig gegoogelt, doch habe nichts gefunden, einfach zu verstehen. Ich weiß schon, dass die generation Funktionen, wahrscheinlich zu lösen Sie, Sie sind zu Komplex, ich würde lieber nicht in Ihnen. Ich bin auf der Suche nach einem einfacheren Weg.

P. S.
Wenn es hilft, ich erinnere mich an etwas, wie diese es gelöst:

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

Und dann irgendwie berechnet x, führen zu expliziten form der rekursiven Formel, doch ich kann mich nicht genau erinnern,

InformationsquelleAutor der Frage atoMerz | 2011-04-23

  1. 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)

    Nun die 4 ist Weg.
    Als Sie sagte, der nächste Schritt ist, dass f(n) = x ^ n

    x^(n+1) = 3 * x^n + x^(n-1) - 3 * x^(n-2)

    Division durch x^(n-2)

    x^3 = 3 * x^2 + x - 3
x^3 - 3 * x^2 - x + 3 = 0

    factorise zu finden 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

    Finden Sie nun die A,B und C mit den Werten, die Sie haben

    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

    Lösung für A,B und C:

    f(3)-f(1) = 24 = 24C      => C = 1
f(2)-f(1) = 6 = 2A + 6    => A = 0
2 = B + 3                 => B = -1

    Schließlich

    f(n) = 3^n - 1

    InformationsquelleAutor der Antwort Alex

  2. 5

    Ok, ich weiß, Sie wollte nicht, dass erzeugende Funktionen (GF) und all die komplizierten Sachen, aber mein problem war nicht linearen und einfachen linearen Methoden nicht zu funktionieren scheint. So nach einem ganzen Tag des Suchens, fand ich die Antwort und hoffentlich diese Erkenntnisse helfen wird, die andere.

    Mein problem: a[n+1]= a[n]/(1+a[n]) (D. H. nicht-linear (oder Polynom), aber auch nicht völlig nichtlinear - es ist eine rationale Differenz-Gleichung)

    1. wenn Ihr Wiederauftreten ist linear (oder Polynom), wikihow hat Schritt-für-Schritt-Anleitung (mit und ohne GF)
    2. wenn Sie wollen, um etwas zu Lesen über GF gehen, um dieses wikiaber ich habe nicht bekommen, bis ich angefangen die Beispiele (siehe weiter)
    3. GF Anwendungsbeispiel auf Fibonacci -
    4. wenn der Vorherige Beispiel nicht sinnvoll, den download GF-Buch und Lesen Sie den einfachsten GF-Beispiel (Abschnitt 1.1), d.h. eine[n+1]= 2 a[n]+1, dann 1.2, a[n+1]= 2 a[n]+1, dann 1.3 - Fibonacci)
    5. (während ich auf das Buch-Thema) templatetypedef erwähnt Konkrete Mathematik, download hieraber ich weiß nicht viel darüber, außer dass es eine Wiederholung, Summen, und die GF-Kapitel (unter anderem) und eine Tabelle der einfachen GFs auf Seite 335
    6. als tauchte ich tiefer für nichtlineare Zeug, ich sah auf dieser Seitemit denen ich nicht bei z-Transformationen Vorgehen und nicht versuchen, lineare algebra, aber der link zu rational Unterschied eqn war der beste (siehe nächsten Schritt)
    7. so pro auf dieser Seiterationale Funktionen sind nett, weil Sie können verwandeln Sie sich in Polynome und lineare Methoden Schritt 1. 3. und 4. oben, was ich schrieb mit der hand und wahrscheinlich einen Fehler gemacht, weil (siehe 8)
    8. Mathematica (oder auch die freie WolframAlpha) hat eine Wiederholung solver, der mit RSolve[{a[n + 1] == a[n]/(1 + a[n]), a[1] == A}, a[n], n] hab mir eine einfache {{a[n] -> A/(1 - A + A n)}}. Also ich denke, ich werde gehen zurück und suchen Fehler in der hand-Berechnungen (Sie sind gut für das Verständnis, wie die ganze Umwandlungsprozess funktioniert).

    Sowieso, hoffe, das hilft.

    InformationsquelleAutor der Antwort alexey

  3. 2

    In der Regel gibt es keinen Algorithmus für die Umwandlung einer rekursiven form in einem iterativen. Dieses problem ist unentscheidbaren. Als ein Beispiel, betrachten Sie diese rekursive definition einer Funktion definiert, die die Collatz-Folge:

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

    Es ist nicht bekannt, ob oder nicht, das ist auch eine gut definierte Funktion oder nicht. Waren ein Algorithmus existieren, der könnte konvertieren, das in einer geschlossenen form, wir könnten entscheiden, ob oder nicht es war gut definiert.

    Jedoch, für die vielen gemeinsamen Fällen ist es möglich, zu konvertieren, eine rekursive definition in eine iterative. Die ausgezeichnete lehrbuch Concrete Mathematics verbringt viel seiner Seiten zeigen, wie dies zu tun. Eine gängige Methode, die Recht gut funktioniert, wenn Sie haben eine Vermutung, was die Antwort ist, ist die Verwendung von Induktion. Als ein Beispiel für deinen Fall, nehme an, dass Sie glauben, dass Ihre rekursive definition ist in der Tat 3^n - 1. Um dies zu beweisen, versuchen zu beweisen, dass es gilt für die Basis-Fällen, dann zeigen Sie, dass dieses wissen können Sie verallgemeinern die Lösung nach oben. Sie hat nicht den Normalfall in deinem post, aber ich gehe davon aus, dass

    f(0) = 0
f(1) = 2

    Gegeben, lasst uns sehen, ob Ihre Vermutung richtig ist. Für die spezifische Eingänge 0 und 1, Sie können überprüfen Sie durch Inspektion, dass die Funktion nicht berechnen 3^n - 1. Für den induktiven Schritt, lassen Sie uns davon ausgehen, dass für alle n' < n, dass f(n) = 3^n - 1. Dann haben wir, dass

    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

    Wir haben also gerade bewiesen, dass dieser rekursive Funktion tatsächlich produzieren 3^n - 1.

    InformationsquelleAutor der Antwort templatetypedef

Schreibe einen Kommentar