Question

Vollständige Induktion: Anzahl Wörter der Länge höchstens n über dem Alphabet {0,1}

ich muss diese Aufgabe mit Vollständige Induktion lösen die Idee dass ich in IS geometrische summenformel verwende aber komme nicht mehr weiter.

Answer 1

Hallo, fang mit n=2 an, wieviele Worte gibt es mit <=n Buchstaben. 7

Wenn man jetzt von 2 nach 3 geht, wieviele neue kommen dazu? kannst du das aus der Anzahl 7 bei 2 herausfinden, ohne alle aufzuschreiben? auf dieselbe Weise kommst du von n nach n+1

Alle alten bleiben, denn es sind ja alle mit weniger als  3 dabei, Nur neue mit 3 kommen dazu, die stellt man aus den 2 Buchstaben ( bzw n buchstabiegen her) wieviele? das addiere.

Bei der Induktion musst du doch nur benutzen, wieviele  neue Worte du durch zufügen einer 1 und durch zufügen einer 0 machen kannst.

Gruß lul

Answer 2

Du kannst dieses Problem auf einen vollständigen binären Baum der Höhe n zurückführen. Dort wird jedem Wort ein Knoten zugewiesen. Zeige nun durch vollständige Induktion, dass dieser Baum genau 2^{n+1}-1 Knoten hat. Hier mal eine Skizze als Unterstützung:

Im Induktionsschritt betrachtest du nun so einen Baum (nach Induktionsvoraussetzung ist die Knotenanzahl ja schon bekannt) und packst zu diesem Baum noch eine Schicht unten dran, sodass du wieder einen vollständigen binären Baum nun mit Höhe n+1 hast.