0 Daumen
364 Aufrufe

In einem k-nären Baum hat jeder Knoten genau k oder 0 Söhne (ein binärer Baum ist zum Beispiel 2-när). Beweisen Sie durch vollständige Induktion, dass in einem k-nären Baum der Höhe h die maximale Anzahl an Knoten (k^h −1)/(k−1) ist.


Ich komme bei dieser Aufgabe leider nicht weiter. Der Induktionsanfang wäre ja h auf 0 zu setzen so das gilt das keine weiteren Söhne existieren. also (k^0 -1) / (k-1) = 0. Ist also eine wahre Aussage.


Nur beim Induktionsschritt tue ich mich ein wenig schwer. Zu zeigen ist ja das die obige Formel äquivalent ist zu (k^h+1  -1)/(k-1).  Nur wie gehe ich da vor ?


Kann mir jemand sagen wie er bei der Lösung vorgegangen ist ?


Vielen Dank im voraus und natürlich würde ich die beste Antwort markieren ^^

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community