TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 158

Man beweise die Beziehung ${\binom {n+1}{k+1}}={\binom {n}{k+1}}+{\binom {n}{k}}$ mit Hilfe der Formel ${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}$.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Fakultät

Binomialkoeffizient

Binomialkoeffizient

$\forall n,k\in \mathbb {N} ,k\leq n:\qquad {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}$

Äquivalente Definition (Merkregel): ${\binom {n}{k}}={\frac {\overbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} ^{k\;{\text{Glieder}}}}{\underbrace {1\cdot 2\cdots k} _{k\;{\text{Glieder}}}}}$ Spezialfall: ${\tbinom {n}{0}}:=1$

Lösungsvorschlag

Noch kürzer und intuitiver als in Mathematik für Informatik geht es folgendermaßen:

Zuerst müssen wir die Binomialkoeffizienten auflösen, das gelingt noch relativ einfach nach der Definition:

${\binom {n}{k+1}}+{\binom {n}{k}}={\frac {n!}{(k+1)!(n-k-1)!}}+{\frac {n!}{k!(n-k)!}}$

Anschließend müssen wir beide Brüche auf einen gemeinsamen Nenner bekommen. Dazu bilden wir das kleinste gemeinsame Vielfache von beiden Nennern. Wir versuchen dazu zuerst so herauszuheben, dass sich das kgV leicht erschließt:

${\frac {n!}{(k+1)!(n-k-1)!}}+{\frac {n!}{k!(n-k)!}}={\frac {n!}{k!(k+1)(n-k-1)!}}+{\frac {n!}{k!(n-k-1)!(n-k)}}$

Wir sehen nun, dass in beiden Zählern $k!(n-k-1)!$ vorkommt, einmalig kommen die Terme $k+1$ bzw. $n-k$ vor. Das kleinste gemeinsame Vielfache ist demnach $k!(n-k-1)!(k+1)(n-k)$, das wir als neuen Zähler verwenden (die Nenner erweitern wir entsprechend um die einmalig vorkommenden Terme):

${\frac {n!}{k!(k+1)(n-k-1)!}}+{\frac {n!}{k!(n-k-1)!(n-k)}}={\frac {n!(n-k)+n!(k+1)}{k!(n-k-1)!(k+1)(n-k)}}$

Jetzt können wir ausmultiplizieren:

${\frac {n!(n-k)+n!(k+1)}{k!(n-k-1)!(k+1)(n-k)}}={\frac {n!n-n!k+n!k+n!}{k!(k+1)(n-k-1)!(n-k)}}={\frac {n!n+n!}{(k+1)!(n-k)!}}={\frac {n!(n+1)}{(k+1)!(n-k)!}}={\frac {(n+1)!}{(k+1)!(n-k)!}}$

Zu guter Letzt wenden wir noch den Binomialkoeffizent an:

${\frac {(n+1)!}{(k+1)!(n-k)!}}={\binom {n+1}{k+1}}$

Lösungsvorschlag aus Mathematik für Informatik

Die Lösung im Buch Mathematik für Informatik ist nicht kommentiert und deshalb vielleicht etwas schwierig zu verstehen. Ich versuche mich deshalb an einer ausführlicheren Lösung, die aber den gleichen Weg verwendet:

Zuerst müssen wir die Binomialkoeffizienten auflösen, das gelingt noch relativ einfach nach der Definition:

${\binom {n}{k+1}}+{\binom {n}{k}}={\frac {n!}{(k+1)!(n-k-1)!}}+{\frac {n!}{k!(n-k)!}}$

Anschließend müssen wir beide Brüche auf einen gemeinsamen Nenner bekommen. Dazu formen wir zuerst um und heben dann heraus. Um diesen Schritt zu verstehen, muss man verstehen, wie man aus einer Fakultät herausheben kann:

${\frac {n!}{(k+1)!(n-k-1)!}}+{\frac {n!}{k!(n-k)!}}={\frac {n!}{k!(k+1)(n-k-1)!}}+{\frac {n!}{k!(n-k-1)!(n-k)}}$

Nun können wir den Bruch ${\frac {n!}{k!(n-k-1)!}}$, der ja im Nenner von beiden Brüchen vorkommt, herausheben:

${\frac {n!}{k!(k+1)(n-k-1)!}}+{\frac {n!}{k!(n-k-1)!(n-k)}}={\frac {n!}{k!(n-k-1)!}}\cdot \left({\frac {1}{k+1}}+{\frac {1}{n-k}}\right)$

Jetzt bringen wir die zwei Brüche in der Klammer auf einen gemeinsamen Nenner, in dem wir diese ausmultiplizieren:

${\frac {n!}{k!(n-k-1)!}}\cdot \left({\frac {1}{k+1}}+{\frac {1}{n-k}}\right)={\frac {n!}{k!(n-k-1)!}}\cdot \left({\frac {n-k}{(k+1)(n-k)}}+{\frac {k+1}{(n-k)(k+1)}}\right)$

Jetzt können wir die Brüche addieren:

${\frac {n!}{k!(n-k-1)!}}\cdot \left({\frac {n-k}{(k+1)(n-k)}}+{\frac {k+1}{(n-k)(k+1)}}\right)={\frac {n!}{k!(n-k-1)!}}\cdot {\frac {n-k+k+1}{(k+1)(n-k)}}={\frac {n!}{k!(n-k-1)!}}\cdot {\frac {n+1}{(k+1)(n-k)}}$

Und nun haben wir nur mehr eine Multiplikation, die wir einfach ausmultiplizieren können. Zum Schluss wenden wir die Formel für den Binomialkoeffizient an und wir sind fertig:

${\frac {n!}{k!(n-k-1)!}}\cdot {\frac {n+1}{(k+1)(n-k)}}={\frac {(n+1)!}{(k+1)!(n-k)!}}={\binom {n+1}{k+1}}$

-- Superwayne 20:51, 26. Nov. 2014 (CET)

Quelle: Datei:TU Wien-Algebra und Diskrete Mathematik VO (Karigl) - Mathematik für Informatik.pdf (S. 52)