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

Aus VoWi
Zur Navigation springen Zur Suche springen

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

Hilfreiches[Bearbeiten]

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

Beispiel (a)[Bearbeiten]


\begin{align}
{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{align}

Beispiel (b)[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{align}
{n \choose k} + {n \choose 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 \left( \frac{1}{n-k}+\frac{1}{k+1} \right) \\
 & = \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))!} \\
 & = {n+1 \choose k+1}
\end{align}

Dieses Beispiel befindet sich auch im Buch auf Seite 52.

Siehe auch WS13/Beispiel 153.

Beispiel (c)[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]

\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-