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

Man beweise nachstehende Identitäten für Binomialkoeffizienten:

(a)$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{n-k})$ (b)$(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k+1})=(\genfrac{}{}{0ex}{}{n+1}{k+1})$ (c)$\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})=2^n$

(d)$\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})=0$

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

Binomialkoeffizient

Binomialkoeffizient

$\mathrm{\forall }n,k\in \mathbb{N},k\le n:(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$

Äquivalente Definition (Merkregel): $(\genfrac{}{}{0ex}{}{n}{k})=\frac{\stackrel{k\text{Glieder}}{\overbrace{n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}}}{\underset{k\text{Glieder}}{\underbrace{1\cdot 2\cdots k}}}$ Spezialfall: $(\genfrac{}{}{0ex}{}{n}{0}):=1$

Lösungsvorschlag von vigrid

Beispiel (a)

$\begin{array}{cc}(\genfrac{}{}{0ex}{}{n}{k})& =(\genfrac{}{}{0ex}{}{n}{n-k})\\ \frac{n!}{k!\cdot (n-k)!}& =\frac{n!}{(n-k)!\cdot (n-(n-k))!}\\ \frac{n!}{(n-k)!\cdot k!}& =\frac{n!}{(n-k)!\cdot k!}\end{array}$

Beispiel (b)

$(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k+1})=(\genfrac{}{}{0ex}{}{n+1}{k+1})$

Beachte: $n!\cdot (n+1)=(n+1)!$

Es werden wieder die Binomialkoeffizienten aufgelöst:

$\begin{array}{cc}(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k+1})& =\frac{n!}{k!\cdot (n-k)!}+\frac{n!}{(k+1)!\cdot (n-k-1)!}\\ & =\frac{n!}{k!\cdot (n-k-1)!}\cdot \frac{1!}{n-k}+\frac{n!}{k!\cdot (n-k-1)!}\cdot \frac{1!}{k+1}\\ & =\frac{n!}{k!\cdot (n-k-1)!}\cdot (\frac{1}{n-k}+\frac{1}{k+1})\\ & =\frac{n!}{k!\cdot (n-k-1)!}\cdot \left(\frac{(k+1)+(n-k)}{(n-k)\cdot (k+1)}\right)\\ & =\frac{n!}{k!\cdot (n-k-1)!}\cdot \left(\frac{n+1}{(n-k)\cdot (k+1)}\right)\\ & =\frac{n!\cdot (n+1)}{k!\cdot (k+1)\cdot (n-k-1)!\cdot (n-k)}\\ & =\frac{(n+1)!}{(k+1)!\cdot (n-k)!}\\ & =\frac{(n+1)!}{(k+1)!\cdot ((n+1)-(k+1))!}\\ & =(\genfrac{}{}{0ex}{}{n+1}{k+1})\end{array}$

Dieses Beispiel befindet sich auch im Buch auf Seite 52.

Siehe auch WS13/Beispiel 153.

Beispiel (c)

$\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})=2^n$

Der Binomische Lehrsatz ist folgendermaßen definiert:

$\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{(n-k)}{y}^k=(x+y{)}^n$

Aus der rechten Seite ergibt sich: $2^n=(1+1{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})1^{(n-k)}{1}^k$

Da $1^x$ immer 1 ergibt, ist die Lösung äquivalent zur Angabe

Beispiel (d)

$\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})=0$

Lösung ähnlich wie (c):

$0=(1-1{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})1^{(n-k)}(-1{)}^k=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})$

---

habe zwei kleine fehler ausgebessert... (beispiel b: beim herausheben war eine multiplikation anstatt einer addition eingetragen bzw. gab es eine falsche "(n+1)! = n! * (n+1)" auflösung...

-Happy-