Rekursionsformel (Binomialkoeffizient)

1. Satz

Sei \(r \in \mathbb{R}\) und \(r \in \mathbb{N}_0\), so gilt:

\begin{align*} \binom{r}{k} = \binom{r-1}{k-1} + \binom{r-1}{k} \end{align*}

2. Beweis

2.1. natürliche Zahlen

Sei \(r \in \mathbb{N}\), so betrachten wir die Anzahl der k-Elementigen Teilmengen. Dazu wählen heben wir ein Element \(a\) hervor: Dieses ist entweder in der Teilmenge, dann existieren \(\binom{r-1}{k-1}\) verschiedene Möglichkeiten oder nicht in der Teilmenge, dann existieren \(\binom{r}{k}\) verschiedene Möglichkeiten. Diese sind auch wegen \(a\) echt verschieden und damit folgt:

\begin{align*} \binom{r}{k} = \binom{r-1}{k-1} + \binom{r-1}{k} \end{align*}

2.2. reelle Zahlen

folgt aus der Betrachtung des Binomialkoeffizient als Polynom.