Lineare Rekursionsgleichung

Aufrufe: 896     Aktiv: 17.10.2021 um 07:55

0
Hi Leute,
im Rahmen  einer Algorithmen und Datenstrukturen Vorlesung kam folgende Frage auf...  kann hier vielleicht jemand weiterhelfen, wie man auf das Ergebnis kommt? Ich habe diverse Beispiele im Netz gefunden, aber leider kann ich durch kombinieren meine Aufgabe nicht damit hinbekommen.

EDIT vom 16.10.2021 um 15:56:

meine Formel:

EDIT vom 16.10.2021 um 19:34:


Etc etc für T(4) usw.
Diese Frage melden
gefragt

Student, Punkte: 32

 
Kommentar schreiben
1 Antwort
1
Ist Dein google kaputt? Man findet im Netz diverse Erklärungen wie man das rechnet, das sind auch gleich die obersten Treffer.
Lineare zweigliedrige Rekursionen mit konstanten Koeffizienten der Form $x_n+a\,x_{n-1}+b\,x_{n-2}=c$ haben die allgemeine Lösung
$x_n = c_1\,x_1^n+c_2\,x_2^n+c_3$, wobei $x_1,x_2$ die Nullstellen des char. Polynoms $x^2+a\,x+b$ sind und $c_1,c_2,c_3$ noch anzupassende Konstanten. Das gilt im Fall $x_1\neq x_2$.
Was erhälst Du damit als Lösung?
(EDIT: Lösungsansatz korrigiert)
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 39.6K

 

Sorry, hatte mich vielleicht ausgedrückt. Ich bräuchte nur mal die Sicht in diesem Kontext von Laufzeiten von Algorithmen. Aber ich danke dir. Werde die Frage nochmal im Informatikforum stellen, da ich von der Formel aus dem Mathebuch nicht direkt auf meine Formel schließen kann   ─   sokoviaaccords 16.10.2021 um 15:32

Hi Mikn, danke für die Hilfe. habe mal meine Formel als EDIT ergänzt und die die du gepostet hat, ist die gängige die ich sonst auf Youtube oder Google finde.   ─   sokoviaaccords 16.10.2021 um 15:57

Ich danke euch für die Hilfe. Ich habe die geom. Summe genommen und dann für n entsprechende Werte eingesetzt. Aber leider komme ich nicht auf die Werte, die ich durch Induktion ermittelt habe. Benötigt ihr ein Foto davon oder wisst ihr, was ich meine? Tausend Dank euch   ─   sokoviaaccords 16.10.2021 um 18:55

Hab es mal angehangen. @cauchy sorry für die vielleicht laienhafte Verwendung der Begriffe.

Nach meinem Verständnis müsste ich in deine Formel 2 für n einsetzen und das gleiche herausbekommen wie T(2) in meinen Notizen. Wo ist mein Fehler?
  ─   sokoviaaccords 16.10.2021 um 19:35

Vielen Dank für eure Hilfe, damit ist das Problem geklärt. Einerseits die Herleitung der geom. Summe und andererseits dass die Formel nur für jedes 2. n gilt, hilft mir enorm :)   ─   sokoviaaccords 17.10.2021 um 07:55

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.