Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Vollständige Induktion einer rekursiven Gleichung

Vollständige Induktion einer rekursiven Gleichung

Universität / Fachhochschule

Sonstiges

Tags: Induktion, Rekursion, Sonstig

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Hotweb

Hotweb aktiv_icon

10:19 Uhr, 09.05.2022

Antworten
Guten Tag,

Ich sitze aktuell an folgender Aufgabe:

Gegeben sei die rekursive Laufzeitgleichung T(n) mit:
T(n)=1 für n=1
T(n)=8T(n2)+n2n für n>1

Zeigen Sie mittels Induktion dass
T(n)=(2+2)n3-(1+2)n2n
gilt. Gehen Sie dafür davon aus, dass n eine Zweierpotenz ist (n=2k mit k).


Aktuell habe ich:

Induktionsanfang:
n=1
T(1)=(2+2)13-(1+2)121
1=1

Induktionsschritt:
Vorraussetzung: Es sei T(n)=(2+2)n3-(1+2)n2n für ein beliebiges n.
Behauptung: Dann gilt für n+1:T(n+1)=(2+2)(n+1)3-(1+2)(n+1)2n+1

Induktionsschluss:
8T(n+12)+(n+1)2n+1



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."
Antwort
HAL9000

HAL9000 aktiv_icon

10:33 Uhr, 09.05.2022

Antworten
Nun, eigentlich führt man hier eine Vollständige Induktion nicht über n sondern über k durch, wobei n=2k.

Der Induktionsschritt kk+1 entspricht in dem Sinne dann n2n statt deines nn+1.
Hotweb

Hotweb aktiv_icon

11:40 Uhr, 09.05.2022

Antworten
Vielen Dank für die Antwort.

Ich habe es nun umformuliert, sodass ich nun bei:

Vorraussetzung: T(2k)=(2+2)(2k)3-(1+2)(2k)22k
Behauptung: für k+1:T(2k+1)=(2+2)(2k+1)3-(1+2)(2k+1)22k+1

habe.
Somit komm ich für den Induktionsschluss auf :
T(2k+1)=8T(2k+12)+(2k+1)22k+1

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
Antwort
HAL9000

HAL9000 aktiv_icon

12:54 Uhr, 09.05.2022

Antworten
Du weißt schon, dass 2k+12=2k212=2k ist, und du daher bei T(2k+12)=T(2k) die Induktionsvoraussetzung einsetzen kannst?
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.