Beweis mit n über k

23.10.2008, 22:12

Martin M.

Beweis mit n über k

Ich stehe vor einer Aufgabe und weiß nicht genau wie ich anfangen soll, viell könnt ihr mir einen Tipp geben:
Beweisen sie das für alle natürlichen Zahlen n und k gilt:
$\begin{eqnarray*} \begin{pmatrix} n \\ 0 \end{pmatrix} + \begin{pmatrix} n+1 \\ 1 \end{pmatrix} + ... + \begin{pmatrix} n+k \\ k \end{pmatrix} = \begin{pmatrix} n+k+1 \\ k \end{pmatrix} \end{eqnarray*}$

23.10.2008, 22:16

Auf diesen Beitrag antworten »

Induktion über $\begin{eqnarray*} k \end{eqnarray*}$ , wobei im Induktionsschritt wieder mal die wohlbekannte Summeneigenschaft des Pascalschen Dreiecks Anwendung finden darf.

24.10.2008, 10:07

bartho

Auf diesen Beitrag antworten »

Ich habe gerade genau das selbe problem mit dieser aufgabe.
Ich kenne die induktion bisher nurso, dass hinter dem = nur ein n steht sodass man dann n+1 nimmt. aber wie stell ich das an wenn da auch ein k ist?
kann man das nicht irgendwie nur mit dem pascallschen freieck beweisen? habe mal eine grafik erstellt die die aufgabe für n=1 und k bis 2 ausgibt:
[attach]8933[/attach]

EDIT:
Ist diese Summenformel für den ausdruck richtig:
$\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} n+k \\ k \end{pmatrix} = \begin{pmatrix} n+k+1 \\ k \end{pmatrix} \end{eqnarray*}$

Falls ja, dann ist mein Problem: wie muss ich nun vorgehen n bleibt ja konstant und wird nicht wie ich es bei der vollständigen indktion kenne n+1 genommen. wobei k sowieso erhöht wird das muss ich ja nicht k+1 schreiben.

24.10.2008, 11:42

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von bartho
Ist diese Summenformel für den ausdruck richtig:
$\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} n+k \\ k \end{pmatrix} = \begin{pmatrix} n+k+1 \\ k \end{pmatrix} \end{eqnarray*}$

Nicht ganz. Es muß heißen: $\begin{eqnarray*} \sum_{j=0}^k~\begin{pmatrix} n+j \\ j \end{pmatrix} = \begin{pmatrix} n+k+1 \\ k \end{pmatrix} \end{eqnarray*}$

In diesem Fall wählt man n beliebig, aber fest. Dann macht man die Induktion über k.

24.10.2008, 13:11

bartho

Auf diesen Beitrag antworten »

Okay soweit klar dann gehe ich wie folgt vor:
Also zeige ich im Inkrktionsanfang $\begin{eqnarray*} \sum_{i=0}^k~(\begin{pmatrix} 1+0 \\ 0 \end{pmatrix})+(\begin{pmatrix} 1+1 \\ 1 \end{pmatrix}) = \begin{pmatrix} 1+1+1 \\ 1 \end{pmatrix} = 3 \end{eqnarray*}$
Dann kommt der induktionsschritt:
$\begin{eqnarray*} \sum_{i=0}^k~ \begin{pmatrix} n+i \\ i \end{pmatrix} +\begin{pmatrix} n+k+1 \\ k+1 \end{pmatrix} = \begin{pmatrix} n+k+1 \\ k \end{pmatrix} + \begin{pmatrix} n+k+1 \\ k+1 \end{pmatrix} \end{eqnarray*}$
und am ende muss irgendwie rauskommen:
$\begin{eqnarray*} \begin{pmatrix} n+k+2 \\ k+1 \end{pmatrix} \end{eqnarray*}$

Ist das soweit richtig? Bloß wie komme ich auf das:
$\begin{eqnarray*} \begin{pmatrix} n+k+2 \\ k+1 \end{pmatrix} \end{eqnarray*}$

24.10.2008, 14:02

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von bartho
Also zeige ich im Inkrktionsanfang $\begin{eqnarray*} \sum_{i=0}^k~(\begin{pmatrix} 1+0 \\ 0 \end{pmatrix})+(\begin{pmatrix} 1+1 \\ 1 \end{pmatrix}) = \begin{pmatrix} 1+1+1 \\ 1 \end{pmatrix} = 3 \end{eqnarray*}$

Du solltest das n beliebig lassen. Jetzt ist das n ganz verschwunden. Und für welchen Wert von k machst du den Anfang?

Zitat:

Original von bartho
Ist das soweit richtig? Bloß wie komme ich auf das:
$\begin{eqnarray*} \begin{pmatrix} n+k+2 \\ k+1 \end{pmatrix} \end{eqnarray*}$

Im Prinzip ja. Kennst du die Beziehung $\begin{eqnarray*} \binom n k + \binom{n}{k+1} = \binom{n+1}{k+1} \end{eqnarray*}$ ?

Aber eigentlich ist das gar nicht dein Thread. Von daher sollten wir das Feld Martin M. überlassen. smile

25.10.2008, 15:22

Martin M.

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit

Im Prinzip ja. Kennst du die Beziehung $\begin{eqnarray*} \binom n k + \binom{n}{k+1} = \binom{n+1}{k+1} \end{eqnarray*}$ ?

Darf ich das als Axiom benutzen?

25.10.2008, 16:34

Martin M.

Auf diesen Beitrag antworten »

Mein Problem ist nähmlich, ich muss diese aufgaben in der uni abgeben und diese werden bewertet und ich weiß nicht ob ich diesen zusammenhang benutzen kann ohne ihn zu beweisen.

25.10.2008, 18:02

klarsoweit

Auf diesen Beitrag antworten »

Wenn das in der Vorlesung dran war, dann in jedem Fall. Ansonsten hilft ein Hinweis auf eine geeignete Quelle.

25.10.2008, 18:32

Martin M.

Auf diesen Beitrag antworten »

Eine solche quelle wäre was z.b.?

25.10.2008, 18:40

klarsoweit

Auf diesen Beitrag antworten »

Hast du kein Analysis-Buch? Erstaunt1