Beweis mit vollst. Induktion

29.10.2006, 21:04

kleine-Elfe

Auf diesen Beitrag antworten »

Beweis mit vollst. Induktion

Halli Hallo,
ich habe in meiner Hausübung ne Aufgabe, die ich überhaupt nicht kann. Ich hoffe, ihr könnt mir helfen.

Man beweise durch vollständige Induktion:

Für natürliche Zahlen 0 $\begin{eqnarray*} \leq \end{eqnarray*}$ m $\begin{eqnarray*} \leq \end{eqnarray*}$ n gilt

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

Dabei sind $\begin{eqnarray*} \begin{pmatrix} n \\ m \end{pmatrix} \end{eqnarray*}$ Binomialkoeffizienten.

Danke schonmal im Vorraus!

29.10.2006, 21:43

Shurakai

Auf diesen Beitrag antworten »

Wo liegt denn dein Problem? Aufgaben lösen wir hier nicht komplett, wir geben nur Tips smile

smile

Hast du schon [Workshop] Vollständige Induktion gelesen?

29.10.2006, 21:45

kleine-Elfe

Auf diesen Beitrag antworten »

ja habe ich schon. mein problem ist, dass mir der ansatz fehlt...

ich weiß, dass nur tipps gegeben werden, habe ich mir doch alles schon durchgelesen, was man hier darf und was nicht

29.10.2006, 21:45

sqrt(2)

Auf diesen Beitrag antworten »

Der IV lässt sich auf den Zusammenhang

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

der aus dem Pascalschen Dreieck bekannt ist, zurückführen. Den kannst du über die Definition des Binomialkoeffzienten beweisen.

30.10.2006, 12:24

kleine-Elfe

Auf diesen Beitrag antworten »

irgendwie verstehe ich das immer noch nicht...

30.10.2006, 12:59

klarsoweit

Auf diesen Beitrag antworten »

Dann mach doch mal den Induktionsanfang für n=m. Das solltest du schaffen. Augenzwinkern

Augenzwinkern

Anzeige

30.10.2006, 14:53

kleine-Elfe

Auf diesen Beitrag antworten »

Also ich habe jetzt:

IA: n=m

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

wahre Aussage, da: $\begin{eqnarray*} \begin{pmatrix} n \\ n \end{pmatrix} = \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow 1=1 \end{eqnarray*}$

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

wahre Aussage, da: $\begin{eqnarray*} \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} (n+1)+1 \\ (n+1)+1 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow 1=1 \end{eqnarray*}$

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

für alle m,n $\begin{eqnarray*} \in \mathbb N \end{eqnarray*}$

Stimmt das so?

30.10.2006, 14:58

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von kleine-Elfe
IS: $\begin{eqnarray*} \sum_{k=m}^n+1~ \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} (n+1)+1 \\ (n+1)+1 \end{pmatrix} \end{eqnarray*}$

Was soll das? verwirrt

verwirrt

Vermutlich meintest du:
$\begin{eqnarray*} \sum_{k=m}^{n+1}~ {k\choose m} \end{eqnarray*}$
Spalte davon den letzten Summanden ab.

EDIT: Nochmal zum Induktionsanfang: Formal richtig muß es heißen:
$\begin{eqnarray*} \sum_{k=m}^m~\begin{pmatrix} k \\ m \end{pmatrix} = {m \choose m} = 1 = \begin{pmatrix} m+1 \\ m+1 \end{pmatrix} \end{eqnarray*}$

Man setzt schließlich beim Induktionsanfang n=m für n das m ein und nicht umgekehrt.

30.10.2006, 15:02

kleine-Elfe

Auf diesen Beitrag antworten »

hää?

unglücklich

30.10.2006, 15:03

sqrt(2)

Auf diesen Beitrag antworten »

edit: Ihr seid mal wieder zu schnell für mich...

Zitat:

Original von kleine-Elfe
IS: $\begin{eqnarray*} \sum_{k=m}^n+1~ \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} (n+1)+1 \\ (n+1)+1 \end{pmatrix} \end{eqnarray*}$

wahre Aussage, da: $\begin{eqnarray*} \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} (n+1)+1 \\ (n+1)+1 \end{pmatrix} \end{eqnarray*}$

