Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
8.4 Fast Absolute Power – Induktionsbeweis
Hallo,
kann jemand mir sagen, welcher Induktionsschritt hier sein soll? n → n + 2 oder n → 2n?
Außerdem finde ich schwierig, im Induktionsschluss z.B. fap(b*b, e) zu Induktionsvoraussetzung fap(b, 2e) zurück führen. Kann jemand einen Tipp geben?
Danke!
Hi 
Bin nicht im aktuellen AuD Kurs, hab aber die Aufgabe in den alten Übungsaufgaben gefunden und mir angeschaut.
Normalerweise müsste man bei einer Induktion mit 2 sich über den Aufrufbaum hinweg verändernden Variablen ja 2 Schritte jeweils über eine der Variablen machen. Hier würde ich das aber anders machen. Ich hab meine Induktionsanfänge so gewählt und bewiesen, dass sie für ein bestimmtes e immer die Korrektheit für alle möglichen b zeigen.
Dann reicht ein einziger Induktionsschritt von e auf 2e (also Induktionsvorraussetzung fap(b,e)=|b|^e), den du relativ leicht beweisen kannst.
Ich send dir meine Lösung jz mal nicht, um dir den Spaß nicht zu verderben, aber ich glaub an dich
Viel Erfolg!
Vielen Danke für die Antwort.
Aber ich konnte mich nicht vorstellen, welche Induktionsanfänge hier gewählt werden können.
Bis jetzt habe die IA0 (0,0), IA1(b,0) für gerade Zahlen und IA2(b,1) für ungerade Zahlen(natürlich muss für positive und negative b zeigen) gewählt. Wie du gesagt, muss ich für ein bestimmtes e für alle b zeigen. D.h. (b, e) soll auch als Induktionsanfang gewählt werden? Oder habe etwas Missverständnis?
IA (0,0) kannst du zwar nehmen, ist allerdings relativ unnötig wenn du IA (b,0) hast, weil (0,0) ja in (b,0) enthalten ist. IA1 und IA2 sind super (das meinte ich mit "für ein bestimmtes e alle b zeigen). Wenn du (b,e) als Induktionsanfang ohne weiteres beweisen könntest, bräuchtest du ja die ganze Induktion nicht ;). Also dein IA1 und IA2 passen genau (Wenn du sie beweist; nicht vergessen, hat mich mal 2 Punkte gekostet…).
Allerdings ist mir gerade ein kleiner Fehler in meiner Lösung aufgefallen. Der Schritt e auf 2e stimmt zwar, man braucht aber natürlich danach auch den Schritt von 2e auf 2e+1, um die Aussage auch für ungerade e zu beweisen.
Also:
IV1: fap(b,e)=|b|^e; IS1: e → 2e;
IV2: fap(b,2e)=|b|^2e; IS1: 2e → 2e+1;
Hoffe ich konnte dir helfen und schreib mir gerne falls du noch Fragen hast
Ja, die grobe Struktur ist mir jetzt klar.
Es gibt noch ein Problem, wie ich am Anfang gestellt habe. Es ist schwierig, dass IS1 per IV1 beweisen können.
Da fap(b, 2e) kann fast nie wieder mit fap(b, e) darstellen. b wird stetig quadratisch, 2e wird immer halbieren. Die beide passen immer nicht wieder. Meiner Meinung nach führt e wieder zu 0. Aber das Prozess ist schwer zu formulieren.
Oder gibt es noch eine bessere Idee?
Du machst es dir zu schwer.
Was b ist, ist ja völlig egal, weil IV setzt voraus, dass die Aussage für irgendein b gilt, also auch b^2. Schließlich zeigt dein Induktionsanfang die Aussage ja bei enem bestimmten e für alle b (again: Wenn richtig bewiesen).
Du machst den Induktionsschritt nur über e.
Ich weiß ist ein bisschen verwirrend formuliert, aber weiß nicht wie ich das ausdrücken soll ohne die ganze Lösung preiszugeben…