Binomialkoeffizient

31.10.2010, 19:41

Sub

Auf diesen Beitrag antworten »

Binomialkoeffizient

Meine Frage:
Hallo Leuz

Ich verstehe folgende Frage nicht ganz,

Beweise die folgenden Aussagen für alle x Element R und alle k Element N:

Zwei Aufgaben sind dargestellt, in der ersten kommen (x,k) vor in der zweiten gibt es nur (n,k).

In der zweiten Aufgabe soll ich folgenden Beweis führen:

Summe(k=0 bis n) mit (n über k) = 2^n.

Wie soll ich das für x beweisen, es kommt drin doch garnicht vor, oder sollt ich x einfach gleich n setzen, weil n auch Element der reellen Zahlen ist?
Ausserdem. Es ist mir nicht ganz klar wie ich k wählen soll, da k=0 doch kein Element aus N ist, oder irre ich mich?

Meine Ideen:
Mein Ansatz war folgender;

2^n = (1+1)^n = Summe(k=0 bis n)(n über k)*1^k*1^n-k = Summe(k=0 bis n)
(n über k).

Ich hatte diesen Ansatz hier schon gesehen gehabt, allerdings sollte man dort zeigen, dass es für alle n Element N mit einschliesslich der 0 gilt.

Bitte um Rat
Sub.

31.10.2010, 20:25

system-agent

Auf diesen Beitrag antworten »

Zuerst einmal ist es Definitionssache ob die Null eine natürliche Zahl sein soll oder nicht. Das kann jeder handhaben wie derjenige lustig ist.

Also du sollst zeigen, dass $\begin{eqnarray*} \sum\limits_{k=0}^n{n\choose k}=2^n \end{eqnarray*}$ .
Hier kommt wirklich kein $\begin{eqnarray*} x \end{eqnarray*}$ vor, also wird sich das eben auf eine Teilaufgabe beziehen.

Zuerst einmal: Was gefällt dir denn an $\begin{eqnarray*} n=0 \end{eqnarray*}$ nicht?
Da wäre $\begin{eqnarray*} 2^0=? \end{eqnarray*}$ und $\begin{eqnarray*} \sum\limits_{k=0}^0{n\choose k}={0\choose0}=? \end{eqnarray*}$ , also?

Für $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ hast du den Beweis schon.

01.11.2010, 14:23

Sub

Auf diesen Beitrag antworten »

Binomialkoeffizient
Vielen Dank, ich denke auch die Aufgabenstellung muss so sein.

Also grundsätzlich hab ich nix gegen die null smile

smile

Was Du meinst, es wäre (1=1) oder?

Den Beweis kann ich ja dann in der gleichen weise für n = 1 fortfühern oder?
Aber du sagtest ich hätte ihn schon für (n>=1).

Was mich aber interssieren würde ist der übergang von (n zu n+1) , den muss man doch noch zeigen.

Mein Ansatz:

2^n+1 = (1+1)^n+1 = Summe(k=0 bis n+1) (n+1 über k) * 1^n + 1 - k * 1^k =

Summe(k=0 bis n) (n über k=0) + 1 * 1^n+1 = 1 + 1 * 1^n+1 = 2^n+1.

Ist das so in ordnung?

01.11.2010, 14:28

klarsoweit

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient

Zitat:

Original von Sub
Was mich aber interssieren würde ist der übergang von (n zu n+1) , den muss man doch noch zeigen.

Wieso? Das mußt du nur bei einer vollständigen Induktion.
Hier hast du aber die allgemeine binomische Formel angewendet. Und damit ist die Sache erledigt.

01.11.2010, 14:42

Sub

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient
Aha Ok.

War den der Beweis von (n zu n+1) nach Induktion wenigstens richtig?

01.11.2010, 14:50

klarsoweit

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient
Der ist - mit Verlaub - einfach nur murks.
Abgesehen von der falschen binomischen Formel, wie willst du von

Zitat:

Original von Sub
Summe(k=0 bis n+1) (n+1 über k) * 1^n + 1 - k * 1^k =

auf

Zitat:

Original von Sub
Summe(k=0 bis n) (n über k=0) + 1 * 1^n+1

kommen?

Anzeige

01.11.2010, 15:00

Sub

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient
Ich dachte in der zweiten Summe, wenn ich zu (n über k ) die 1 addiere gilt Gleichheit mit der ersten Summe.

Und ich hätte die Gleichung damit äqivalent umgeformt.

01.11.2010, 15:09

