Beweis durch vollständige Induktion: Binärbaum

Question

Text erkannt:

Beweisen Sie die folgende Aussage per Induktion:
Die Anzahl der Kanten in einem vollständigen Binärbaum der Höhe \( h \) ist \( 2^{h+1}-2 \).

Aufgabe:

siehe Oben.

Problem/Ansatz:

habe mich mit dieser Aufgabe beschäftigt und es hat sich rausgestellt dass es total falsch war. Wie muss ich hier vorgehen ? Vielen Dank im Voraus für die Tipps, eine Lösung wäre auch okay dann würde ich es ein paar mal durchgehen und verinnerlichen.

Answer 1

h=0 ==>  keine Kanten, passt zu 2^(0+1)-2 = 0

Es gelte für h. Zeige: Dann gilt es auch für h+1.

Ein vollständiger Binärbaum der Höhe h+1 entsteht dadurch,

dass man an eine Wurzel zwei vollständige Binärbäume

der Höhe h anhängt. Dann gibt es zwei Kanten, die von der Wurzel

ausgehen und daran hängt rechts und links je ein vollständiger

Binärbaum, also hat der h+1 Baum an Kanten

 2 + 2 * (Kantenzahl vom Baum der Höhe h )

Das gibt nach Ind.annahme

 2 + 2* (2^(h+1)-2)

= 2 + 2*2^(h+1) - 4

= 2*2^(h+1) - 2

= 2^(h+2) - 2.  Das passt !