Summe von m=k bis n (m über k) = (n+1 über k+1)

Question

Aufgabe:

Wir sollen A(n,k) mit vollständiger Induktion beweisen. n,k ∈ N, wobei 0 <= k <= n

n
∑    (m über k) = ( n+1 über k+1)
m=k

Problem/Ansatz:

IA:  Ist der Satz für n = k = 1 beweisen, da kommt 1=1 raus(schreibe das jetzt nicht ausführlich hin)

IH: Wenn A(n,k) => A(n+1,k)

IS: durch das internet komme ich auf (n+2 über k+1) = (n+1 über k+1) + (n+1 über k), ich verstehe nicht wieso man auf den letzten teil der formel kommt, nämlich (n+1 über k)? könnt ihr mir erklären, wie das hergeleitet wird?

Die Umformung am Ende, auf die Komme ich, aber irgendwie komme ich schon alleine beim Beweisen der Gleichheit der normalen Formel zu einem Fehler, z.B. für

n = 3 , k=1

(3+1 über 1+1) für zu (4 über 2) = 6 und Summe von m=k bis n (m über k) ergibt 3, da m und k immer gleichgroß sind ergibt das hier n*1 und n ist 3 somit kommt als summe 3 raus, und 6 ungleich 3, wieso?

Answer 1

Aloha :)

Erstmal zu dem sehr wichtigen, weil oft benötigten, Zusammenhang ("Du schreibst den Binomialkoeffizienten 3-mal hin, mit \(=\) und \(+\) dazwischen, subtrahierst rechts unten eine 1 und addierst diese links oben."):$$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$Der Binomialkoeffizient \(\binom{n}{k}\) gibt an, wie viele Möglichkeiten es gibt, aus einer n-elementigen Menge genau k Elemente auszuwählen. Gebe ich zu einer n-elementigen Menge 1 neues Element hinzu und möchte k Elemente auswählen -- suche also \(\binom{n+1}{k}\) -- können folgende Fälle auftreten:

a) das neue Element wird nicht ausgewählt, dann muss ich aus den alten n Elementen genau k auswählen. Dafür gibt es \(\binom{n}{k}\) Möglichkeiten.

b) das neue Element wird ausgewählt, dann muss ich aus den alten n Elementen noch genau (k-1) auswählen. Dafür gibt es \(\binom{n}{k-1}\) Möglichkeiten.

In Summe ist das genau der oben genannte Zusammenhang.\(\;\;\checkmark\)

Formal kann man diesen Zusammenhang wie folgt zeigen:$$\binom{n}{k}+\binom{n}{k-1}=\frac{n!}{k!\cdot(n-k)!}+\frac{n!}{(k-1)!\cdot(n-(k-1))!}$$$$=\frac{n!}{k!\cdot(n-k)!}+\frac{n!}{(k-1)!\cdot(n-k+1)!}$$$$=\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)!}$$$$=\frac{n!\cdot(n-k+1)}{k!\cdot(n-k+1)!}+\frac{n!\cdot k}{k!\cdot(n-k+1)!}=\frac{n!\cdot n-n!\cdot k+n!+n!\cdot k}{k!\cdot(n-k+1)!}$$$$=\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}\;\;\checkmark$$

Hier benötigst du diese Formel, nur sind n und k beide um 1 größer:$$\binom{n+2}{k+1}=\binom{n+1}{k+1}+\binom{n+1}{k}$$Damit zeigen wir nun mittels vollständiger Induktion die

Behauptung:\(\quad\sum\limits_{m=k}^n\binom{m}{k}=\binom{n+1}{k+1}\quad;\quad 0\le k\le n\)

Verankerung bei \(n=0\):

Wegen \(0\le k\le n\) und \(n=0\) muss \(k=0\) sein und es gilt:$$\sum\limits_{m=k}^n\binom{m}{k}=\sum\limits_{m=0}^0\binom{m}{0}=\binom{m}{0}=1=\binom{0+1}{0+1}=\binom{n+1}{k+1}\;\;\checkmark$$Induktionsschritt \(n\to n+1\):

$$\sum\limits_{m=k}^{n+1}\binom{m}{k}=\sum\limits_{m=k}^n\binom{m}{k}+\binom{n+1}{k}=\binom{n+1}{k+1}+\binom{n+1}{k}=\binom{n+2}{k+1}$$$$\phantom{\sum\limits_{m=k}^{n+1}\binom{m}{k}}=\binom{(n+1)+1}{k+1}\;\;\checkmark$$

Comments

Durch deine Erklärung im Zusammenhang mit der kompletten Formel, die ich gestern selbstständig erst komplett verstanden habe, habe die gesamte Aufgabe verstanden. Vielen Dank! :)