Beweis einer Summenformel mit Binomialkoeffizient

Question

Hallo liebe Community.
Seit kurzem studiere ich Informatik und bin bemüht in Mathematik auf Universitätsniveau durchzusteigen. Leider gestaltet sich das nicht immer als so einfach und ich würde mich über eure Hilfe sehr freuen.

Ich habe folgende Aufgabe auf meinem aktuellen Übungsblatt:
Beweise die Formel

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

Problem/Ansatz:

Ich bin mir bewust, dass sich der rechte Teil der Gleichung als
$$\frac{n!}{k! * (n-k)!}$$ schreiben lässt.
Ferner lässt sich durch geschicktes umformen bestimmt die linke Seite mehr der rechten angleichen.
Leider fehlt mir der entscheidende Gedanke/Ansatz
Induktion?
Kontraposition?

Ich bedanke mich für etwaige Ideen und Lösungsansätze!

MfG elyminas

Comments

Du hast den Binomialkoeffizienten aufgeschrieben. Du hast noch zusätzlich den Faktor k. Kürze diesen mit Hilfe von k!=1*2*3*...*(k-1)*k. Destilliere aus dem Rest wieder einen Binomialkoeffizienten ....

---

Ein alternativer Ansatz: Definiere \(\displaystyle f(x)=(1+x)^n=\sum_{k=0}^n\binom nkx^k\).
Differenzieren liefert \(\displaystyle f^\prime(x)=n{\cdot}(1+x)^{n-1}=\sum_{k=1}^nk{\cdot}\binom nkx^{k-1}\).
Setze nun \(x=1\) und erhalte \(\displaystyle f^\prime(1)=n{\cdot}2^{n-1}=\sum_{k=1}^nk{\cdot}\binom nk\).

---

@ Arsinoé4:

Danke; raffinierte Methode !

Wir wissen aber nicht, ob darin auch Bestandteile stecken, die nach Ansicht des Autors des Übungsblattes ebenfalls noch zu beweisen wären.

---

Gelöscht, weil nachträglich festgestellt, dass mein geposteter Rechenweg schon dastand.

Answer 1

Aloha :)

Willkommen in der Mathelounge... \o/

$$\sum\limits_{k=0}^{n}k\binom{n}{k}=\sum\limits_{k=\pink1}^{n}k\cdot\frac{n!}{k!\cdot(n-k)!}=\sum\limits_{k=1}^{n}k\cdot\frac{n\cdot (n-1)!}{k\cdot(k-1)!\cdot(n-k)!}$$$$\phantom{\sum\limits_{k=0}^{n}k\binom{n}{k}}=n\sum\limits_{k=1}^{n}\frac{(n-1)!}{(k-1)!\cdot(\underbrace{(n-1)-(k-1)}_{=(n-k)})!}=n\sum\limits_{k=1}^{n}\binom{n-1}{k-1}$$$$\phantom{\sum\limits_{k=0}^{n}k\binom{n}{k}}=n\sum\limits_{k=0}^{n-1}\binom{n-1}{k}=n\sum\limits_{k=0}^{n-1}\binom{n-1}{k}\cdot1^{(n-1)-k}\cdot1^k$$$$\phantom{\sum\limits_{k=0}^{n}k\binom{n}{k}}=n\cdot(1+1)^{n-1}=n\cdot2^{n-1}$$

Darin haben wir den binomischen Lehrsatz mit \(\,a=1\,\) und \(\,b=1\,\) verwendet:$$(a+b)^n=\sum\limits_{k=0}^n\binom{n}{k}a^{n-k}b^k\implies$$$$(1+1)^{n-1}=\sum\limits_{k=0}^{n-1}\binom{n-1}{k}\cdot1^{(n-1)-k}\cdot1^k\implies2^{n-1}=\sum\limits_{k=0}^{n-1}\binom{n-1}{k}$$

Comments

Wo hast Du denn die Induktionsvoraussetzung benutzt?

---

Danke für den Hinweis, habe mein Posting entsprechend angepasst.

---

Aloha Tschakabumba,
danke für deine ausführliche Antwort! =)

