Summe des Produkts der Binomialkoeffizienten: ∑nk=0(−1)k(nk)(n+kk)=(−1)n∑k=0n(−1)k(nk)(n+kk)=(− 1)n\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n

Wenn Sie die zu beweisende Gleichung schreiben als$\sum_k(-1)^{n-k}\binom nk\binom{n+k}n=1$, können Sie die linke Seite als Ergebnis der Anwendung von interpretieren$n$-te Finite-Differenzen-Operation$\Delta^n$zur Folge$k\mapsto\binom kn$, und den Term der resultierenden Sequenz bei nehmen$k=n$. Dann$\Delta(k\mapsto\binom km)=k\mapsto\binom k{m-1}$impliziert, dass die linke Seite wird$\Delta^n\left(k\mapsto\binom kn\right)(n)=\binom n{n-n}=\binom n0=1$wie gewünscht.

Ein anderer Ansatz besteht darin, die Negation des oberen Index im zweiten Binomialkoeffizienten zu erkennen:

$$(-1)^k\binom{n+k}k=\binom{k-(n+k)-1}k=\binom{-n-1}k,$$ Danach wird die Identität zum Beispiel die Vandermonde-Identität $$\sum_{k=0}^n(-1)^k\binom nk\binom{n + k}k= \sum_k\binom n{n-k}\binom{-n-1}k=\binom{-1}n=(-1)^n.$$

${}$

Nach Anfrage im Kommentar hinzugefügt. Keines dieser Argumente erfordert viel mehr als grundlegende Kenntnisse über Binomialkoeffizienten. Der Differenzoperator$\Delta$ist definiert durch$\Delta(f)(k)=f(k+1)-f(k)$, also mit$f:k\mapsto\binom km$man bekommt

$$\Delta(f)(k)=\binom{k+1}m-\binom km=\binom k{m-1}$$

nur von Pascals Wiederholung. Und die Formel

$$\Delta^n(f)(n)=\sum_i(-1)^{n-i}\binom nif(n+i)$$ entweder folgt leicht durch Induktion aus der Definition von $\Delta$, oder wenn Sie es vorziehen, indem Sie die Identität des Operators verwenden $I$und verschieben $S$auf Funktionen, definiert durch $I(f)=f$Und $S(f)(i)=f(i+1)$, Schreiben $\Delta=S-I$, und unter Verwendung der Binomialformel für $(S-I)^n$(möglich seit $S$Und $I$pendeln).

Bei der zweiten Variante kennst du die Formel wahrscheinlich schon$\binom{-n}k= (-1)^k\binom{n+k-1}k$für Binomialkoeffizienten mit negativem oberen Index, oder aber die Gleichheit der äußeren Ausdrücke in

$$(1+X)^{-n} = \sum_{k\in\mathbf N} \binom{-n}kX^k = \sum_{k\in\mathbf N}(-1)^k\binom{n+k-1}kX^k$$ (Wenn nicht, siehe diese Antwort , die die erste Formel ableitet). Dann $\sum_k(-1)^k\binom{n+k}kX^k=(1+X)^{-n-1}$, und die Instanz der Vandermonde-Identität wird durch den Vergleich der Koeffizienten in bewiesen $$\sum_n\left(\sum_{k=0}^n(-1)^k\tbinom{n + k}k\tbinom nk\right)X^n =(1+X)^{-n-1}(1+X)^n=(1+X)^{-1}=\sum_n(-1)^nX^n$$ Dies könnte der Beweis sein, der nur die Manipulation von verwendet $(1+X)^{n-1}$du hast gefragt.

Angenommen, wir versuchen zu bewerten

$$\sum_{k=0}^n (-1)^k {n\choose k} {n+k\choose k}.$$

Beginne am

$${n+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^{n+k} \; dz.$$

Dies ergibt den folgenden Ausdruck für die Summe

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{k=0}^n {n\choose k} \frac{(-1)^k}{z^{k+1}} (1+z)^{n+k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \sum_{k=0}^n {n\choose k} (-1)^k \frac{(1+z)^k}{z^k}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \left(1-\frac{z+1}{z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \frac{(-1)^n}{z^n} \; dz \\ = \frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}}\; dz.$$

Daraus folgt, dass die geschlossene Form der Summe gegeben ist durch

$$(-1)^n [z^n] (1+z)^n = (-1)^n.$$

Eine Spur, wann diese Methode auf MSE erschienen ist und von wem, beginnt unter diesem MSE-Link .

Der folgende kombinatorische Beweis kann ebenfalls von Interesse sein. Nach dem Multiplizieren beider Seiten mit$(-1)^n$, und Neuindizieren der Summierung durch Ersetzen$k$mit$n-k$, können wir die zu beweisende Gleichung umschreiben als

$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{2n-k}n=1$$ Beide Seiten beantworten folgende Frage:

Wie viele Saiten von$n$Einsen und$n$Nullen gibt es, wo auf keine Null unmittelbar eine Eins folgt?

Offensichtlich gibt es nur eine solche Zeichenfolge,$11\cdots100\cdots0$.

Andererseits können wir dies nach dem Inklusions-Exklusions-Prinzip zählen. Nehmen Sie alle$\binom{2n}n$Saiten von$n$Nullen und$n$diejenigen, und für jeden$i=1,2,\dots,n$, subtrahieren Sie die Zeichenfolgen, in denen die$i^{th}$Auf die Null folgt eine Eins. Jede solche Zeichenkette kann erzeugt werden, indem eine beliebige Zeichenkette von genommen wird$n$Nullen und nur$n-1$Einsen und fügt dann eine Eins nach dem hinzu$i^{th}$null. Daher für jeden$i=1,\dots,n$, müssen wir subtrahieren$\binom{2n-1}n$, also subtrahieren$n\binom{2n-1}n$.

Zeichenfolgen mit zwei Instanzen einer Null gefolgt von einer Eins wurden jedoch doppelt subtrahiert, sodass diese wieder hinzugefügt werden müssen. Mit einer ähnlichen Methode werden die Zahlenzeichenfolgen, bei denen beide die$i^{th}$Null und die$j^{th}$Nullen folgen Einsen ist$\binom{2n-2}n$. Wir müssen dies für jeden der hinzufügen$\binom{n}2$Nullenpaare, also fügen Sie hinzu$\binom{n}2\binom{2n-2}n$.

Wenn wir auf diese Weise fortfahren (Subtrahieren der dreifach subtrahierten Zeichenfolgen, Hinzufügen der vierfach subtrahierten Zeichenfolgen usw.), erhalten wir die alternierende Summe auf der linken Seite.

Nur um eine direkte Methode zu sehen:

$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k}= \sum_{k=0}^{n}\binom{n}{n-k}\binom{-n-1 }{k}$$ $$=\binom{-1 }{n}=\left(-1\right)^{n}\binom{n}{n}=\left(-1\right)^{n}$$