klarsoweit

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient
Bevor ich mich weiter dazu auslasse, solltest du
a) die Formeln mit Latex und
b) diese richtig
schreiben.

Ich bekomme ja langsam Augenflimmern.

01.11.2010, 16:33

Sub

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient
Ja mach ich, ich habs mir jetzt runtergeladen und versuch mich im umgang damit.

01.11.2010, 16:57

system-agent

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient

Zitat:

Original von Sub
Ja mach ich, ich habs mir jetzt runtergeladen und versuch mich im umgang damit.

Du musst das nicht bei dir installieren um es hier im Board zu nutzen. Die Formeln tippst du mithilfe des Boardeigenen Formeleditors und stellst den "Formelcode" zwischen

code:
1:	[latex] ... [/latex]

ein.

01.11.2010, 17:01

Sub

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient
Ich versuche es, bloss kenn ich noch die ganzen Befehle nicht die ich zwischen
latex und /latex rein setzen muss damit meine Aufgabe dar steht.

01.11.2010, 17:09

Sub

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient
$\begin{eqnarray*} [latex]\sum\nolimits_{k=0}^{n+1} {n+1 \choose k} = 2^{n+1} \end{eqnarray*}$ [/latex]

Ok es stimmt so. ich wollte beweisen das die Formel für alle n stimmt.

In der Aufgabenstellung steht aber ich soll es für alle k Element N beweisen.

Zuvor hatte ich es mit dem Binomiallehrsatz beweisen gehabt für n grösser gleich 1.

Jetzt würde ich das noch gerne mit der induktion beweisen und zwar von n auf n+1 und habe diese Formel dafür augestellt.

Bin mir aber weiterhin nicht sicher was mit dem k gemeint ist, ist k einfach irgendeine natüliche Zahl wie n?

Wie müsste ich jetzt vorgehen?

01.11.2010, 17:24

system-agent

Auf diesen Beitrag antworten »

Vergiss doch dieses dämliche $\begin{eqnarray*} k \end{eqnarray*}$ , in deiner Formel ist es nur ein Index, nicht mehr und nicht weniger.

Also versuche den Induktionsschritt einmal zu tun.
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1}{n+1\choose k}=\sum\limits_{k=0}^n{n+1\choose k} + {n+1\choose n+1}=? \end{eqnarray*}$

Nun schau dir mal das an.

01.11.2010, 17:53

Sub

Auf diesen Beitrag antworten »

Ist das,

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1}{n+1\choose k}=\sum\limits_{k=0}^n{n+1\choose k} + {n+1\choose n+1}={n+2\choose n+k+1} \end{eqnarray*}$

01.11.2010, 17:59

system-agent

Auf diesen Beitrag antworten »

Was willst du nun damit? Vor allem wohin ist die Summe verschwunden?
Du kannst doch ziemlich einfach $\begin{eqnarray*} {n+1\choose n+1} \end{eqnarray*}$ berechnen.
Dann steht also
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1}={n+1\choose n+1}+\sum\limits_{k=0}^n{n+1\choose k} \end{eqnarray*}$
da.
Auf den Inhalt der Summe kannst du das anwenden, was du bei Wikipedia findest. Was kriegst du dann?

01.11.2010, 18:30

Sub

Auf diesen Beitrag antworten »

Binomialkoeffizient
Ich bin mir nicht sicher was ich da machen muss. Ich habe alles auf gleichen nenner gebracht...

01.11.2010, 18:43

system-agent

Auf diesen Beitrag antworten »

Aha. Ich sehe hier weder dein Notizblatt noch Nenner. Beantworte doch einfach mal die Fragen.
(i) $\begin{eqnarray*} {n+1\choose n+1}=? \end{eqnarray*}$
(ii) $\begin{eqnarray*} {n+1\choose k}=? \end{eqnarray*}$ , wobei du das hier mithilfe dessen umformen sollst, was ich dir auch Wikipedia gezeigt habe.

01.11.2010, 18:58

Sub

Auf diesen Beitrag antworten »

mach ich,

(i) $\begin{eqnarray*} {n+1\choose n+1}={n\choose k} + {n\choose k+1} \end{eqnarray*}$

und

(ii) $\begin{eqnarray*} {n+1\choose k}={n\choose k-1} + {n\choose k} \end{eqnarray*}$

01.11.2010, 19:29

system-agent

Auf diesen Beitrag antworten »

Dein erstes ist Quatsch. Was soll das $\begin{eqnarray*} k \end{eqnarray*}$ dort?
Es ist
$\begin{eqnarray*} {n+1\choose n+1}=\frac{(n+1)!}{(n+1)!\cdot((n+1)-(n+1))!}=? \end{eqnarray*}$ .

