Vollständige Induktion Anzahl Möglichkeiten

Neue Frage »

dohx Auf diesen Beitrag antworten »
Vollständige Induktion Anzahl Möglichkeiten
Hallo ihr Lieben,

ich brauch mal wieder eure Hilfe. Und zwar soll ich eine v. Induktion für die Möglichkeiten der Länge n beträgt 2^n bei 2 Charakter-Möglichkeiten führen. Ich komm nur mit den Gedanken nicht weiter weil ich nicht weiß wie ich das beweisen soll, z.B. wenn ich beweisen muss ob etwas < ist. Versuche ich den Ausdruck immer weiter aufgrund der Annahme runter zu brechen. Aber was tu ich hier? Mit was setze ich die Annahme gleich? n = 1, 2^1 = 2 ich weiß das es richtig ist aber was kommt hier auf die Seite?
Elvis Auf diesen Beitrag antworten »

Induktionsanfang:
Induktionsvoraussetzung:
Induktionsschluss:
q.e.d.

Jede Erklärung hätte sehr viel länger gedauert als den Beweis mal eben hinzuschreiben. Bitte entschuldige meine Ungeduld.
Leopold Auf diesen Beitrag antworten »

Sehr gut kann man sich das auch an einem Baum vorstellen, wie man ihn aus der Schule bei Bernoulli-Ketten kennt: 0 für Erfolg, 1 für Mißerfolg. In jeder neuen Stufe findet bei jedem Knoten eine Verzweigung statt, ein Ast zeigt zur 0, der andere zur 1. Die Anzahl der Pfade verdoppelt sich so von Stufe zu Stufe. Wenn man den Baum von links nach rechts zeichnet, nach oben immer den Ast zur 0, nach unten den zur 1, kann man die Pfade von oben nach unten ordnen.

Für sähe das so aus: 00,01,10,11

Für die nächste Stufe wird bei jedem bisherigen Pfad wieder entweder zur 0 oder zur 1 verzweigt:

Aus 00 wird 000,001.
Aus 01 wird 010,011.
Aus 10 wird 100,101.
Aus 11 wird 110,111.

Und die Pfade sind von oben nach unten automatisch wie die Zahlen im Binärsystem geordnet:

000,001,010,011,100,101,110,111

So entstehen die Zweierpotenzen beim Zählen der Pfade.

Ist natürlich auch nichts anderes, als was Elvis sagte, nur auf ganz anschaulichem Niveau.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »