Summe von Binomialkoeffizient

10.11.2013, 18:01

morethanlife

Auf diesen Beitrag antworten »

Summe von Binomialkoeffizient

'nabend zusammen.
Ich sitz' gerade an ein paar Aufgaben und bei einer komme ich einfach nicht weiter. Wäre toll, wenn jemand mir helfen könnte.

Es geht um einen Induktionsbeweis mit Summenzeichen und Binomialkoeffizient.

Für alle n aus den Natürlichen Zahlen (mit 0) gilt:

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

Angefangen habe ich mit dem Induktionsanfang, das lief auch ganz gut und zeigt, dass für n = 1 die Gleichung aufgeht.
Bei dem Induktionsschritt komme ich leider überhaupt nicht weiter. Ich hab nicht so die Ahnung, wie man die Summe von einem Binomialkoeffizienten umformen/berechnen/vereinfachen kann.

Über einen kleinen Denkanstoss würde ich mich sehr freuen smile

smile

LG

10.11.2013, 18:24

Kasen75

Auf diesen Beitrag antworten »

Hallo,

allgemein gilt ja: $\begin{eqnarray*} \begin{pmatrix}n+1 \\ k+1 \end{pmatrix} = \begin{pmatrix}n \\ k \end{pmatrix}+\begin{pmatrix}n \\ k+1 \end{pmatrix} \end{eqnarray*}$

Das könnte helfen.

Grüße.

Edit:
@jimmyt
@mythos
Unsere drei Posts ergänzen sich perfekt. Insofern kann im Prinzip jeder von uns weitermachen.

10.11.2013, 18:25

jimmyt

Auf diesen Beitrag antworten »

RE: Summe von Binomialkoeffizient

Zitat:

Original von morethanlife
...
Für alle n aus den Natürlichen Zahlen (mit 0) gilt:

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

Angefangen habe ich mit dem Induktionsanfang, das lief auch ganz gut und zeigt, dass für n = 1 die Gleichung aufgeht.
Bei dem Induktionsschritt komme ich leider überhaupt nicht weiter. Ich hab nicht so die Ahnung, wie man die Summe von einem Binomialkoeffizienten umformen/berechnen/vereinfachen kann.

Über einen kleinen Denkanstoss würde ich mich sehr freuen smile

smile

LG

Naja, so wie sonst auch: smile

smile

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \binom {b + k} k ~=~ \left ( \sum\limits_{k=0}^{n} \binom {b + k} k \right ) + \binom {b + n+1} {n+1} ~\stackrel{I.V.}{=}~ \dots ~=~ \binom {b + n + 2} {n+1} \end{eqnarray*}$

10.11.2013, 18:26

jimmyt

Auf diesen Beitrag antworten »

@Kasen75 :

Sorry, du warst 1 min. schneller. Freude

Freude

10.11.2013, 18:34

mYthos

Auf diesen Beitrag antworten »

Zeige: Aus der Richtigkeit für n folgt, dass die Formel auch für (n + 1) richtig ist:
Das heisst, rechts in die Induktionsbehauptung wird anstatt n --> (n + 1) eingesetzt und links wird die Summe um den (n + 1). Summand vergrößert, das muss eine Identität ergeben:

$\begin{eqnarray*} \begin{pmatrix} b+n+1 \\ n \\ \end{pmatrix} + \begin{pmatrix} b+n+ 1 \\ n + 1 \\ \end{pmatrix} = \begin{pmatrix} b+n+2 \\ n+1 \\ \end{pmatrix} \end{eqnarray*}$
---------

EDIT(2):

Zitat:

Original von Kasen75
...
allgemein gilt ja: $\begin{eqnarray*} \begin{pmatrix}n+1 \\ k+1 \end{pmatrix} = \begin{pmatrix}n \\ k \end{pmatrix}+\begin{pmatrix}n \\ k+1 \end{pmatrix} \end{eqnarray*}$
...

Damit ist die obige Gleichung natürlich viel schneller zu verifizieren!

--------

Mit Hilfe der Beziehung $\begin{eqnarray*} \begin{pmatrix}n \\ k \\ \end{pmatrix} = \frac{n!}{k!(n-k)!} \end{eqnarray*}$ werden die Terme aufgelöst und anschließend die Gleichung mit $\begin{eqnarray*} \frac{(n + 1)!}{(b+n+1)!} \end{eqnarray*}$ multipliziert (damit der gleiche gemeinsame Nenner und gleichzeitig eine effiziente Kürzung erreicht werden) ..

Es ergibt sich eine Identität.

EDIT: Das ist ja direkt ein Ansturm ... na ja, dennoch lass' ich's mal stehen.

mY+

10.11.2013, 18:40

morethanlife

Auf diesen Beitrag antworten »

Hey, vielen lieben Dank an euch alle smile

smile

Ich werde diese Tipps mal benutzen und schauen, ob ich dann auf ein Ergebnis komme Wink

Wink

Anzeige

10.11.2013, 19:19

morethanlife

Auf diesen Beitrag antworten »

RE: Summe von Binomialkoeffizient

Zitat:

Original von jimmyt

Naja, so wie sonst auch: smile

