Vollständige Induktion: binomial(n+1,k+1) = sum binomial(m,k), m=k to n

Question

Seien \( n, k \in \mathbb{N} \) mit \( n \geq k . \) Beweisen Sie für festes \( k \) durch vollständige Induktion über \( n: \)
$$ \left(\begin{array}{l} {n+1} \\ {k+1} \end{array}\right)=\sum \limits_{m=k}^{n}\left(\begin{array}{c} {m} \\ {k} \end{array}\right) $$

(I.A.) Für n=1 und k=1 (da n>=k):

1=1    wahre Aussage

(I.S.) Hier liegt nun mein Problem. Ich komme zu folgendem Ansatz:

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

 Gleichheit ist hier Vorhanden, aber ich habe absolut keine Ahnung wie ich das zeigen soll.

Comments

Versuch mal die Darstellung von https://www.mathelounge.de/57843/binomischer-lehrsatz-vollstandige-induktion-summenformel

zu verstehen.

Da wird wohl die gleiche Formel bewiesen.

Answer 1

Im Prinzip musst du hier alles in Fakultäten umschreiben, auf einen Nenner bringen und vereinfachen.

( n+1 tief k+1) + (n+1 tief k)
= (n+1)! / ((k+1)! (n+1-(k+1))!  + (n+1)! /(k! *(n+1-k)!)
= (n+1)! / ((k+1)! (n-k)!  + (n+1)! /(k! *(n+1-k)!)

= ((n+1)! (n+1-k)) / ((k+1)! (n+1-k)!  + ((n+1)!(k+1) /((k+1)! *(n+1-k)!)

= ((n+1)! (n+1-k)) +  ((n+1)!(k+1)) /((k+1)! *(n+1-k)!)

= ((n+1)! (n+1-k+(k+1)) / ((k+1)!* (n+2-(k+1))!)

       |Anm: Violett nur etwas komplizierter geschrieben!

= ((n+1)! (n+2))/ ((k+1)!* (n+2-(k+1))!)

= (n+2)! / ((k+1)!* (n+2-(k+1))!)

= ( n+2 tief k+1) qed. Induktionsschritt.