Zeige die Rekursionsformel

Question

Aufgabe:

Text erkannt:

Für \( k, n \in \mathbb{N}_{0} \) mit \( k \leq n \) definieren wir die Fakultät \( n ! \) durch \( n !:=\prod \limits_{i=1}^{n} i \) und den Binomialkoeffizienten \( \left(\begin{array}{l}n \\ k\end{array}\right) \) durch \( \left(\begin{array}{l}n \\ k\end{array}\right):=\frac{n !}{k !(n-k) !} \).
(a) Zeige die Rekursionsformel \( \left(\begin{array}{c}n \\ k-1\end{array}\right)+\left(\begin{array}{c}n \\ k\end{array}\right)=\left(\begin{array}{c}n+1 \\ k\end{array}\right) \) für \( n \in \mathbb{N} \) und \( k \in\{1 \ldots n\} \).

Answer 1

Aloha :)

Du hast hier zwei Möglichkeiten. Bei der ersten, machst du dir klar, was der Binomialkeoffizient bedeuet. Bei der zweiten rechnest du einfach nur.

Möglichkeit 1

Wir haben \(n\) Objekte und wollen daraus genau \(k\) Objekte (ohne Zurücklegen) auswählen. Die Anzahl dieser Auswahlmöglichkeiten bezeichnen wir mit \(\binom{n}{k}\).$$\binom{n}{k}\coloneqq\text{Anzahl der Möglichkeiten, aus \(n\) Objekten genau \(k\) auszuwählen.}$$Diese Ausdrücke heißen "Binomialkoeffizienten", man liest sie als "n über k" oder auch "n aus k".

Randbedingungen:

1) Es gibt immer genau eine Möglichkeit, kein Objekt auszuwählen, wir erhalten dann die leere Menge, also ist \(\binom{n}{0}=1\)

2) Es gibt immer nur eine Möglichkeit, alle Objekte auszuwählen, also ist \(\binom{n}{n}=1\)

Zur Rekursionsgleichung:

Wie viele Möglichkeiten gibt es, aus \((n+1)\) Objekten genau \(k\) auszuwählen? Zur Beantwortung stellen wir uns vor, wir hätten \(n\) Objekte und würden dazu ein neues Objekt dazulegen. Dann gibt es 2 Möglichkeiten.

a) Das neue Objekt wird ausgewählt. Dann müssen aus den \(n\) alten Objekten noch genau \((k-1)\) ausgewählt werden. Dafür gibt es \(\binom{n}{k-1}\) Möglichkeiten.

b) Das neue Objekt wird nicht ausgewählt. Dann müssen aus den \(n\) alten Objekten genau \(k\) Objekte ausgewählt werden. Dafür gibt es \(\binom{n}{k}\) Möglichkeiten.

Das bedeutet mit Binomialkoeffizienten geschrieben:$$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$$

Möglichkeit 2

$$\binom{n}{k}+\binom{n}{k-1}=\frac{n!}{k!\cdot(n-k)!}+\frac{n!}{(k-1)!\cdot(n-(k-1))!}$$$$\qquad=\frac{n!}{k!\cdot(n-k)!}\cdot\frac{(n-k+1)}{(n-k+1)}+\frac{n!}{(k-1)!\cdot(n-k+1)!}\cdot\frac{k}{k}$$$$\qquad=\frac{n!\cdot(n-k+1)}{k!\cdot\underbrace{(n-k)!\cdot(n-k+1)}_{=(n-k+1)!}}+\frac{n!\cdot k}{\underbrace{(k-1)!\cdot k}_{=k!}\cdot(n-k+1)!}$$$$\qquad=\frac{n!\cdot n-n!\cdot k+n!}{k!\cdot(n-k+1)!}+\frac{n!\cdot k}{k!\cdot(n-k+1)!}=\frac{n!\cdot n\,\cancel{-n!\cdot k}+n!\,\cancel{+n!\cdot k}}{k!\cdot(n-k+1)!}$$$$\qquad=\frac{n!\cdot n+n!}{k!\cdot(n-k+1)!}=\frac{n!\cdot(n+1)}{k!\cdot(n+1-k)!}=\frac{(n+1)!}{k!\cdot((n+1)-k)!}=\binom{n+1}{k}\quad\checkmark$$

Answer 2

Zeige, dass \(\frac{n!(n-(k-1))!}{(k-1)!}+\frac{n!(n-k)!}{k!}=\frac{(n+1)!(n+1-k))!}{k!}\) gilt.

Dazu musst du nur die linke Seite entsprechend umformen.

(Ein erster Schritt wäre, den ersten Bruch mit k zu erweitern, damit der Nenner auch dort k! ist.)