Zeigen Sie mit Hilfe vollständiger Induktion, dass…

Question

Aufgabe:

(a) Zeigen Sie mithilfe vollständiger Induktion, dass für alle \( n \in \mathbb{N}_{0} \) gilt

\( \sum \limits_{k=0}^{n} k\left(\begin{array}{l} n \\ k \end{array}\right)=n 2^{n-1} \)

(b) Beweisen Sie die Identität (1) kombinatorisch mithilfe doppelten Abzählens. Tipp: Betrachten Sie die Menge \( M=\{(a, A): a \in A, A \subseteq N\} \), wobei \( N \) eine Menge mit \( n \) Elementen ist, und zählen Sie die Menge \( M \) zuerst nach \( a \) und dann \( A \mathrm{ab} \).

Problem/Ansatz:

…  Den Anfang hab ich.. komme bei dem zu zeigen von: (n+1) • 2^n nicht weiter

b) verstehe ich gar nicht

Answer 1

Zum Induktionsschluss verwenden wir die Rekursionsformel für Binomialkoeffizienten (Pascal-Dreieck). Dafür müssen wir einen Summanden separat betrachten:

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

Der erste Summen-Term entspricht der Induktionsvoraussetzung, den zweiten ziehen wir auseinander:

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

$$=n+1+n2^{n-1}+\sum_{k=0}^{n-1}k{n\choose k}+\sum_{k=0}^{n-1}{n\choose k}$$

Die erste Summe entspricht der Induktionsvoraussetzung - bis auf den letzten Summand. Die zweite Summe ist \((1+1)^n\) - bis auf den letzten Summand:

$$...=n+1+n2^{n-1}+n2^{n-1}-n+2^n-1=(n+1)2^n$$