Gibt es eine Formel mit der man eine rekursive Folge in eine explizite Folge umschreiben kann?
4 Antworten
In der Schule lernt man die Formeln für arithmetische und geometrische Folgen und Reihen:
- aₙ₊₁=aₙ+c ⇔ aₙ=c·n+a₀ ⇔ Σᵢ₌₀..ₙ aᵢ=c·n·(n+1)/2+n·a₀
- aₙ₊₁=c·aₙ ⇔ aₙ=a₀·cⁿ ⇔ Σᵢ₌₀..ₙ aᵢ=a₀·(cⁿ–1)/(c·–1)
Eine allgemeine Formel gibt es nicht. So muss man jede rekursive Folge ganz individuell untersuchen. Ein mächtiges Werkzeug dafür sind erzeugende Funktionen.
Mir ist das nur für Einzelfälle bekannt, mich würde das aber auch mal interessieren.
Mein Prof hat mal so nebenbei gezeigt, dass man sogar für die Fibonacci-Folge eine explizite Bildungsvorschrift der Form Fn=(1+√52)n−(1−√52)n√5 finden kann.
Ich hatte mal wieder eine ähnliche Aufgabe gesehen und wüsste gerne, ob es da zumindest einen groben Ansatz für die Methodik gibt.
Falls sich hier ein übereifriger Experte befindet, wie kommt man von a(n+1) = 2a(n) + 1 mit a(1) = 1 auf a(n) = 2ⁿ - 1?
Es würde mich nicht wundern, wenn manchmal die explizite Darstellung nur in Form einer unendlichen Reihenentwicklung gelingt.
Verteile die Konstante +1 gleichmäßig auf alle Vorkommen von a():
a(n+1) = 2a(n) + 1
[a(n+1)+1] = 2·[a(n)+1]
a(n)+1 ist offensichtlich eine geometrische Folge.
Tatsächlich gibt es ein solches Verfahren, was aber meist in der Informatik angewendet wird:
https://www.youtube.com/watch?v=eDPiPQ15oXk
Die Beschreibungen die cih für Mathematik gefunden habe haben jeweils nur ganz kleine Teilaspekte abgebildet.
Wenn ein Algorithmus endrekursiv ist, lässt er sich problemlos in einen iterativen Algorithmus umschreiben. Andernfalls ist dies leider nicht immer so einfach möglich.
Es geht hier um explizite und rekursive Bildungsvorschriften für Folgen, nicht Algorithmen.
Der Unterschied liegt darin, dass man dafür mindestens ein grundlegendes Verständnis von Algorithmen haben muss.
Dem FS geht es höchtswahrscheinlich darum, wie man das für einfache artithmetische Folgen oder Potenzfolgen umwandelt. Es besteht eine gute Wahrscheinlichkeit, dass der FS keinerlei Programmierkenntnisse hat.
Die benötigte Transferleistung, um von dem verlinkten Artikel auf das gewünschte Ergebnis zu kommen, ist eher nicht einem 10.-Klässler zuzumuten.
Dann ist aber die Frage falsch gestellt. Witzigerweise habe ich im Netz kein generelles VErfahren für das Thema gefunden, ausser eben die Informatik-Lösung. Letztich kann man aber jeden auf einem Von-Neumann-Rechner implementierbaren Algorithmus auf eine Folge zurück führen.Die ist dann zwar möglicherweise ein wenig komplex, aber gehen tut es :-)
Das stimmt wohl, und man könnte den Algorithmus auch in Scratch implementieren ;)
Die Frage ist hier eher, ob man das auch wirklich kann. Meine Meinung dazu kennst du ja und mir wäre auch lieber, wenn der FS seine Frage etwas genauer ausgeführt hätte. Aber gerade, weil das nicht geschehen ist, bin ich zu meiner Annahme gekommen.
Allgemein gehts leider nicht. Sprich nicht jede Rekursive Folge hat eine explizite Darstellung.
Es gibt zwar bestimmte Verfahren die mal zum Ziel führen und manchmal nicht aber im wesentlichen ists immer eine eigene Arbeit für jede Folge.