Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Binomialkoeffizienten » Beweis Binomialkoeffizienten Summenformel
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Beweis Binomialkoeffizienten Summenformel
Teido
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2015
Mitteilungen: 57
Wohnort: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2016-11-05


Hallo,
ich sitze vor folgender Aufgabe und finde einfach nicht den passenden weg zur Lösung:

<math>\sum \limits_{k=1}^{n} k \binom{n}{k} x^k (1-x)^{n-k} = nx</math>

Den Anfang habe ich für <math> n=1 </math> gezeigt:

<math> \sum \limits_{k=1}^{1} 1 \binom{1}{1} x^1 (1-x)^{1-1} = x =1x </math>

Ebenfalls steht in der Aufgabe folgendes Theorem soll verwendet werden: (wurde in der vorangegangenen Aufgabe Bewiesen)

<math> k \binom{n}{k} = n \binom{n-1}{k-1} </math>

Mein Ansatz sieht bisher so aus:
<math>
\sum \limits_{k=1}^{n+1} k \binom{n+1}{k} x^k (1-x)^{n+1-k}

= (n+1)x^{n+1} \binom{n+1}{n+1} (1-x)^{n+1-(n+1)} + \sum \limits_{k=1}^{n} k \binom{n}{k} x^k (1-x)^{n-k}

= x(n+1) x^n + \sum \limits_{k=1}^{n} k \binom{n}{k} x^k (1-x)^{n-k}
</math>

Im nächsten Schritt würde ich, aufgrund des Hinweises in der Aufgabe, <math>k \binom{n}{k}</math> austauschen. Danach allerdings ist auch schluss...

Die Alternative wäre, das Theorem vor dem abspalten des obersten Summengliedes anzuwenden, was mich leider auch nicht weiter gebracht hat.

Für einen kleinen Denkanstoß wäre ich sehr Dankbar :)

Grüße



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Red_
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.09.2016
Mitteilungen: 914
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2016-11-05