Ich bin gerade bemüht diese mental einwandfrei nachzuvollziehen, anstatt einfach zu kopieren, der Lerneffekt soll schließlich im Vordergrund stehen

Kannst du mir erklären wie du hier

\(\phantom{\sum\limits_{k=0}^{n}k\binom{n}{k}}=n\sum\limits_{k=0}^{n-1}\binom{n-1}{k}=n\sum\limits_{k=0}^{n-1}\binom{n-1}{k}\cdot1^{(n-1)-k}\cdot1^k\)

von der linken Seite der Gleichung zur rechten kommst?
Den eingänglichen Teil und die Umformung um in eine mit dem binomischen Lehrsatz kompatible Form zu kommen versteh' ich

Beste Grüße

---

Ich habe jeden Summanden mit einer \(1\) multipliziert:$$\binom{n-1}{k}=\binom{n-1}{k}\cdot\pink1=\binom{n-1}{k}\cdot\pink{1^{(n-1)-k}\cdot1^k}$$

---

Hallo nochmal,

ich versteh' leider immer noch nicht warum.

Sei

\(\binom{n-1}{k}=\)

\(\frac{(n-1)!}{k! * (n-1-k)!}\)

Multipliziere ich nun mit 1 kann ich den Zähler unverändert lassen und den Nenner als Nenner^-1 schreiben.. Aber wie komme ich zu

\({1^{(n-1)-k}\cdot1^k}\) ?

---

1 mal 1 ist immer noch einfach nur 1.

Und (1 mal "Irgendwas") ist gleich "irgendwas".

---

Das ist ja wohl ganz offensichtlich, ich würde hier nicht fragen wenn ich nicht nach Geisteskräften mitdenken würde
Aber wieso ist

\(\binom{n-1}{k}=\binom{n-1}{k}\cdot\pink1=\binom{n-1}{k}\cdot\pink{1^{(n-1)-k}\cdot1^k}\) ?

---

Immer noch:

Weil  \(\pink{1^{(n-1)-k}\cdot1^k}\)

einfach nur   \(\pink{1\cdot1}=1\) ist.

Und wenn man so etwas wie  \(\binom{n-1}{k}\) mit 1 multipliziert, darf man so etwas ohne weitere Konsequenzen tun, weil die Multiplikation mit 1 einen vorhandenen Wert nicht ändert.

---

Jetzt ist der Groschen gefallen, ich hatte angenommen es müsse hier eine Rechenregel für den Binomialkoeffizient geben o.Ä
danke für eure Geduld und Expertise abakus und Tschakabumba!

Answer 2

... der rechte Teil der Gleichung als$$\frac{n!}{k! * (n-k)!}$$ schreiben lässt

Das ist zu unkonkret. EIN FAKTOR im Rahmen der Summe lässt sich so schreiben. Du hast den Faktor k vergessen.

\(\green{k}\cdot \frac{n!}{k! * (n-k)!}=\frac{\green{k}\cdot 1\cdot2\cdot \cdots \cdot(n-1)\cdot n}{1\cdot2\cdot \cdots \cdot(k-1)\cdot k\qquad 1\cdot2\cdot \cdots \cdot(n-k-1)\cdot (n-k)}\).

In diesem Bruch kannst du k kürzen und n als Faktor herausziehen. Du erhältst

\(n\cdot\frac{ 1\cdot2\cdot \cdots \cdot(n-1)}{1\cdot2\cdot \cdots \cdot(k-1)\cdot \qquad 1\cdot2\cdot \cdots \cdot(n-k-1)\cdot (n-k)}=n\cdot \binom{n-1}{k-1}\).

Somit lautet die Behauptung

\(n*2^{n-1} = \sum \limits_{k=0}^{n}n\cdot \binom{n-1}{k-1}\) oder noch deutlicher \(2^{n-1} = \sum \limits_{k=0}^{n} \binom{n-1}{k-1}\).

Für k=0 ist der resultierende Binomialkoeffizient \(\binom{n-1}{-1}\) gleich null, und die Summe der übrigen Bionomialkoeffizienten (=Zeilensumme im Pascalschen Dreieck) ist bekanntlich eine Zweierpotenz.