Mit der Umformung aus (ii) kriegst du dann also:
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1}{n+1\choose k}={n+1\choose n+1}+\left(\sum\limits_{k=0}^n{n\choose k-1}\right)+\left(\sum\limits_{k=0}^n{n\choose k}\right) \end{eqnarray*}$ .

Was weisst du über den dritten Summanden? [Induktion !!]

Für den zweiten Summanden beachte, dass $\begin{eqnarray*} {n\choose -1}=0 \end{eqnarray*}$ . Passe die Grenzen der Summe dann entsprechend an.

01.11.2010, 19:32

Sub

Auf diesen Beitrag antworten »

Binomialkoeffizient
Ja ich sehs, es tut mir leid mit dem k habe ich mich vertippt, mich aber dummerweise noch die ganze Zeit gefragt was es da soll.

01.11.2010, 19:48

system-agent

Auf diesen Beitrag antworten »

Hast du nun den Beweis?

01.11.2010, 19:54

Sub

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient
Das müsse doch jetzt (i) sein,

$\begin{eqnarray*} {n+1\choose n+1}=\frac{(n+1)!}{(n+1)!\cdot((n+1)-(n+1))!}={n\choose n} + {n\choose n+1} \end{eqnarray*}$

nein das kann ich sein

01.11.2010, 20:04

system-agent

Auf diesen Beitrag antworten »

unglücklich

Also bitte, rechne das jetzt mal ernsthaft aus. Hinweise: Kürzen; Was gibt die Differenz zweier gleicher Zahlen?; $\begin{eqnarray*} 0!=1 \end{eqnarray*}$ .

01.11.2010, 20:11

Sub

Auf diesen Beitrag antworten »

Es muss doch Null sein,

deshalb wenn ich im Nenner die Diffenrez beider Zahlen bilde, kommt da Null raus und ich erhalte als Ergebniss

$\begin{eqnarray*} {1\choose 0} \end{eqnarray*}$

01.11.2010, 20:16

system-agent

Auf diesen Beitrag antworten »

Was tust du denn da? Nun erinnere dich mal an die 6. Klasse und kürze einfach Brüche. Ganz egal was $\begin{eqnarray*} (n+1)! \end{eqnarray*}$ für eine Zahl ist, sie kommt im Zähler und Nenner vor, also?
Was ist denn nun $\begin{eqnarray*} (n+1)-(n+1) \end{eqnarray*}$ ?
Was also bleibt von dem grossen Bruch übrig?

01.11.2010, 20:25

Sub

Auf diesen Beitrag antworten »

Binomialkoeffizient
ist das,

$\begin{eqnarray*} (n+1)-(n+1)= 0 \end{eqnarray*}$ Fakultät und das ist gleich 1

und die 1 müsste doch als Endergebniss übrig bleiben oder?

01.11.2010, 20:31

system-agent

Auf diesen Beitrag antworten »

Ja, so ist es.

Nun also ersetze den schrecklicken Binomialkoeffizient $\begin{eqnarray*} {n+1\choose n+1} \end{eqnarray*}$ durch 1 in dem was wir oben am zeigen sind.

Die weiteren Fragen zu den anderen Summen, die ich dir oben gestellt habe, bleiben.

01.11.2010, 20:36

Sub

Auf diesen Beitrag antworten »

OK,

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1}{n+1\choose k}=1 +\left(\sum\limits_{k=1}^n{n\choose k-1}\right)+\left(\sum\limits_{k=0}^n{n\choose k}\right) \end{eqnarray*}$

Ich habe im zweiten Summanden k=1 gesetzt wegen der Null Definition.
Aber ich denk dadurch muss man das ganze im zweiten Summanden bis n+1 aufsummieren.

01.11.2010, 20:57

Sub

Auf diesen Beitrag antworten »

Ich versuche es darzustellen mache aber bei Latex irgendwo dauernd einen Fehler.

Ich weist das Bildungsgesetz mit Fakultät,

Und dass für die Summe(k=0 bis n) mit (n über k) für k=0,1,2,n = 2^n
rauskommt.

Wenn man für k diese Zahlen in den Binomialkoeffizienten einsetzt.

01.11.2010, 22:45

system-agent

Auf diesen Beitrag antworten »

Zitat:

Original von Sub
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1}{n+1\choose k}=1 +\left(\sum\limits_{k=1}^n{n\choose k-1}\right)+\left(\sum\limits_{k=0}^n{n\choose k}\right) \end{eqnarray*}$

