Kombinatorische Gleichung per Induktion beweisen

Question

Aufgabe:

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

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

Ich möchte die Gleichung per Induktion lösen, jedoch weiss ich nicht, wie ich beim Induktionsschritt vorgehen soll. Alternative Lösungsvorschläge (ohne Induktion) sind auch willkommen.

Answer 1

Aloha :)

Ich empfehle, zunächst die Summe wie folgt umzuformen:

$$S_n:=\sum\limits_{l=1}^n\binom{n+k-l}{k}=\sum\limits_{l=1}^n\binom{k+(n-l)}{k}=\sum\limits_{i=0}^{n-1}\binom{k+i}{k}$$$$\phantom{S_n}=\sum\limits_{i=0}^{n-1}\binom{k+i}{(k+i)-k}=\sum\limits_{i=0}^{n-1}\binom{k+i}{i}$$Da \(l\) von \(1\) bis \(n\) läuft, läuft \((n-l)\) von \((n-1)\) runter bis auf \(0\). Durch Einführung der Lauffavirablen \(i\) werden die Summanden in der Summe zwar von rechts nach links geschrieben, aber der Wert der Summe bleibt ungeändert. Nach dieser Umformung geht die Induktion recht schnell.

Verankerung bei \(n=1\):

$$S_n=\sum\limits_{i=0}^{n-1}\binom{k+i}{i}=\sum\limits_{i=0}^{1-1}\binom{k+i}{i}=1=\binom{1+k}{k+1}=\binom{n+k}{k+1}\quad\checkmark$$

Induktionsschritt \(n\to n+1\):

$$S_{n+1}=\sum\limits_{i=0}^{(n+1)-1}\binom{k+i}{i}=\sum\limits_{i=0}^{n}\binom{k+i}{i}=\binom{k+n}{n}+\sum\limits_{i=0}^{n-1}\binom{k+i}{i}$$$$\phantom{S_{n+1}}\stackrel{I.V.}{=}\binom{k+n}{(k+n)-n}+\binom{n+k}{k+1}=\binom{n+k}{k}+\binom{n+k}{k+1}=\binom{n+1+k}{k+1}$$

Answer 2

Zunächst einmal kannst du dir an ein paar Beispielen am Pascalschen Dreieck klar machen, wie die Gleichung funktioniert: Wenn man bei einer 1 am rechten Rand startet, dann diagonal nach links unten wandert und die Koeffiizenten addiert und irgendwann stoppt, ist die Summe immer genau so groß wie die Zahl, die in der nächsten Zeile rechts neben der Zahl steht, die der nächste Summand gewesen wäre. Das liegt am Aufbau des Dreiecks, und grundlegend hierfür ist die Gleichung $$ \begin{pmatrix} m+1\\k+1 \end{pmatrix}=\begin{pmatrix} m\\k \end{pmatrix}+\begin{pmatrix} m\\k+1 \end{pmatrix}\text{ für } m\in \mathbb{N}, k \in \mathbb {N}_{0} $$ Diese kannst du vermutlich voraussetzen, aber man kann sie auch direkt mit der Definition über Fakultäten und etwas Bruchrechnung nachweisen. Die zu beweisende Gleichung kann man per Induktion nach n nachweisen. Der Anfang ist wie fast immer einfach. Im Induktionsschritt kannst du dann zunächst die obige Gleichung für m = n+k anwenden. Dann kannst du auf den zweiten Term der rechten Seite die IV anwenden. Durch Indexverschiebung erhältst du eine Summe für l = 2 bis n+1 und bei den Binomialkoeffizienten in der Summe auch n+1 statt n. Und dann passt auch genau der erste Term, der ist dann nämlich der fehlende Summand für l = 1 in der Summe.