Zahlenfolge



  • Hi Leute,
    ich benötige eine Formel oder ein schnelles Verfahren mit dem man die Zahl an einer gewissen Stelle der Zahlenfolge bestimmen kann.
    Also die Zahlenfolge sieht folgendermaßen aus (es gilt Punkt- vor Strichrechnung):
    I a/b
    II (a+a/b)/b
    III (a+(a+a/b)/b+a/b)/b
    IV (a+III+II+I)/b
    V (a+IV+III+II+I)/b
    VI (a+V+IV+III+II+I)/b
    bzw. allgemein:
    zu dem Wert a wird die Summe der vorherigen Zahlen hinzuaddiert und dann das ganze durch b geteilt.
    Ich weiß nicht, ob man für so eine Zahlenfolge überhaupt eine Formel entwickeln kann, aber mit meiner rekursiven Funktion stoße ich dann doch recht schnell an Grenzen.

    Ich bin für jeden Hinweis oder jede Idee sehr dankbar,
    ich hoffe einer von euch kann mit weiterhelfen.

    Gruß Daniel



  • a/b *(1+1/b)^N
    für N = 0,1,2,3....



  • Cool, vielen Dank space!
    Eine Frage noch, wie kommt man darauf? Das will ich auch können 🙂



  • Hallo

    Das erklär ich dir gerne.
    Bevor ich mir aber die Finger vielleicht umsonst blutig tippe:
    Weisst du was man in der Mathematik unter "Reihen" und "Binomialkoeffizienten" versteht ?

    Wenn nicht, auch nicht schlimm. Wird dann aber ein etwas längerer Beitrag 😉

    (Bin jetzt aber vorerst weg...antwort evtl. erst morgen)

    [ Dieser Beitrag wurde am 08.06.2003 um 20:59 Uhr von space editiert. ]



  • Binomialkoeffizienten sind klar, aber Reihen könntest du erklären. Danke!



  • Hallo

    Eine Reihe ist, grob gesagt, eine Summe. Überlicherweise verwendet man das große Sigma als Symbol dafür.
    Da das hier nicht darstellbar ist, verwende ich folgende Notation:
    sum(i=1;n){i} = 1+2+3+...+n
    i ist der Summationsindex, der hier von 1 bis n läuft. Summiert wird über das, was in den geschweiften Klammern steht.
    Also nur i hier.
    Anderes Beispiel:
    sum(i=0;n){a^i} = a^0 + a^1 + a^2 + ... + a^n
    Hier wird über a^i summiert wobei i wieder der Summationsindex ist.

    Die Binomialkoeffizienten "n über k" schreibe ich im folgenden als "bin(n,k)"

    Als zweites ist der Binomische Lehrsatz notwendig. Allgemein lautet er:
    (a + b)^n = sum(i=0;n){ bin(n,i)*a(n-i)*bi }

    Beispiel für n = 2:
    (a+b)^2 = sum(i=0;2){ bin(2,i)*a(2-i)*bi }
    = bin(2,0)*a2*b0 + bin(2,1)*a1*b1 + bin(2,2)*a0*b2
    = a^2 + 2ab + b^2

    Das entspricht ja genau dem Spezialfall der Bin. Formel wie man sie aus der Schule kennt.

    Zum eigentlichen Problem:
    Um zu einer gegebenen Rekursionsgleichungen eine explizite Form zu finden gibt es mehrere Ansätze.
    Der einfachste und naheliegendste besteht darin, die ersten 3 oder 4 Rekursionen zu berechnen, hinzuschreiben
    und zu versuchen daraus eine Reihe oder direkt eine Formel zu entwickeln.
    (Entdeckt man eine Formel, müsste man deren Korrektheit eigentlich noch beweisen, z.B. durch Induktion.
    Hatte aber keine Lust dazu)

    Also wird das jetzt gemacht. Im Gegensatz zu dir löse ich aber alle Klammern auf:

    1: a/b
    2: a/b + a/(b^2)
    3: a/b + 2a/(b^2) + a/(b^3)
    4: a/b + 3a/(b^2) + 3a/(b^3) + a/(b^4)
    5: a/b + 4a/(b^2) + 6a/(b^3) + 4a/(b^4) + a/(b^5)
    u.s.w.

    Jetzt heißt es Regeln zu suchen, durch welche die obigen Ausdrücke gebildet werden

    1. Wenn man die Binomialkoeffizienten kennt, sieht man hier schon direkt, dass eine einfache Regelmäßigkeit vorliegt.
      Die Koeffizienten sind nämlich
      1: ....1
      2: ...1 1
      3: ..1 2 1
      4: .1 3 3 1
      5: 1 4 6 4 1

    Wie im Pascalschen Dreieck.

    1. Es ist stets eine Summe, die um einen Summanden "wächst" bei fortschreitender Anwendung der Rekursion

    2. a/(b^i) ist immer zu finden. i läuft dabei von 0 bis N.

    Daraus lässt sich jetzt folgende Reihe basteln:

    bin(N,0)*a/b + bin(N,1)*a/(b^2) + bin(N,2)*a/(b^3) + ... + bin(N,N-1)*a/(b^(N)) + bin(N,N)*a/(b^(N+1))

    Und in verkürzter Schreibweise:
    sum(i=0,N){ bin(N,i) * a/(b^(i+1)) }

    Etwas umformen:
    sum(i=0,N){ bin(N,i) * a * 1/(b^(i+1)) } // Statt a/b einfach a*1/b
    = a * sum(i=0,N){ bin(N,i) * 1/(b^(i+1)) } //a ist unabhängig vom Summationsindex und kann rausgezogen werden
    = a/b * sum(i=0,N){ bin(N,i) * 1/(b^i) } //Ein 1/b stört und wird auch herausgezogen
    = a/b * sum(i=0,N){ bin(N,i) * 1^(N-i) * 1/(b^i) } //Multiplikation mit 1 ändert nichts.

    Im letzten Schritt ist der Faktor 1^(N-i) dazu gekommen.
    Das hat einen einfachen Grund. Jetzt sieht die Reihe genauso aus wie im Binomischen Leersatz.
    Was oben a war ist hier 1, und was oben b war ist hier 1/b.
    Also:

    a/b * sum(i=0,N){ bin(N,i) * 1^(N-i) * (1/b)^i) } // Beachte 1/(b^i) = (1/b)^i
    = a/b * (1 + 1/b)^N

    Fertig.


Anmelden zum Antworten