Liebe Community,

beim Lösen eines Matherätsels (Link) aus der Wahrscheinlichkeitsrechnung bin ich auf die folgende Identität gestoßen:

\( \sum_{i=0}^{n} \sum_{j=i}^{n} { {n+1} \choose i} {n \choose j} = 2^{2n} \)

Der linke Term ergibt sich aus meinem Lösungsansatz und führt über dessen Auswertung (mit gegebenem $n$) auch auf das korrekte Ergebnis des Rätsels. Mit dessen Wissen lässt sich dann anschließend auch auf den rechten Term schließen.

Nun wäre ich am Beweis dieser Identität interessiert. Leider führten all meine bisherigen Versuche ins Leere.
Gibt es hier vielleicht jemanden, der mir hierbei helfen kann und möchte?

LG Roman

EDIT:
Habe es jetzt doch noch selbst hinbekommen. Vom rechten Term aus kann man sich mit Hilfe des Binomischen Lehrsatzes $(1+1)^n=\sum_{k=0}^n {n \choose k} = 2^n$ vorab überlegen, wo man letztlich gerne ankommen möchte:

\( 2^{2n} = 2^n \cdot 2^n = \sum_{i=0}^{n} {n \choose i} \cdot \sum_{j=0}^{n} {n \choose j} = \sum_{i=0}^{n} \sum_{j=0}^{n} {n \choose i} {n \choose j} \)

Nun vom linken Term aus beginnend trennt man die Teilsumme für $i=0$ vom Rest, auf welchen man die Pascalsche Formel ${{n+1}\choose k} = {n \choose k}+{n \choose {k-1}}$ anwenden kann:

\( \sum_{i=0}^{n} \sum_{j=i}^{n} { {n+1} \choose i} {n \choose j} = \sum_{j=0}^n {{n+1} \choose 0} {n \choose j} +  \sum_{i=1}^{n} \sum_{j=i}^{n} [ { n \choose i} + {n \choose {i-1}} ] {n \choose j} \)

Hier nutzt man ${{n+1} \choose 0}=1={n \choose 0} $ und multipliziert des Weiteren die Klammer aus:

\( = \sum_{j=0}^n {n \choose 0} {n \choose j} +  \sum_{i=1}^{n} \sum_{j=i}^{n} { n \choose i}{n \choose j} + \sum_{i=1}^{n} \sum_{j=i}^{n} {n \choose {i-1}}{n \choose j}  \)

Die ersten beiden Terme lassen sich so zu einer Doppelsumme zusammenziehen, der dritte wird über Anpassung der Start- und Endwerte äquivalent umgeschrieben:

\( = \sum_{i=0}^{n} \sum_{j=i}^{n} { n \choose i}{n \choose j} + \sum_{i=0}^{n-1} \sum_{j=i+1}^{n} {n \choose i}{n \choose j}  \)

Aufgrund der nun vorhandenen Symmetrie in der zweiten Doppelsumme lassen sich deren Laufvariablen zuerst äquivalent vertauschen sowie deren Start- und Endwerte dann ein weiteres Mal äquivalent umschreiben. Letzteres lässt sich gut erkennen, wenn man die Doppelsumme z.B. tabellarisch anschreibt.

\( = \sum_{i=0}^{n} \sum_{j=i}^{n} { n \choose i}{n \choose j} + \sum_{j=0}^{n-1} \sum_{i=j+1}^{n} {n \choose i}{n \choose j} = \sum_{i=0}^{n} \sum_{j=i}^{n} { n \choose i}{n \choose j} + \sum_{i=1}^{n} \sum_{j=0}^{i-1} {n \choose i}{n \choose j} \)

Beide Terme lassen sich so nun zur vorab überlegten Doppelsumme exakt zusammenziehen und führen damit wie bereits gezeigt auf den gewünschten Potenzterm (siehe oben):

\( = \sum_{i=0}^{n} \sum_{j=0}^{n} {n \choose i} {n \choose j} = \cdots = 2^{2n} \)