smile

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \binom {b + k} k ~=~ \left ( \sum\limits_{k=0}^{n} \binom {b + k} k \right ) + \binom {b + n+1} {n+1} ~\stackrel{I.V.}{=}~ \dots ~=~ \binom {b + n + 2} {n+1} \end{eqnarray*}$

Sorry wenn ich das nicht so kapiere, aber bedeutet das, dass ich einfach das Summenzeichen weglassen und für k "n" einsetzen kann? Ich komme leider immer noch nicht so recht klar, ist halt noch recht neu.

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \binom {b + k} k ~=~ \left ( \sum\limits_{k=0}^{n} \binom {b + k} k \right ) + \binom {b + n+1} {n+1} <br /> <br /> = \begin{pmatrix} b + n \\ n \\ \end{pmatrix} + \begin{pmatrix} b + n + 1 \\ n + 1 \\ \end{pmatrix} <br /> <br /> = \begin{pmatrix} b + n \\ n \\ \end{pmatrix} + \begin{pmatrix} b + n \\ n \\ \end{pmatrix} + \begin{pmatrix} b + n \\ n + 1 \\ \end{pmatrix} \end{eqnarray*}$ . Ist das so richtig umgeformt?...

10.11.2013, 19:22

Kasen75

Auf diesen Beitrag antworten »

RE: Summe von Binomialkoeffizient
@jimmyt

Du machst weiter ?

10.11.2013, 19:54

Kasen75

Auf diesen Beitrag antworten »

RE: Summe von Binomialkoeffizient

Zitat:

Original von morethanlife

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \binom {b + k} k ~=~ \left ( \sum\limits_{k=0}^{n} \binom {b + k} k \right ) + \binom {b + n+1} {n+1} <br /> <br /> = \begin{pmatrix} b + n \\ n \\ \end{pmatrix} + \begin{pmatrix} b + n + 1 \\ n + 1 \\ \end{pmatrix} \end{eqnarray*}$

Das Summenzeichen bekommst du nicht weg, indem du einfach für k n einsetzt. $\begin{eqnarray*} \begin{pmatrix} b + n \\ n \\ \end{pmatrix} \end{eqnarray*}$ repräsentiert nur den letzten Summanden der Summe.

Lasse die linke Seite so, wie du sie hier in der ersten Zeile hast. Jetzt solltest du die rechte Seite (mit n+1): $\begin{eqnarray*} \begin{pmatrix} b + n + 1+1 \\ n+1 \\ \end{pmatrix} \end{eqnarray*}$ umformen.

Dabei hilft dir der Zusammenhang den ich schon gepostet hatte:

$\begin{eqnarray*} \begin{pmatrix}m+1 \\ l+1 \end{pmatrix} = \begin{pmatrix}m \\ l \end{pmatrix}+\begin{pmatrix}m \\ l+1 \end{pmatrix} \end{eqnarray*}$

Ich habe jetzt die Variablen m und l genommen, damit keine Verwechslungsgefahr besteht.

$\begin{eqnarray*} m=b + n + 1 \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{l}=n \end{eqnarray*}$

Edit: ich meinte l statt k.

Edit2:
@jimmyt
Ich kann im Moment nicht weiter machen.

10.11.2013, 20:20

morethanlife

Auf diesen Beitrag antworten »

Okay, ich erhalte dann

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

Wie geht's dann weiter? Muss ich dieses Ergebnis nun mit der Fakultätenschreibweise darstellen?

10.11.2013, 20:22

jimmyt

Auf diesen Beitrag antworten »

RE: Summe von Binomialkoeffizient

Zitat:

Original von Kasen75
@jimmyt

Du machst weiter ?

@Kasen75 :
Ich war kurz etwas essen. Mach du weiter. Freude

Freude

10.11.2013, 20:30

jimmyt

Auf diesen Beitrag antworten »

Zitat:

Original von morethanlife
Okay, ich erhalte dann

$\begin{eqnarray*} \sum\limits_{k=0}^n \begin{pmatrix} b + k \\ k \\ \end{pmatrix} + \begin{pmatrix} b + n + 1 \\ \textcolor{red}{n} \\\end{pmatrix} \textcolor{red}{+ \binom {b + n + 1} {n + 1}} \end{eqnarray*}$

Wie geht's dann weiter? Muss ich dieses Ergebnis nun mit der Fakultätenschreibweise darstellen?

Schau dir mal die rot markierten Sachen an.
Nachdem du das korrigiert hast, anschließend die Induktionvoraussetzung einsetzen.
Dann kurz rechnen, und schon hast du den Beweis. smile

smile

Tipp 1: Vor dem Rechnen schau dir das nochmal an:

Zitat:

Original von Kasen75
...
Dabei hilft dir der Zusammenhang den ich schon gepostet hatte:

$\begin{eqnarray*} \begin{pmatrix}m+1 \\ l+1 \end{pmatrix} = \begin{pmatrix}m \\ l \end{pmatrix}+\begin{pmatrix}m \\ l+1 \end{pmatrix} \end{eqnarray*}$

Ich habe jetzt die Variablen m und l genommen, damit keine Verwechslungsgefahr besteht.

