Die letzten 2 Beiträge |
Gast |
Zu a)
Das Prinzip der vollständigen Induktion beruht darauf, einen Startwert ohne Vorgänger zu finden und daraus formal auf den ersten Nachfolger zu schließen.
Zu b)
Anstatt die Anzahl von Elementen in absoluten Zahlen anzugeben, wäre es doch sicher besser eine Formel zu besitzen. |
sebaa |
vollständige Induktion
Meine Frage:
Eine Abbildung B: N0 × N0 ? N0 ist folgendermaßen definiert:
für jedes k E N0 : B(k, 0) = 1
für jedes m E N0 : B(0, m) = 1
für jedes k E N0 und jedes m E N0 :B(k + 1, m + 1) = B(k + 1, m) + B(k, m + 1)
a) Beweisen Sie mittels vollständiger Induktion:
Für jedes n ? N0 gilt B(n, n) ? 2^n
.
b) Begründen Sie, warum für jedes k E N0 und jedes m E N0 der Wert B(k, m)
die Zahl verschiedener Wörter w E {a, b}*
ist, in denen das Zeichen a
genau k mal vorkommt und das Zeichen b genau m mal.
Meine Ideen:
Ich verstehe leider nicht genau die Aufgaben. Bin völlig planlos
Könnte mir bitte jemand erklären? |
|
|