0 Daumen
300 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

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...