$\begin{eqnarray*} m=b + n + 1 \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{l}=n \end{eqnarray*}$

Edit: ich meinte l statt k.

Tipp 2: Kurze Anmerkung zu Latex:
Du kannst auch anstelle der pmatrix den Befehl binom n k nehmen. Freude

Freude

10.11.2013, 20:53

morethanlife

Auf diesen Beitrag antworten »

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

Ist es nun korrekt? Und was genau ist hier die Induktionsvoraussetzung?

Es tut mir echt leid... Danke für eure Geduld. Gott

Gott

10.11.2013, 21:09

jimmyt

Auf diesen Beitrag antworten »

Zitat:

Original von morethanlife
$\begin{eqnarray*} \sum\limits_{k=0}^n \begin{pmatrix} b + k \\ k \\ \end{pmatrix} + \begin{pmatrix} b + n + 1 \\ n + 1 \\\end{pmatrix} \textcolor{red}{+ \begin{pmatrix} b + n + 2 \\ n + 2 \\\end{pmatrix}} \end{eqnarray*}$

Ist es nun korrekt? ...

Nein, leider nicht. Das rot markierte bitte streichen. smile

smile

Zitat:

Original von morethanlife
... Und was genau ist hier die Induktionsvoraussetzung? ...

Induktionvoraussetzung:

$\begin{eqnarray*} \sum\limits_{k=0}^{n} \binom {b + k} k ~=~ \binom {b + n+1} {n} \end{eqnarray*}$

Zitat:

Original von morethanlife
...
Es tut mir echt leid... Danke für eure Geduld. Gott

Gott

Kein Problem, aller Anfang ist schwer.

Induktionschritt:

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \binom {b + k} k ~=~ \left ( \sum\limits_{k=0}^{n} \binom {b + k} k \right ) + \binom {b + n+1} {n+1} ~\stackrel{I.V.}{=}~ \textcolor{red}{\binom {b + n+1} {n}} + \binom {b + n+1} {n+1} ~=~ \dots \end{eqnarray*}$

Das rot markierte ist der Teil, wo du die Induktionvoraussetzung während des Induktionschrittes einsetzt.
Den Rest müßtest du jetzt mit dem sehr guten Tipp von Kasen75 eigentlich hinbekommen. Freude

Freude

Edit:
@Kasen75
Ok, dann mache ich weiter. Ich glaube wir haben's gleich.

10.11.2013, 21:40

morethanlife

Auf diesen Beitrag antworten »

Okay, das hat mir schon echt weitergeholfen. Ich erhalte dann:

$\begin{eqnarray*} \sum\limits_{k=0}^n \begin{pmatrix} b + k \\ k \\ \end{pmatrix} + \begin{pmatrix} b + n + 1 \\ n + 1 \\\end{pmatrix} <br /> <br /> = \begin{pmatrix} b + n + 1 \\ n \\ \end{pmatrix} + \begin{pmatrix} b + n + 1 \\ n + 1 \\ \end{pmatrix} <br /> <br /> = \begin{pmatrix} b + n + 1 \\ n \\ \end{pmatrix} + \begin{pmatrix} b + n \\ n \\ \end{pmatrix} + \begin{pmatrix} b + n \\ n + 1 \\ \end{pmatrix} \end{eqnarray*}$

Bis dahin richtig? Ich habe versucht den Tipp von Kasen anzuwenden. Nun stehe ich leider erneut auf dem berühmten Schlauch. Nun habe ich probiert diese Binomialkoeffizienten als Fakultäten zu schreiben... leider ohne Erfolg unglücklich

unglücklich

. Der letzte Schritt besteht aber darin, oder?

10.11.2013, 22:14

morethanlife

Auf diesen Beitrag antworten »

Ich glaub ich hab es jetzt:

$\begin{eqnarray*} \begin{pmatrix} b + n + 1 \\ n \\ \end{pmatrix} + \begin{pmatrix} b + n + 1 \\ n + 1 \\ \end{pmatrix} <br /> <br /> <br /> = \begin{pmatrix} b + n + 2 \\ n + 1 \\ \end{pmatrix} \end{eqnarray*}$

Genau das erhält man, wenn man in die ursprüngliche Gleichung auf der rechten Seite n + 1 einsetzt.
Puhh, das war's jetzt aber oder?

10.11.2013, 22:54

mYthos

Auf diesen Beitrag antworten »

Um dich nicht mehr länger auf die Folter zu spannen (Jimmy schläft vielleicht schon Augenzwinkern

Augenzwinkern

), ja, so stimmt es.
Dies war ja schon am Anfang evident, man muss es halt "sehen".

mY+

10.11.2013, 23:10

morethanlife

Auf diesen Beitrag antworten »

Hehe, Vielen Dank.

Der Binomialkoeffizient bzw. das Summenzeichen bzw. die Kombination der beiden sind halt für einen Anfänger noch nicht so durchsichtig. Die Hilfestellungen haben mir auf jeden Fall sehr gut weitergeholfen. smile

smile

Wink

10.11.2013, 23:18

jimmyt

Auf diesen Beitrag antworten »

Gerne geschehen. smile

smile

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »