vollständige Induktion |
| 07.11.2018, 18:55 | Auf diesen Beitrag antworten » |
| 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? |
|
|
|
| 10.11.2018, 21:23 | Auf diesen Beitrag antworten » |
| 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. |
|
|
