vollständige Induktion mit binominalkoeffizient

Question

Aufgabe:

Zeigen Sie durch vollständige Induktion, dass ∀n ∈ ℕ die folgende Aussage gilt:

\( \sum\limits_{k=1}^{n}{k\begin{pmatrix} n\\k\\ \end{pmatrix}} \) = n · 2^n-1

Hinweis: Nutzen Sie, dass ∀k,n ∈ ℕ gilt:

\( \sum\limits_{i=0}^{n}{\begin{pmatrix} n\\i\\ \end{pmatrix}} \) = 2ⁿ und  \( \begin{pmatrix} n+1\\k+1\\ \end{pmatrix} \) = \( \begin{pmatrix} n\\k\\ \end{pmatrix} \) + \( \begin{pmatrix} n\\k+1\\ \end{pmatrix} \)

Problem/Ansatz:

Wie eine vollständige Induktion funktioniert weiß ich. Die Aussage stimmt auch für n=1, das habe ich schon geprüft.

Leider weiß ich nichts mit den Hinweisen anzufangen und ich hoffe es kann mir einer von euch helfen.

Answer 1

 \( \sum\limits_{k=1}^{n}{k\begin{pmatrix} n\\k\\ \end{pmatrix}} = n*2^{ n-1} \)

Dann gilt

 \( \sum\limits_{k=1}^{n+1}{k\begin{pmatrix} n+1\\k\\ \end{pmatrix}}  \)

Der letzte Summand ist n+1 also

 \(= \sum\limits_{k=1}^{n}{k\begin{pmatrix} n+1\\k\\ \end{pmatrix}}     + n+1 \)

Index verschieben

 \( =\sum\limits_{k=0}^{n-1}  {(k+1)  \begin{pmatrix} n+1\\k+1\\ \end{pmatrix}}  +n+1\)

2.Hinweis verwenden:

 \( =\sum\limits_{k=0}^{n-1}  {(k+1) ( \begin{pmatrix} n\\k\\ \end{pmatrix}+  \begin{pmatrix} n\\k+1\\ \end{pmatrix}} ) +n+1\)

in 2 Summen aufteilen

$$ =\sum\limits_{k=0}^{n-1}  {(k+1)  \begin{pmatrix} n\\k\\ \end{pmatrix}} +\sum\limits_{k=0}^{n-1}  {(k+1)\begin{pmatrix} n\\k+1\\ \end{pmatrix}} +n+1$$

(k+1) in der 1. Summe auflösen und nochmal auf 2 aufteilen

$$ =\sum\limits_{k=0}^{n-1}  {k  \begin{pmatrix} n\\k\\ \end{pmatrix}}+\sum\limits_{k=0}^{n-1}  {  \begin{pmatrix} n\\k\\ \end{pmatrix}}  +\sum\limits_{k=0}^{n-1}  {(k+1)\begin{pmatrix} n\\k+1\\ \end{pmatrix}} +n+1$$

Das n+1 am Schluß verteilen wir:

In der ersten Summe nehmen wir das n als den Summand für k=n und bei der 2. die 1. Dann

$$ =\sum\limits_{k=0}^{n}  {k  \begin{pmatrix} n\\k\\ \end{pmatrix}}+\sum\limits_{k=0}^{n}  {  \begin{pmatrix} n\\k\\ \end{pmatrix}}  +\sum\limits_{k=0}^{n-1}  {(k+1)\begin{pmatrix} n\\k+1\\ \end{pmatrix}} $$

Der 1. Summand der 1. Summe ist 0, und in der  3. Summe Index verschieben also

$$ =\sum\limits_{k=1}^{n}  {k  \begin{pmatrix} n\\k\\ \end{pmatrix}}+\sum\limits_{k=0}^{n}  {  \begin{pmatrix} n\\k\\ \end{pmatrix}}  +\sum\limits_{k=1}^{n}  {k\begin{pmatrix} n\\k\\ \end{pmatrix}} $$

Auf die erste und die dritte die Ind.vor. anwenden und auf die zweite den 1. Hinweis

= n*2^(n-1) + 2^n + n*2^(n-1)

= (n+1) * 2^n     q.e.d.

Comments

\( \sum\limits_{k=1}^{n+1}{k\begin{pmatrix} n+1\\k\\ \end{pmatrix}} \)
Der letzte Summand ist n+1 also
\( \sum\limits_{k=1}^{n+1}{k\begin{pmatrix} n+1\\k\\ \end{pmatrix}} \) + n + 1

kannst du mir das oben genannte vielleicht noch ein bisschen genauer erklären? Ich weiß nicht warum ich diesen Schritt machen darf.

und vielen Dank für deine Hilfe, damit habe ich nicht gerechnet.

---

Da hast du nicht ganz sorgfältig gelesen:

Die erste Summe geht bis n+1

aber die zweite nur bis n

(Habe ich gemacht, Weil ja die Ind. vor. nur bis n gilt)

deshalb habe ich den letzten Summanden

von der Summer abgetrennt, und später bei den

anderen Summen, wo er gebraucht wurde,

dazu getan.