Ja, das ist sehr gut.

Genau, die Induktionshypothese besagt gerade, dass
$\begin{eqnarray*} \sum\limits_{k=0}^n{n\choose k}=2^n \end{eqnarray*}$ .
Also kannst du den dritten Summanden ersetzen.

Beachte für den zweiten:
Es gilt
$\begin{eqnarray*} \sum\limits_{k=1}^n{n\choose k-1}=\sum\limits_{k=0}^{n-1}{n\choose k} \end{eqnarray*}$
nach einer weiteren kleinen Indexverschiebung. Erinnere dich nun nocheinmal an die Induktionshypothese. Beachte, dass hier nicht bis $\begin{eqnarray*} n \end{eqnarray*}$ summiert wird, also "fehlt" ein Summand.

01.11.2010, 23:41

Sub

Auf diesen Beitrag antworten »

Ich bin mir nicht sicher ob ich verstehe. Kann ich den zweiten Summanden nicht bis n+1 aufsummieren weil ich ja bei k = 1 anfange?
Dann würde mir kein Summand mehr fehlen

01.11.2010, 23:49

system-agent

Auf diesen Beitrag antworten »

Das verstehe ich nicht.

Ich schreib dir mal was auf:
$\begin{eqnarray*} 2^n=\sum\limits_{k=0}^n{n\choose k}={n\choose n}+\sum\limits_{k=0}^{n-1}{n\choose k} \end{eqnarray*}$ ,
wegen der Induktionshypothese. Klingelts?

02.11.2010, 00:01

Sub

Auf diesen Beitrag antworten »

Binomialkoeffizient
Hmm, aber laut der Definition ist es doch gerade so als würdest Du die 1 zum Summanden dazu addieren.

02.11.2010, 00:03

system-agent

Auf diesen Beitrag antworten »

Du sprichst in Rätseln.

02.11.2010, 00:05

Sub

Auf diesen Beitrag antworten »

Binomialkoeffizient
Was ich eben meinte ist, das folgendes gilt,

$\begin{eqnarray*} {n\choose n} = 1 \end{eqnarray*}$

02.11.2010, 00:18

system-agent

Auf diesen Beitrag antworten »

Ja, das stimmt. Damit wollte ich dich darauf stupsen, dass du diese lästige Summe
$\begin{eqnarray*} \sum\limits_{k=0}^{n-1}{n\choose k} \end{eqnarray*}$
sofort ausrechnen kannst und letztlich auch den in Frage stehenden zweiten Summanden in
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1}{n+1\choose k}=1 +\left(\sum\limits_{k=1}^n{n\choose k-1}\right)+\left(\sum\limits_{k=0}^n{n\choose k}\right) \end{eqnarray*}$
los wirst und das gewünschte Ergebnis folgt.

Du musst nur noch alles zusammenschreiben.

02.11.2010, 00:22

Sub

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient
Was ich eben meinte ist, das folgendes gilt,

$\begin{eqnarray*} {n\choose n} = 1 \end{eqnarray*}$

02.11.2010, 00:29

system-agent

Auf diesen Beitrag antworten »

Wie gesagt, das ist richtig. Nun schreibe gemäss meinem Beitrag eben alles zusammen und du bist fertig.

02.11.2010, 00:33

Sub

Auf diesen Beitrag antworten »

Binomialkoeffizien
Vielen Dank für deine Hilfe und Gedult, das mach ich.

Ich hab aber noch eine frage,

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

Wie soll ich den letzten Summanden ausrechnen, laut der Definition in Fakultät umwandeln, aber da steht ja noch die Summe da.

Also n -1 und k = 0 in den Binomialkoeffizienten einsetzen, Hauptnenner finden und mit $\begin{eqnarray*} {n\choose n } \end{eqnarray*}$ addieren?

02.11.2010, 00:50

system-agent

Auf diesen Beitrag antworten »

Ich hatte dir diese Zeile [=Induktionshypothese] doch gerade hingeschrieben, damit du die Summe ausrechnen kannst.
$\begin{eqnarray*} 2^n=\sum\limits_{k=0}^n{n\choose k}={n\choose n}+\sum\limits_{k=0}^{n-1}{n\choose k} \end{eqnarray*}$
ist doch dasselbe wie
$\begin{eqnarray*} \sum\limits_{k=0}^{n-1}{n\choose k}=2^n-{n\choose n}=2^n-1 \end{eqnarray*}$ .

12 nächste Seite »

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »