(Twitter)
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)
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
Link
geantwortet
mikn
Lehrer/Professor, Punkte: 38.86K
Lehrer/Professor, Punkte: 38.86K
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
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.