Kombinatorik (Binomialkoeffizient) (Pascal`s & Vandermonde Identität)

Question

Aufgabe:

1. Seien \( n, k \in \mathbb{N} \). Zeigen Sie, dass

$$ \left(\begin{array}{c} n+1 \\ k \end{array}\right)=\left(\begin{array}{c} n \\ k-1 \end{array}\right)+\left(\begin{array}{l} n \\ k \end{array}\right) $$
2. Seien \( m, n, r \in \mathbb{N}, \) wobei \( r \leq m \) und \( r \leq n . \) Zeigen Sie, dass
$$ \left(\begin{array}{c} m+n \\ r \end{array}\right)=\sum \limits_{k=0}^{r}\left(\begin{array}{c} m \\ r-k \end{array}\right) \cdot\left(\begin{array}{l} n \\ k \end{array}\right) $$

Answer 1

Definition war ja vermutlich

$$\begin{pmatrix} n\\k \end{pmatrix}=\frac{n!}{k!*(n-k)!}$$

also ist

$$\begin{pmatrix} n+1\\k \end{pmatrix}=\frac{(n+1)!}{k!*(n+1-k)!}$$

und

$$\begin{pmatrix} n\\k-1 \end{pmatrix}=\frac{n!}{(k-1)!*(n-k+1)!}$$

und die rechte Seite ist

$$\begin{pmatrix} n\\k-1 \end{pmatrix}+\begin{pmatrix} n\\k \end{pmatrix}=\frac{n!}{(k-1)!*(n-k+1)!}+\frac{n!}{k!*(n-k)!}$$

gleiche Nenner herstellen:

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

auf einen Bruchstrich

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

also das gleiche Ergebnis wie die linke Seite.

Comments

Dankerschön. Und was ist mit Aufgabe 2?