Hi,
ohne Induktion könntest du beide Seiten des binomischen Lehrsatzes ableiten:
<math>(a+b)^n = \sum_{k=0}^n {{n\choose k}\cdot a^k \cdot b^{n-k}</math>

Nach <math>a</math> ableiten und etwas umformen.

Red



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 11025
Wohnort: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2016-11-05


Hallo Teido,
der Artikel Vollständige Indoktrination ist lesenswert. Neben dem Vorschlag von Red_ kannst Du auch den Ausdruck <math>k\binom{n}{k}</math> in der ursprünglichen Summe ersetzen und umformen, damit Du den binomischen Lehrsatz anwenden kannst.

Bei Deinem Induktionsschritt hast Du in der Summe plötzlich <math>k\binom{n}{k}</math> statt <math>k\binom{n+1}{k}</math>.

Ich hoffe, das hilft Dir,
Roland

[Die Antwort wurde vor Beitrag No.1 begonnen.]

[Verschoben aus Forum 'Mathematik' in Forum 'Binomialkoeffizienten' von rlk]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Teido
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2015
Mitteilungen: 57
Wohnort: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2016-11-06


Vielen dank für den Hinweis, arbeite den Artikel gerade durch.

Hab allerdings mit einer Aussage direkt im zweiten Kapitel ein wenig zu kämpfen:

''Aus der Eindeutigkeit im Rekursionssatz folgt übrigens das Prinzip der vollständigen Induktion: Man betrachte hierbei <math>a : \mathds{N}\to \{0,1\}</math> definiert durch <math>(a(n)=1) \Leftrightarrow P(n)</math> Aus <math>P(0)</math> folgt dann <math>a(0)=1</math>, und <math>P(n) \Rightarrow P(n+1)</math> besagt <math>a(n)=1 \Rightarrow a(n+1)=1</math>. Die konstante Abbildung <math>n \mapsto 1</math> erfüllt dieselbe Rekursionsvorschrift, sodass also <math>a(n)=1</math> für alle <math>n \in \mathds{N}</math> gilt, d.h. <math>P(n)</math> gilt für alle <math>n \in \mathds{N}</math>. Der Rekursionssatz ist also stärker als die vollständige Induktion.''

Meiner Auffassung nach wird hier gesagt, dass eine Abbildung <math>a</math> von <math>\mathds{N}</math> auf {0,1} abbildet, was Äquivalent zur Rekursiven Vorschrift <math>P(n)</math> ist. Aufgrund der Äquivalenz folgt dann, dass <math>P(0) \Rightarrow a(0)</math>. Hier hab ich schon die erste Schwierigkeit: Warum darf bzw. wird hier nochmal aus <math>P(0)</math> gefolgert? Schließlich ist <math>a(n)=1</math> ja bereits am Anfang des Satzes definiert...

Die zweite Hälfte ergibt dann wieder etwas mehr Sinn für mich:
<math>P(n)</math> gibt einen Wert aus, und da die Vorschrift rekursiv ist, kann P aus dem Ergebnis <math>P(n+1)</math> 'erzeugen'. Ebenfalls gilt: die Vorschrift ist äquivalent zur Abbildung , daher folgt  <math>(P(n) \Rightarrow P(n+1)) \Leftrightarrow (a(n) \Rightarrow a(n+1))</math>.

Gibt es vielleicht noch andere Artikel speziell über den Rekursionssatz von Dedekind? Über Google bin ich nicht so wirklich fündig geworden.

Grüße



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Teido
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2015
Mitteilungen: 57
Wohnort: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2016-11-06


Desweiteren glaube ich, den beweis erbracht zu haben:
(ist schon spät, hoffe mal ich habe keinen groben Unfug gemacht..)

<math>

\sum \limits_{k=1}^{n+1} k \binom{n+1}{k} x^k (1-x)^{n+1-k}


=\sum \limits_{k=1}^{n+1} n \binom{n-1+1}{k-1} x^k (1-x)^{n+1-k}

=\sum \limits_{k=0}^{n} (n+1) \binom{n}{k-1+1} x^{k+1} (1-x)^{n+1-(k+1)}

= (n+1)x \sum \limits_{k=0}^{n}  \binom{n}{k} x^k (1-x)^{n-k}

</math>
Einsetzen des Binomialkoeffizienten:
<math>
(n+1)x (x+1-x)^n = (n+1)x
</math>




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 11025
Wohnort: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2016-11-06


Hallo Teido,
ja, so ähnlich hatte ich mir das vorgestellt. In der zweiten Zeile hast Du <math>n</math> statt <math>n+1</math> als ersten Faktor, aber in der dritten ist es wieder richtig.

Servus,
Roland



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Teido
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2015
Mitteilungen: 57
Wohnort: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2016-11-06


Ja, ich hab den Laufindex der Summe an den des Binomialsatzes dort angepasst. Jedoch bin ich mir nicht so ganz sicher ob ich dabei alles richtig umgeformt habe. Schließlich habe ich ja auch kein n+1 über k geschrieben beim anpassen...

Wenn ich so nochmal drüber schaue würde ich das ganze eher so machen:
<math>

\sum \limits_{k=1}^{n+1} k \binom{n+1}{k} x^k (1-x)^{n+1-k}


=\sum \limits_{k=1}^{n+1} (n+1) \binom{n-1+1}{k-1} x^k (1-x)^{n+1-k}

</math>
Anpassen des Summenindizes von <math>k=1..(n+1) \rightarrow k=0..n </math>

<math>
=\sum \limits_{k=0}^{n} (n+1) \binom{n}{k-1+1} x^{k+1} (1-x)^{n+1-(k+1)}

= (n+1)x \sum \limits_{k=0}^{n}  \binom{n}{k} x^k (1-x)^{n-k}

</math>

Müsste ich beim anpassen nicht auch alle <math>n </math> mit <math> n+1 </math> austauschen, wodurch das ganze zu <math> n+2 </math> wird?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 11025
Wohnort: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2016-11-06


Hallo Teido,
Du hast eine Indexverschiebung gemacht, also den Summationsindex <math>k</math> durch <math>m=k+1</math> ersetzt. Wieso sollte sich dadurch das von <math>k</math> unabhängige <math>n</math> ändern?

Servus,
Roland



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Teido hat die Antworten auf ihre/seine Frage gesehen.
Teido wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]