TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 153

Aus VoWi
Zur Navigation springen Zur Suche springen

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)!}.

Hilfreiches[Bearbeiten]

Baustein:Fakultät

Binomialkoeffizient[Bearbeiten, WP, 2.03 Definition]
\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\cdot2\cdots k}_{k\;\text{Glieder}}} Spezialfall: \tbinom{n}{0}:=1

Lösungsvorschlag[Bearbeiten]

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[Bearbeiten]

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)