Induktion über k mit Binomialkoeffizient

Question

Aufgabe:

Beweisen Sie für alle k ∈ ℕ:

$$\sum \limits_{i=0}^{k} \begin{pmatrix} k\\i \end{pmatrix}^2 =\begin{pmatrix} 2k\\k \end{pmatrix}$$

Problem/Ansatz:

Die IA und IV sind klar. Kann mir aber jemand vielleicht einen Tipp geben, wie man hier den Induktionsschritt machen würde?

Comments

Ist Induktionsbeweis ausdrücklich verlangt?

---

Tatsächlich nicht, nein. Aber "für alle ... aus ℕ" verstehe ich immer als Hinweis auf eine Induktion.

Answer 1

Die Vandermonde Identität gibt uns

\(\begin{aligned} \sum \limits_{k=0}^{r}\left(\begin{array}{c} m \\ k \end{array}\right)\left(\begin{array}{c} n \\ r-k \end{array}\right)=\left(\begin{array}{c} m+n \\ r \end{array}\right) .\end{aligned} \)
In deinem Fall setzen wir also \( m=n \) und \( r=n \), also
\(\begin{aligned} \sum \limits_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right)\left(\begin{array}{c} n \\ n-k \end{array}\right)=\sum \limits_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right)\left(\begin{array}{l} n \\ k \end{array}\right)=\left(\begin{array}{c} n+n \\ n \end{array}\right)=\left(\begin{array}{c} 2 n \\ n \end{array}\right) .\end{aligned} \)
Die Vandermonde Identität ist wohl eine der wichtigsten Identitäten für Binomialkoeffizienten und kann mittels Koeffizientenvergleich von \( (1+x)^{n}(1+x)^{m} \) und \( (1+x)^{n+m} \) hergeleitet werden, wobei man den Binomischen Lehrsatz anwendet.

Comments

Das macht Sinn, dann braucht man auch keine Induktion, da die Vandermonde Identität schon bewiesen wurde. :D Danke dir!

Answer 2

Aloha :)

Wieso willst du diese Aussage mit Induktion zeigen? Sie ist doch sofort klar...

Du möchtest aus \((2k)\) Objekten genau \(k\) auswählen. Dafür gibt es \(\binom{2k}{k}\) Möglichkeiten.

Lege die \((2k)\) Objekte in Form von zwei gleich großen Haufen zu je \(k\) Elementen vor dich hin. Wenn du aus dem ersten Haufen genau \(i\) Objekte auswählst, musst du aus dem zweiten Haufen noch genau \((k-i)\) Objekte auswählen. Dafür gibt es \(\binom{k}{i}\cdot\binom{k}{k-i}=\binom{k}{i}\cdot\binom{k}{i}=\binom{k}{i}^2\) Möglichkeiten. Da du in der Wahl von \(i\) frei bist, musst du alle diese Möglichkeiten von \(i=0\) bis \(i=k\) addieren:

$$\binom{2k}{k}=\sum\limits_{i=0}^k\binom{k}{i}\binom{k}{k-i}=\sum\limits_{i=0}^k\binom{k}{i}^2$$

Comments

Das hat mir sehr beim Verständnis geholfen, danke dir! :D