---

Geschrieben von sebaa am 07.11.2018 um 18:55:

  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?

---

Geschrieben von Gast am 10.11.2018 um 21:23:

 

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.