Links steht aber eine Summe und nicht nur $\begin{eqnarray*} {{n+1}\choose{n+1}} \end{eqnarray*}$ .

Ich mach mal den Anfang für dich:

$\begin{eqnarray*} \sum_{k=m}^{n+1}{k \choose m} &=& {{n+2} \choose {m+1}} \\ \sum_{k=m}^n {k \choose m} + {{n+1} \choose m} &=& {{n+2} \choose {m+1}} \quad\text{(IV anwenden)}\\ {{n+1} \choose {m+1}} + {{n+1} \choose m} &=& {{n+2} \choose {m+1}} \end{eqnarray*}$

30.10.2006, 15:07

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von kleine-Elfe
hää? unglücklich

unglücklich

Bitte etwas konkreter. Ich denke, daß zumindest der Umgang mit formalen Schreibweisen, insbesondere dem Summensymbol, keine Probleme darstellen sollten.

PS: was studierst du?

30.10.2006, 15:14

kleine-Elfe

Auf diesen Beitrag antworten »

ich verstehe es irgendwie nicht. ich kann das schon nachvollziehen, aber ich weiß nicht wie ich weiter machen soll.

30.10.2006, 15:17

klarsoweit

Auf diesen Beitrag antworten »

Was genau vestehst du denn nicht? Ich meine, wir mühen uns hier ab, aber das hilft nichts, wenn du nicht konkret dein Problem schilderst. Da können wir dir alles vorrechnen und du verstehst nur Bahnhof.

30.10.2006, 16:13

Increadable

Auf diesen Beitrag antworten »

Ich sitze gerade an der selben Aufgabe, beziehungsweisen sitze ich da schon seit einer Woche dran.
Also der Induktionsanfang ist ja soweit klar, wenn ich n=m schreibe, usw.

Aber bei mir haperts auch noch beim Induktionsschluss.

Was bedeutet dieses (IV) anwenden? Hilfe

Hilfe

Ich hab es zuerst auch wie kleine-Elfe gemacht und einfach n+1 für n eingesetzt, aber dann habe ich wieder nur eine Behauptung....
Also wie beweise ich denn das jetzt? Ist das der Anfang, wie ihn sqrt(2) gemacht hat?

30.10.2006, 17:53

klarsoweit

Auf diesen Beitrag antworten »

"(IV) anwenden" bedeutet: "hier wird nun die Induktionsvoraussetzung angewendet". Daszu sollte man bei der vollständigen Induktion wissen, was Induktionsvoraussetzung und Induktionsziel ist.

30.10.2006, 18:06

kleine-Elfe

Auf diesen Beitrag antworten »

was ist denn das induktionsziel?

30.10.2006, 18:13

Increadable

Auf diesen Beitrag antworten »

Die Induktionsvoraussetzung ist doch demnach, dass $\begin{eqnarray*} \begin{pmatrix} k \\ m \end{pmatrix} \end{eqnarray*}$ = $\begin{eqnarray*} \begin{pmatrix} n+1 \\ m+1 \end{pmatrix} \end{eqnarray*}$
Oder?
denn nur wenn das gilt, kann ich den nächsten Schritt beweisen,
das Ziel wäre demnach also, dass n = n+1 ist
[also, dass die Summe nicht nur für alle n gilt, sondern auch für alle n+1)
??

30.10.2006, 18:17

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis mit vollst. Induktion
Ein kleiner Exkurs "vollständige Induktion":

Du hast eine Aussage A(n), die du für alle n aus N oder zumindest für einen Teil davon (hier n >= m) zeigen sollst. Also schreiben wir diese Aussage mal hin:

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

Jetzt gibt es 2 Dinge zu tun:
1. Induktionsanfang
2. Induktionsschluß

zu 1: Da wird für n der erste Wert eingesetzt, für den die Aussage gelten soll. In der Regel ist das n=1, hier ist ausnahmsweise n=m.
Das Einsetzen des Anfangswertes sollte zu einer wahren Aussage führen.

