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

Man beweise nachstehende Identitäten für Binomialkoeffizienten:
(a) ${n \choose k}={n \choose n-k}$ (b) ${n \choose k}+{n \choose k+1}={n+1 \choose k+1}$ (c) $\sum _{k=0}^{n}{n \choose k}=2^{n}$
(d) $\sum _{k=0}^{n}(-1)^{k}{n \choose 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[Bearbeiten | Quelltext bearbeiten]

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 von vigrid[Bearbeiten | Quelltext bearbeiten]

Beispiel (a)[Bearbeiten | Quelltext bearbeiten]

${\begin{aligned}{n \choose k}&={n \choose 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{aligned}}$

Beispiel (b)[Bearbeiten | Quelltext bearbeiten]

${n \choose k}+{n \choose k+1}={n+1 \choose k+1}$

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

Es werden wieder die Binomialkoeffizienten aufgelöst:

$\begin{aligned} (\binom{n}{k}) + (\binom{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 (\frac{(k + 1) + (n - k)}{(n - k) \cdot (k + 1)}) \\ = \frac{n!}{k! \cdot (n - k - 1)!} \cdot (\frac{n + 1}{(n - k) \cdot (k + 1)}) \\ = \frac{n! \cdot (n + 1)}{k! \cdot (k + 1) \cdot (n - k - 1)! \cdot (n - k)} \\ = \end{aligned}$

Beispiel (c)[Bearbeiten | Quelltext bearbeiten]

\sum _{k=0}^{n}{n \choose k}=2^{n}

Der Binomische Lehrsatz ist folgendermaßen definiert:

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

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

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

Beispiel (d)[Bearbeiten | Quelltext bearbeiten]

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

Lösung ähnlich wie (c):

$0=(1-1)^{n}=\sum _{k=0}^{n}{n \choose k}1^{(n-k)}(-1)^{k}=\sum _{k=0}^{n}(-1)^{k}{n \choose 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-