Binomialkoeffizienten Gleichung beweisen, aber wie? (Selbststudium)

Question

Aufgabe:

Informieren Sie sich über den Binomialkoeffizienten und beweisen Sie, dass gilt:

$\left(\begin{array}{l} n+1 \\ k \end{array}\right)=\left(\begin{array}{l} n \\ k-1 \end{array}\right)+\left(\begin{array}{l} n \\ k \end{array}\right)$

Das ist die Aufgabe.

Problem/Ansatz:

Ich habe mir schon mehrere Videos zu Binomialkoeffizienten angesehen aber in keinem wurde gezeigt wie man so etwas oder Ähnliches beweist. Im Grunde habe ich verstanden was Binomialkoeffizienten sind aber weiß nicht wie man die Aufgabe beweisen soll. Hat jemand Tipps, Lösungsansätze oder Videovorschläge?

Comments

https://www.mathelounge.de/969543/gleichungen-mit-bin-koeffizienten#…

Answer 1

Aloha :)

Der Binomialkoeffizieten $\binom{n}{k}$ gibt die Anzahl der Möglichkeiten an, aus $n$ Objekten genau $k$ Objekte ohne Zurücklegen auszuwählen.

Jetzt geben wir zu den $n$ Objekten ein weiteres hinzu und wollen daraus genau $k$ Objekte auswählen. Wir wollen also wissen, was $\binom{n+1}{k}$ ist.

Dazu unterscheiden wir 2 Fälle:

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

2) Das neu hinzugegebene Objekt wird nicht ausgewählt, dann müssen aus den alten $n$ Objekten noch genau $k$ ausgewählt werden. Dafür gibt es $\binom{n}{k}$ Möglichkeiten.

Zusammengefasst heißt das:$$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$$

Comments

Dankeschön. Sehr verständlich erklärt, habe alles nachvollziehen können.

Aber inwiefern genügt diese Erklärung im Bezug auf die Aufgabenstellung?

Zählt solch eine schriftliche Erklärung als „Beweis“?

---

Einen besseren Beweis, als dass du alles direkt verstanden hast, kann ich mir eigentlich gar nicht vorstellen. Die Aufgabenstellung lautet ja auch nicht, dass du es "formal" beweisen sollst.

Der Beweis mit Formeln wäre z.B. so:$$\phantom=\binom{n}{k-1}+\binom{n}{k}$$$$=\frac{n!}{(k-1)!(\pink{n-(k-1)})!}+\frac{n!}{k!{(n-k)!}}$$$$=\frac{n!}{(k-1)!(\pink{(n+1)-k})!}+\frac{n!}{k!{(n-k)!}}$$$$=\frac{n!\cdot\green k}{\green k\cdot(k-1)!((n+1)-k)!}+\frac{n!\cdot\red{((n+1)-k)}}{k!{(n-k)!\cdot\red{((n+1)-k)}}}$$$$=\frac{n!\cdot k}{k!\cdot((n+1)-k)!}+\frac{n!\cdot(n+1)-n!\cdot k}{k!\cdot((n+1)-k)}$$$$=\frac{n!\cdot(n+1)}{k!\cdot((n+1)-k)}$$$$=\binom{n+1}{k}$$