Summenformel mit Kombinatorik, beweisen

Question

folgende Aufgabe wird mir zum Verhängnis:

Zu Beweisen für alle n, k ∈ ℕ (also Induktion?)

\( \sum\limits_{i=0}^{n}{i} \) \( \begin{pmatrix} n \\ i \end{pmatrix} \) = n • 2^n-1

Das wäre eventuell mein Ansatz:

Der IA wenn man n=0 einsetzt stimmt.

Dann der IS \( \sum\limits_{i=0}^{n+1}{i \begin{pmatrix} n+1 \\ i\end{pmatrix}} \) = (n+1)2^(n+1)-1

Wie geht's weiter ? :/

Vielen Dank

Comments

Eine Methode ohne Induktion:
Leite die Funktion \(f(x):=(1+x)^n=\sum\limits_{k=0}^n\binom nkx^k\) nach x ab und setze anschließend x=1.

---

Das hilft mir leider nicht weiter. ^^

Answer 1

ist dir die Identität $$\binom{n}{k}+\binom{n+1}{k}=\binom{n+1}{k+1}$$ bekannt?

Um auf die Indukktionsvoraussetzung zurückgreifen zu können, aolltest du den Term

$$\binom{n+1}{i}$$ vielleicht  umschreiben in

$$\binom{n+1}{i}=\binom{n+1}{i+1}-\binom{n}{k}$$

Comments

Nein,

das verstehe ich leider eher weniger. :/

---

Der Titel der Frage legt nahe, nach einem kombinatorischen Beweis zu suchen.
(Ich hoffe, MC wird nicht wieder böse.)

Man stelle sich folgendes Szenario vor :
n Personen P_1 , ... , P_n legen Kugeln in eine Urne (das ist ja etwas ganz Neues, sonst werden die Kugeln immer aus der Urne gezogen) und zwar nach folgendem Prinzip : Zunächst treten die Personen einzeln an und legen eine Kugel ab, dann in allen möglichen Zweierkombinationen und legen jeder eine Kugel ab, dann in allen möglichen Dreiergruppen und legen jeder eine Kugel ab, dann ... bis sie schließlich alle zusammen antreten und wieder jeder eine Kugel in die Urne legt. Auf diese Weise ergibt sich die Summe auf der linken Seite der Gleichung als die Gesamtzahl der Kugeln in der Urne.

Diese Anzahl lässt sich nun aber auch anders bestimmen, nämlich indem wir abzählen, wieviele Kugeln P_1 beigesteuert hat : Bei jeder möglichen Auswahl aus den übrigen n-1 Personen ist P_1 einmal dabei gewesen. Es gibt insgesamt 2^{n-1} solcher Auswahlen, so viele Kugeln hat also P_1 abgelegt und da das für jede der n Personen gilt erhält man den Term auf der rechten Seite der zu beweisenden Gleichung.