Beweis Anzahl Knoten eines Baumes

[DaKa]

Hallo,

wir müssen für unsere nächste Klausur eine Formel beweisen.

Ich kann zwar durch ausprobieren erkennen, dass die Formel korrekt ist, aber habe keine Ahnung wie ich das beweisen kann.

********************************

FOLGENDE PROBLEMSTELLUNG:

- wie berechnet man die Anzahl aller Knoten eines Baumes, wobei die Baumgröße zum einen von der Tiefe des Baumes, zum anderen davon abhängt, wie viele Kindknoten jedes Kind hat.

Es gilt:

- die Tiefe aller Blaetter ist gleich

- er ist echt dÄr (alle Knoten außer den Blättern haben denselben Grad)

FORMEL:

(d^(t+1)-1)/d-1

t:= Tiefe des Baumes

d:= Grad

Setze ich für z.B. d = 3 und t = 2 ein, erhalte ich 13. Dies ist z.B. ja auch die Korrekte Anzahl der Knoten dieses Baumes.

Wie kann ich das allgemeiner beweisen oder diese Formel herleiten?

Vielen Dank für Eure Mühen,

André

[lupo49]

Eventuell hilft das hier weiter:

Eulerscher Polyedersatz ? Wikipedia

Vollständige Induktion ? Wikipedia

[DaKa]

vielen Dank für die schnelle Antwort. Hat geklappt -> Induktion war der entscheidende Tipp