0 Daumen
82 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:

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$$

von 124 k 🚀
0 Daumen

Mache einen Induktionsbeweis.mit Induktion über n.

von 43 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