Beweis einer Summengleichung

04.11.2008, 23:31

samarium22

Beweis einer Summengleichung

Hallo zusammen,

Ich bin neu im Forum und würde mich freuen, wenn ihr mir helfen könntet.
Wir haben ein Übungsblatt mit beweisen bekommen. Die ersten drei Beweise konnte ich problemlos lösen. Nur beim letzten verzweifle ich.

Weisen sie nach, dass die nachfolgende Gleichung für alle n und k element aus den natürlichen Zahlen mit k <= n gültig ist:

(n+1 über k+1) = Summe von m=k bis n (m über k)

Im Voraus vielen Dank für eure Hilfe. Sorry ich muss das mit dem Formeleditor mal lernen. Bin halt noch neu hier

Edit (mY+): Deswegen trotzdem keine Hilferufe und bitte auch einen aussagekräftigen Titel!! Geändert. Auch ist das kein Analysis-Thema!

05.11.2008, 01:39

WebFritzi

Auf diesen Beitrag antworten »

RE: Beweis einer Summengleichung

Zitat:

Original von samarium22
Sorry ich muss das mit dem Formeleditor mal lernen. Bin halt noch neu hier

Dann tu das doch bitte jetzt gleich. Danke.

05.11.2008, 02:32

samarium22

Auf diesen Beitrag antworten »

RE: Beweis einer Summengleichung
$\begin{eqnarray*} \begin{pmatrix} n & +1 \\ k & +1 \end{pmatrix}~\ \end{eqnarray*}$ = $\begin{eqnarray*} \sum_{m=k}^\infty \end{eqnarray*}$ $\begin{eqnarray*} \binom m k \end{eqnarray*}$

Ich kriege jedoch das unendlich Zeichen nicht weg. Es müsste durch ein n ersetzt werden

Freude

05.11.2008, 04:30

Lazarus

Auf diesen Beitrag antworten »

Du wirst es mit Induktion machen wollen oder ?

Kennst du denn ein Additionstheorem für Binomialkoeffizienten ?
Das hier ist sozusagen nur eine "extended Version" davon.

05.11.2008, 10:16

Dual Space

Auf diesen Beitrag antworten »

[OFFTOPIC]
Sag mal Lazarus, wann schläfst du denn eigentlich mal? geschockt

[/OFFTOPIC]

05.11.2008, 12:47

Airblader

Auf diesen Beitrag antworten »

RE: Beweis einer Summengleichung

Zitat:

Original von samarium22
Ich kriege jedoch das unendlich Zeichen nicht weg. Es müsste durch ein n ersetzt werden

Bei "\sum_{m=k}^\infty" einfach das "\infty" durch "n" ersetzen Augenzwinkern

Im Übrigen musst du nicht für jedes Zeichen eine neue "[ latex ] ... [ /latex ]"-Umgebung schreiben. Ruhig alles in eine Zeile:

code:
1:	[latex]\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} = \sum_{m=k}^n \binom m k[/latex]

ergibt:

$\begin{eqnarray*} \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} = \sum_{m=k}^n \binom m k \end{eqnarray*}$

air

05.11.2008, 13:51

samarium22

Auf diesen Beitrag antworten »

Ja es sollte mit Induktion bewiesen werden.
Was ein Additionstheorem ist weiß ich. Nur bekomm ich es mit der Induktion nicht wirklich gebacken.

05.11.2008, 14:10

Lazarus

Auf diesen Beitrag antworten »

@samarium22: Also ein bisschen mehr als ein "das versteh ich nicht" hätte ich mir schon erwartet.
Was kann man daran nicht backen ? Induktion ist ja, um in der Metapher zu bleiben, immer nach einem Standardrezept zuzubereiten. Also schrittweise vortasten bitte! Wie fängt man Induktion an ?

OT:
Dual Space: Schlaf ? Je nage dans le brouillard!

05.11.2008, 15:55

samarium22

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} = \sum_{m=k}^n \binom m k \end{eqnarray*}$

Induktionsanfang: n=1 , k=1, m=k

$\begin{eqnarray*} \begin{pmatrix} n & +1 \\ k & +1 \end{pmatrix}~\ \end{eqnarray*}$ = $\begin{eqnarray*} \,~\binom 2 2 \end{eqnarray*}$ = $\begin{eqnarray*} \frac{2!}{2!} \end{eqnarray*}$ = $\begin{eqnarray*} \frac{3}{3} \end{eqnarray*}$ = 1

$\begin{eqnarray*} \sum_{m=k}^n \binom m k \end{eqnarray*}$ = $\begin{eqnarray*} \,~\binom 1 1 \end{eqnarray*}$ = $\begin{eqnarray*} \frac{1!}{1!} \end{eqnarray*}$ = 1

Induktionsvoraussetzung:

für alle n und alle k $\begin{eqnarray*} \in \end{eqnarray*}$ $\begin{eqnarray*} ~\mathbb N~ \end{eqnarray*}$ mit k $\begin{eqnarray*} \leq~ \end{eqnarray*}$ n gilt $\begin{eqnarray*} \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} = \sum_{m=k}^n \binom m k \end{eqnarray*}$

