0 Daumen
237 Aufrufe

Aufgabe:

Zeigen sve, dass für \( n \in \mathbb{N} \) und \( k \in \mathbb{N}_{0} \) gite:

\(\displaystyle \left(\begin{array}{l} n+k \\ k+1 \end{array}\right)=\sum \limits_{l=1}^{n}\left(\begin{array}{c} n+k-l \\ k \end{array}\right) \)


Problem/Ansatz:

Avatar von

Muss es ein Induktionsbeweis sein? Oder käme auch ein kombinatorischer Beweis in Frage?

2 Antworten

+1 Daumen

Aloha :)

Willkommen in der Mathelounge... \o/

Wir beweisen die folgende Behauptung$$\binom{n+k}{k+1}=\sum\limits_{\ell=1}^n\binom{n+k-\ell}{k}\quad;\quad n\in\mathbb N\;;\;k\in\mathbb N_0$$durch vollständige Indukion über \(n\).

Verankerung bei \(n=1\):$$\binom{n+k}{k+1}=\binom{1+k}{k+1}=\binom{k+1}{k+1}=1$$$$\sum\limits_{\ell=1}^n\binom{n+k-\ell}{k}=\sum\limits_{\ell=1}^1\binom{1+k-\ell}{k}=\binom{1+k-1}{k}=1$$Beide Seiten der Gleichung liefern den Wert \(1.\quad\checkmark\)

Induktionsschritt von \(n\) auf \((n+1)\):$$\sum\limits_{\ell=1}^{\pink{n+1}}\binom{\pink{n+1}+k-\ell}{k}=\sum\limits_{\ell=1\green{-1}}^{\pink{n+1}-\green{1}}\binom{\pink{n+1}+k-(\ell\green{+1})}{k}=\sum\limits_{\ell=0}^n\binom{n+k-\ell}{k}$$$$\qquad=\binom{n+k-0}{k}+\sum\limits_{\ell=1}^n\binom{n+k-\ell}{k}\stackrel{\text{(Ind.Vor.)}}{=}\binom{n+k}{k}+\binom{n+k}{k+1}$$Im letzten Schitt verwende die sicherlich bekannte Identität \(\binom{N+1}{K}=\binom{N}{K}+\binom{N}{K-1}\) mit \(K=k+1\) und \(N=n+k\) verwendet:$$\qquad=\binom{\pink{n+1}+k}{k+1}\quad\checkmark$$

Avatar von 148 k 🚀
0 Daumen

Mache einen Induktionsbeweis.mit Induktion über n.

Avatar von 53 k 🚀

Hallo, ich habe es versucht aber ich weiß nicht genau, wie man die Gleichung bekommen kann. Im Anhang ist meine Prozess, kannst du mir dabei weiter helfen?

Vielen Dank im Voraus!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community