Beweisen Sie die folgende Aussage mit Hilfe vollständiger Induktion:

Der ist zugegebenermaßen etwas tricky. Ich zeige dazu zunächst zwei kleine Zwischenergebnisse vorneweg, die du eventuell schon kennst. Dann musst du sie natürlich nicht nochmal zeigen.

 

Zum einen brauchen wir folgende Aussage (1): \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\)

Wir rechnen das mit Hilfe der Bruch-Definition der Binomialkoeffizienten nach:

\(\binom{n+1}{k} = \\ \frac{(n+1)!}{(n+1-k)!\cdot k!} = \\ \frac{(n+1)\cdot n!}{(n+1-k)!\cdot k!} = \\ \frac{(n+1-k+k)\cdot n!}{(n+1-k)!\cdot k!} = \\ \frac{(n+1-k)\cdot n!}{(n+1-k)!\cdot k!} + \frac{k \cdot n!}{(n+1-k)!\cdot k!} = \\ \frac{n!}{(n-k)! \cdot k!} + \frac{n!}{(n-(k-1))!\cdot (k-1)!} = \\ \binom{n}{k} + \binom{n}{k-1} \)

 

Ok, so weit, so gut. Jetzt gibt's noch das zweite Vor-Resultat: (2): \(\sum_{k=0}^n \binom{n}{k} = 2^n\)

Das zeigen wir per Induktion. Für n=0 passt's auf jeden Fall, nun sei die Aussage wahr für ein n.

\(\sum_{k=0}^{n+1} \binom{n+1}{k} = \\ \sum_{k=1}^{n} \binom{n+1}{k} +1+1 = \\ \sum_{k=1}^{n}( \binom{n}{k}+\binom{n}{k-1}) +1+1 = \\ \sum_{k=1}^{n} \binom{n}{k}+\sum_{k=1}^{n}\binom{n}{k-1} +1+1 =^* \\ \sum_{k=1}^{n} \binom{n}{k}+\sum_{k=0}^{n-1}\binom{n}{k} +1+1 = \\ \sum_{k=0}^{n} \binom{n}{k}+\sum_{k=0}^{n}\binom{n}{k} = \\ 2^n+2^n = 2^{n+1}\)

 

Im letzten Schritt habe ich zweimal die Induktionsvoraussetzung genutzt, bei * wird ein Index-Shift in der zweiten Summe vollzogen. 

 

Mit (1) und (2) können wir nun die eigentliche Aussage zeigen. Der Induktionsanfang klappt hier wie gewohnt (Für n=1 sind beide Seiten der Gleichung 1.). Die Aussage sei wahr für ein n. Es ist wieder ein Index-Shift nötig, den entsprechenden Schritt kennzeichne ich wieder mit einem *.

 

\(\sum_{k=1}^{n+1} k \cdot \binom{n+1}{k} = \\ \sum_{k=1}^n k \cdot \binom{n+1}{k} +n+1 =^{(1)}\\ \sum_{k=1}^n k \cdot ( \binom{n}{k} + \binom{n}{k-1}) +n+1 =\\ \sum_{k=1}^n k \cdot \binom{n}{k} +\sum_{k=1}^n k \cdot \binom{n}{k-1} +n+1 =^* \\ \sum_{k=1}^n k \cdot \binom{n}{k} +\sum_{k=0}^{n-1} (k+1) \cdot \binom{n}{k} +n+1 = \\ \sum_{k=1}^n k \cdot \binom{n}{k} +\sum_{k=0}^{n-1} k \cdot \binom{n}{k} +\sum_{k=0}^{n-1} \binom{n}{k} +n+1 =^{**} \\ \sum_{k=1}^n k \cdot \binom{n}{k} +\sum_{k=1}^{n} k \cdot \binom{n}{k} +\sum_{k=0}^{n} \binom{n}{k} =^{IV, (2)} \\ n \cdot 2^{n-1} + n \cdot 2^{n-1} + 2^n = \\ n \cdot 2^n + 2^n = \\ (n+1) \cdot 2^n\)

 

Bei ** zieh' ich das n in die zweite Summe, als n-ten Summanden, und starte die zweite Summe bei 1, weil der Summand mit k=0 eh gleich 0 ist. Die einzelne 1 wandert in die dritte Summe, als n-ter Summand.

 

Damit sind wir fertig und haben dafür (1), (2) und die Induktionsvoraussetzung gebraucht. Frag' gern nach wenn noch irgendwas unklar ist! :)