Aufgabe 9

Seien $n,\, k$ natürliche Zahlen mit $n \ge k$ . Man beweise

${{n+1} \choose {k+1}} = \sum\limits_{m=k}^n {m \choose k}$ .

1

Hinterlasse einen Kommentar

Webmaster

Leona

Wir beweisen die Aussage mittels vollständiger Induktion.

IA: $n=k$ Dann gilt $\binom{k+1}{k+1}=1=\binom{k}{k}=\sum_{m=k}^k \binom{m}{k}$ . Also stimmt der Induktionsanfang.

IV: Die Aussage $\binom{n+1}{k+1}=\sum_{m=k}^n \binom{m}{k}$ sei für ein beliebiges aber festes $n\geq k$ bewiesen.

IS: $n\mapsto n+1$ Wir wollen zeigen, dass gilt $\binom{n+2}{k+1}=\sum_{m=k}^{n+1}\binom{m}{k}$ .
Wir betrachten

$\begin{align*} \sum_{m=k}^{n+1}\binom{m}{k}&=\binom{n+1}{k}+\sum_{m=k}^{n}\binom{m}{k}\\ &\overset{\text{IV}}{=} \binom{n+1}{k} +\binom{n+1}{k+1}\\ &\overset{\text{Formel}}{=}\binom{n+2}{k+1}. \end{align*}$

Unter der Voraussetzung, dass die Formel

$\begin{align*} \binom{n+1}{k+1}+\binom{n+1}{k}=\binom{n+2}{k+1} \end{align*}$

gilt, haben wir also die Behauptung bewiesen.

Wir beweisen zum Abschluss die Formel:

$\begin{align*} \binom{n+1}{k+1}+\binom{n+1}{k}&\overset{\text{Def}}{=}\frac {(n+1)!}{(k+1)!(n-k)!}+\frac{(n+1)!}{k!(n+1-k)!}\\ &=\frac {(n+1)!(n+1-k)}{(k+1)!(n+1-k)!}+\frac{(n+1)!(k+1)}{(k+1)!(n+1-k)!}\\ &=\frac {(n+1)!((n+1-k)+(k+1))}{(k+1)!(n+1-k)!}\\ &=\frac {(n+1)!(n+2)}{(k+1)!(n+1-k)!}\\ &=\frac {(n+2)!}{(k+1)!(n+1-k)!}\\ &=\frac {(n+2)!}{(k+1)!(n+2-(k+1))!}\\ &\overset{\text{Def}}{=}\binom{n+2}{k+1}. \end{align*}$

1 Hinterlasse einen Kommentar

1

Hinterlasse einen Kommentar