|
Guten Tag,
Ich sitze aktuell an folgender Aufgabe:
Gegeben sei die rekursive Laufzeitgleichung mit: für für
Zeigen Sie mittels Induktion dass gilt. Gehen Sie dafür davon aus, dass eine Zweierpotenz ist mit .
Aktuell habe ich:
Induktionsanfang:
Induktionsschritt: Vorraussetzung: Es sei für ein beliebiges . Behauptung: Dann gilt für
Induktionsschluss:
Ich habe jetzt aktuell allerdings das Problem, dass ich ab hier nicht weiterkomme. Ich weiß zwar, dass ich nun so auflösen und umformen muss, dass ich die Vorraussetzung benutzen kann. Allerdings komm ich nicht wirklich zu diesem Punkt.
Schon mal vielen Dank vorweg und Grüße.
Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
|
Nun, eigentlich führt man hier eine Vollständige Induktion nicht über sondern über durch, wobei .
Der Induktionsschritt entspricht in dem Sinne dann statt deines .
|
|
Vielen Dank für die Antwort.
Ich habe es nun umformuliert, sodass ich nun bei:
Vorraussetzung: Behauptung: für
habe. Somit komm ich für den Induktionsschluss auf :
Ich habe allerdings weiterhin das Problem, dass ich nicht wirklich weiß wie ich zu dem Punkt komme an dem ich meine Vorraussetzung einsetzen kann.
Grüße
|
|
Du weißt schon, dass ist, und du daher bei die Induktionsvoraussetzung einsetzen kannst?
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|