Induktionsbehauptung:

$\begin{eqnarray*} \begin{pmatrix} (n+1)+1 \\ k+1 \end{pmatrix} = \sum_{m=k}^{n+1} \binom m k \end{eqnarray*}$

Induktionsschritt: n -------> n+1

Hier hackt es bei mir ich weiß nicht wie ich weiter machen soll...

unglücklich

05.11.2008, 17:58

WebFritzi

Auf diesen Beitrag antworten »

Dein Ansatz ist schon nicht in Ordnung. Damit beweist du nur die Behauptung für n = k. Und das braucht man nun wirklich nicht mit Induktion zu zeigen.

05.11.2008, 19:50

samarium22

Auf diesen Beitrag antworten »

Wie kann ich den für alle n und k aus N mit k <= n beweisen? Induktion oder anders?

05.11.2008, 19:54

WebFritzi

Auf diesen Beitrag antworten »

Du kannst es mit Induktion beweisen. Die Induktionsbehauptung wäre dann:

Für alle natürlichen n gilt:

$\begin{eqnarray*} \forall k\in\{0,1,\dots,n\}:\quad\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} = \sum_{m=k}^n \binom m k. \end{eqnarray*}$

Im Induktionsschritt ist das bereits von Lazarus genannte Additionstheorem für Binomialkoeffizienten nützlich.

05.11.2008, 20:04

samarium22

Auf diesen Beitrag antworten »

Ok vielen Dank Freude

06.11.2008, 00:35

samarium22

Auf diesen Beitrag antworten »

Ich bin euren Vorschlägen nachgegangen ( additionstheorem der Binomialkoeffizienten) und habe so Schritt für Schritt den obigen Beweis augestellt. Ich saß jetzt ne lange Zeit dran. Ich hoffe ich habe zwischendrin keine Fehler gemacht. Danke für die Hilfe Wink

Induktionsanfang: n= 1

$\begin{eqnarray*} \sum_{m=k}^n \binom m k \end{eqnarray*}$ = $\begin{eqnarray*} \frac{1!}{1!} \end{eqnarray*}$ = 1

$\begin{eqnarray*} \begin{pmatrix} n + 1 \\ k + 1 \end{pmatrix}~ \end{eqnarray*}$ = $\begin{eqnarray*} \frac{2!}{2!} \end{eqnarray*}$ = 1

Induktionsvoraussetzung:

für alle n und alle k $\begin{eqnarray*} \in~\mathbb N~\ \end{eqnarray*}$ mit k $\begin{eqnarray*} \leq~ \end{eqnarray*}$ n gilt $\begin{eqnarray*} \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} = \sum_{m=k}^n \binom m k \end{eqnarray*}$

Induktionsbehauptung:

$\begin{eqnarray*} \sum_{m=k}^{n+1}\binom m k \end{eqnarray*}$ = $\begin{eqnarray*} \begin{pmatrix} (n +1) + 1 \\ k + 1 \end{pmatrix}~ \end{eqnarray*}$

Induktionsschritt: n ------> n+1

$\begin{eqnarray*} \sum_{m=k}^{n+1}\binom m k \end{eqnarray*}$ = ( $\begin{eqnarray*} \sum_{m=k}^n\binom m k \end{eqnarray*}$ ) + $\begin{eqnarray*} \begin{pmatrix} n +1 \\ k \end{pmatrix}~ \end{eqnarray*}$ = $\begin{eqnarray*} \begin{pmatrix} n +1 \\ k +1 \end{pmatrix}~ \end{eqnarray*}$ + $\begin{eqnarray*} \begin{pmatrix} n +1 \\ k \end{pmatrix}~ \end{eqnarray*}$

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

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

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

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

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

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

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

= $\begin{eqnarray*} \begin{pmatrix} n + 2 \\ k + 1 \end{pmatrix}~ \end{eqnarray*}$

= $\begin{eqnarray*} \begin{pmatrix} (n+1) + 1 \\ k + 1 \end{pmatrix}~ \end{eqnarray*}$

q.e.d

07.11.2008, 02:44

WebFritzi

Auf diesen Beitrag antworten »

Das hast du sehr gut gemacht. Nur die Induktionsvoraussetzung ist falsch, denn das ist die Behauptung. Es muss heißen: "Für ein n gilt..." und nicht "Für alle n gilt...". Außerdem:

Zitat:

Original von samarium22
Ich bin euren Vorschlägen nachgegangen ( additionstheorem der Binomialkoeffizienten)

Das sehe ich nirgends. Du hast das Additionstheorem einfach mal kurz in deinem Induktionsschritt bewiesen. Augenzwinkern

Wenn du es sofort verwendet hättest, wäre der Induktionsschritt ein Einzeiler gewesen.

Neue Frage »

Antworten »

Beweis einer Summengleichung

Verwandte Themen