zu 2: beim Induktionsschluß wird angenommen, daß die Aussage A(n) für ein n aus N bewiesen ist. Die Aussage A(n) ist nun also die Induktionsvoraussetzung. Zu zeigen ist jetzt, daß dann auch die Aussage A für die nächste Zahl (das wäre also n+1) gilt. Das heißt, es muß gezeigt werden, daß dann auch A(n+1) gilt. In Formel:
A(n) ==> A(n+1)

A(n+1) ist beim Induktionsschluß das Induktionsziel. Und da es immer gut ist, wenn man weiß, wohin die Reise gehen soll, schreiben wir das mal für diese Aufgabe hin:
$\begin{eqnarray*} A(n+1): \sum_{k=m}^{n+1}~ \begin{pmatrix} k \\ m \end{pmatrix} = \begin{pmatrix} n+1+1 \\ m+1 \end{pmatrix} \end{eqnarray*}$

Dabei habe ich einfach alle n durch n+1 ersetzt.

Noch Fragen? Hier gibt es einen Workshop:
[Workshop] Vollständige Induktion

30.10.2006, 19:01

Increadable

Auf diesen Beitrag antworten »

Das würde bis dahin bedeuten:

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

Induktionsanfang: n=m

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

mit k = m $\begin{eqnarray*} \begin{pmatrix} m \\ m \end{pmatrix} = \begin{pmatrix} m+1 \\ m+1 \end{pmatrix} \end{eqnarray*}$ wahre Aussage

Induktionsschluss: A(n) ==> A(n+1)

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

Wenn ich das jetzt noch weiter umformen will, damit ich wiederum eine wahre Aussage bekomme, muss ich ja eigentlich nur die letzte Zeile nach dem Gleichheitszeichen umformen, da $\begin{eqnarray*} \begin{pmatrix} k \\ m \end{pmatrix} \end{eqnarray*}$ immer eine wahre Aussage ergibt.

also muss ich $\begin{eqnarray*} \begin{pmatrix} n+2 \\ m+1 \end{pmatrix} \end{eqnarray*}$ das irgendwie so hinbiegen, dass da wiederum eine wahre Aussage herauskommt. Darf ich da meine Induktionsvoraussetung ganz benutzen? ALso auch, dass n = m ist?

EDIT:

Okay, n=m kann ich nicht benutzen, denk ich, weil dann eine falsche Aussage herauskommt, aber kann ich nicht das benutzen:

$\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*}$

30.10.2006, 19:24

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Increadable
Wenn ich das jetzt noch weiter umformen will, damit ich wiederum eine wahre Aussage bekomme, muss ich ja eigentlich nur die letzte Zeile nach dem Gleichheitszeichen umformen, da $\begin{eqnarray*} \begin{pmatrix} k \\ m \end{pmatrix} \end{eqnarray*}$ immer eine wahre Aussage ergibt.

Quatsch. $\begin{eqnarray*} \begin{pmatrix} k \\ m \end{pmatrix} \end{eqnarray*}$ ist keine Aussage, sondern ein Term oder Ausdruck, über den die Summe $\begin{eqnarray*} \sum_{k=m}^{n+1}~\begin{pmatrix} k \\ m \end{pmatrix} \end{eqnarray*}$ läuft.

Beim Beweis des Induktionsziels nimmt man meistens die linke Seite vom Induktionsziel und formt die so um, daß man die Induktionsvoraussetzung verwenden kann. Dann formt man weiter um, bis die rechte Seite vom Induktionsziel rauskommt.

30.10.2006, 19:31

Increadable

Auf diesen Beitrag antworten »

Ja, okay, so meint ich es ja auch (fast)

Also, kann ich doch das was ich oben editiert hab benutzen, dann ist man schon ein stück näher, denn ich habe dann schon $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

und muss nur noch den rest irgendwie...weiß nicht...

Und ich hab eine 1 zu viel...

31.10.2006, 09:29

klarsoweit

Auf diesen Beitrag antworten »

Ich weiß jetzt nicht so genau, was du meinst und wo eine 1 zuviel sein soll. Die linke Seite vom Induktionsziel lautet bekanntlich:

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

Jetzt spaltest du aus der Summe den letzten Summanden (also den für k=n+1) ab. Was hast du dann?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »