Posted by Philipp Weis am July 23, 2002 at 11:55:18:
In Reply to: Blatt 3, Aufgabe 5 posted by Martin on July 21, 2002 at 17:35:57:
Das ist ein Fehler in der Musterlösung, so kann das natürlich nicht funktionieren.
Der Trick ist, dass du nur den unvollständigen Teilbaum D mit der Induktionsvoraussetzung abschätzt. Für die anderen, vollständigen Bäume kannst du ja die Anzahl der inneren Knoten genau berechnen. Die ist nämlich I(T(b^{s-1}, s-1)) = b^{s-1}/(b-1) (geometrische Summe, müsst eigentlich auch im Skript stehen).
Wenn du so abschätzt, dann hast du Schluss den Term a(s-1) nicht mehr und die Welt ist wieder in Ordnung!
Philipp