Fragen zu [Workshop]-[Vollständige Induktion]

14.02.2004, 19:25

jama

Fragen zu [Workshop]-[Vollständige Induktion]

Hier könnt Ihr Fragen, Kritik und Wünsche zum Workshop "Vollständige Induktion" ( http://matheboard.de/thread.php?threadid=1533 ) äußern. Vielen Dank an Andy für seine Mühe und an Johko für seine Ergänzung!

Gruß,

Jama

Link zum Workshop: http://matheboard.de/thread.php?threadid=1533

23.03.2004, 12:12

Fauphi

Auf diesen Beitrag antworten »

Hi also ich hätte da mal ne Frage zu der Induktion
Und zwar wie komme ich ganz am Anfang auf die Summenformel?
Den Rest kapier ich schon nur dieser Anfang will mir Einfach nicht in den Kopf.

Mal ne Aufgabe:

1/1*2 + 1/2*3 + 1/3*4 + 1/4*5 + ... + 1/n*(n+1)

Dazu muss man jetzt ne Vermutung über ne Summenformel aufstellen und diese dann mit vollst. Induktion beweisen.

Aber wie komme ich auf die Summenformel??????

23.03.2004, 12:26

Marcyman

Auf diesen Beitrag antworten »

Rechne doch einfach mal die ersten 5 Glieder deiner Reihe aus: 1/2, 2/3, 3/4, 4/5, 5/6... man kommt so schnell zu einer Vermutung (bei einfachen Aufgaben wie dieser), z.B. n/(n+1) als Summe der Reihe. Das kannste dann mit voll. Ind. zeigen.

08.04.2004, 20:41

Selina999

Auf diesen Beitrag antworten »

Induktion mit zwei Summen
Ich schlag mich schon ewig mit diesem Induktionsbeispiel herum und komm nicht drauf wie es geht! :P Irgendwie scheint es so aehnlich zu sein, wie die Induktion mit zwei Summen.

$\begin{eqnarray*} \frac{1}{n+1} \cdot \sum_{i=1}^n~\left( \frac{1}{n} + i^2 \cdot ((i - 1)!) \right) = n! \end{eqnarray*}$

bitte
Hilfe

08.04.2004, 23:31

Ben Sisko

Auf diesen Beitrag antworten »

RE: Induktion mit zwei Summen
Wo genau ist denn dein Problem? Hast du schon versucht das mit Induktion zu beweisen? Wo hakt´s? Hast du nen Ansatz?

Gruß vom Ben

09.04.2004, 13:24

Selina999

Auf diesen Beitrag antworten »

RE: Induktion mit zwei Summen
Mein Problem liegt beim Induktionsschluss $\begin{eqnarray*} n \Rightarrow (n + 1) \end{eqnarray*}$
Das Problem ist der Teil vor dem Summenzeichen: $\begin{eqnarray*} \frac{1}{n+1} \end{eqnarray*}$ da ich dadurch nicht mehr n! fuer den Teil: $\begin{eqnarray*} \sum_{i=1}^n~ \left( \frac{1}{n} + i^2 \cdot ((i - 1)! \right) \end{eqnarray*}$ einsetzen kann.
Ich hab mir dazu folgedes ueberlegt, glaube aber, dass das nicht stimmen kann. Irgendwie muss es fuer diesen Fall eine allgemeinere Vorgehensweise geben.

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

Ich habe den n! Teil mit (n+1) multipliziert, da bei einer Erweiterung auf (n+1)
die ganze Gleichung durch (n+2) dividiert wird. Ausserdem habe ich da $\begin{eqnarray*} \frac{1}{n} \end{eqnarray*}$ innerhalb des Summenzeichens insgesamt 1 ergibt, 1 abgezogen und beim erweiterten Teil dazuaddiert.

Hoffentlich hab ich mich einigermassen verstaendlich ausgedrueckt.

15.05.2004, 15:12

Irrlicht

Auf diesen Beitrag antworten »

Das zweite Beispiel von DeakAndy enthält einen logischen Fehler. Siehe dazu die Diskussion im Thread vollständige Induktion in Höhere Mathematik.

26.05.2004, 03:23

WebFritzi

Auf diesen Beitrag antworten »

Ich finde es nicht so schön, dass das Prinzip der vollständigen Induktion in dem Workshop-Thread überhaupt nicht erklärt wird. Klar - Beispiele sind super. Aber jemand, der wirklich beweisen will, will natürlich auch wissen, WARUM das Beweisschema funktioniert.

01.06.2004, 23:18

Mathespezialschüler

Auf diesen Beitrag antworten »

@WebFritzi

Ich habe einen einzigen Induktionsbeweis in einem Buch gesehen und sofort verstanden, was man da macht.

@all
Aber ein wenig was erklärt haben, möchte ich schon noch. Ich habe Induktion ungefähr so verstanden:
Hat man in einer Menge für eine Teilmenge eine Eigenschaft/Satz etc. bewiesen, so heißt Induktion das Beweisen für die gesamte Menge durch Schließen darauf mithilfe der Eigenaschaft schon bewiesenen Eigenaschaft für die Teilmenge.

Is sicherlich nich so toll ausgedrückt, aber ich habs mir halt mal wieder selbst erarbeitet.
Und noch ne Frage:
Warum heißt es vollständige Induktion?? Gibt es auch eine unvollständige??

@Deakandy

Zitat:

Original von Deakandy
1. Beispiel
Für alle $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ gilt: $\begin{eqnarray*} \sum_{k=1}^n~k = 1+2+...+n = \frac {n \cdot (n+1)} {2} \end{eqnarray*}$

Beweis: Wir zeigen die Aussage durch Induktion nach n
Induktionsanfang (IA): Man zeige, dass n=1 gilt
$\begin{eqnarray*} \sum_{k=1}^1~k = 1 = \frac {1 \cdot (1+1)} {2} \end{eqnarray*}$
Induktionsvorraussetzung (IV): Es gelte für ein $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$
Induktionsschluss (IS): Man schließe von n auf n+1 $\begin{eqnarray*} ( n \rightarrow n + 1) \end{eqnarray*}$
Das heißt man hat zu zeigen, das folgendes gilt:
$\begin{eqnarray*} \sum_{k=1}^{n+1}~k = \frac {(n+1) \cdot (n+1+1)} {2} =\frac {(n+1) \cdot (n+2)} {2} = \frac {n^2+3n+2} {2} \end{eqnarray*}$
Nun geht man wie folgt vor:
$\begin{eqnarray*} \sum_{k=1}^{n+1}~k = \left( \sum_{k=1}^n~k \right) + (n+1) \end{eqnarray*}$
In diesem Schritt holt man lediglich den letzten Summanden raus.
Nun kann man die Induktionsvorraussetzung anwenden
Man setzt für die Summe
$\begin{eqnarray*} \sum_{k=1}^n~k \end{eqnarray*}$ genau das ein, was aus der Voraussetzung gilt und zwar $\begin{eqnarray*} \frac {n \cdot (n+1)} {2} \end{eqnarray*}$
Eingesetzt ergibt sich dann folgender Term:
$\begin{eqnarray*} \frac {n \cdot (n+1)} {2} + n + 1 \end{eqnarray*}$
Diese Summe bringt man geschickt auf einen Bruch durch Erweitern
$\begin{eqnarray*} \frac {n \cdot (n+1)} {2} + \frac {2 \cdot (n+1)} {2} \end{eqnarray*}$
$\begin{eqnarray*} \frac {(n^2+n)+(2n+2)} {2} \end{eqnarray*}$
$\begin{eqnarray*} \frac {n^2+3n+2} {2} \end{eqnarray*}$
Und genau das war zu zeigen.
Man hat nun genau die Form, wie sie unter dem Induktionsschluss stehen hat.
Die Behauptung ist dem Prinzip der vollständigen Induktion bewiesen. q.e.d.

Ich hab mal ne Frage: Wenn man schon bei

$\begin{eqnarray*} \sum_{k=1}^{n+1}~k =\frac {(n+1) \cdot (n+2)} {2} \end{eqnarray*}$

ist, warum ist man dann nicht schon fertig?? Kann man nicht einfach substituieren:

(n+1)=z ; (n+2)=z+1

Und daraus folgt

$\begin{eqnarray*} \sum_{k=1}^{z}~k =\frac {(z) \cdot (z+1)} {2} \end{eqnarray*}$

Warum muss man da beides beweisen??

Ich denke nämlich, dass ich einen Beweis gefunden habe, wo das nicht so ist. Ich hab in "ABITUR WISSEN - Mathematik" von R. Brauner und F. Geiß folgendes gefunden:

Zitat:

Satz 7: Die Funktion $\begin{eqnarray*} f:\ x \to x^n ,\ x \in \mathbb R ,\ n \in \mathbb N \end{eqnarray*}$ hat die Ableitungsfunktion $\begin{eqnarray*} f' :\ x \to n \cdot \ x^{n - 1},\ x \in \mathbb R \end{eqnarray*}$ .

Den Beweis führen wir durch vollständige Induktion.
I) Die Regel ist verankert für n = 1, 2.
II) Schluss von n auf (n+1) : Zur Funktion $\begin{eqnarray*} f_n :\ x \to x^n \end{eqnarray*}$ gehöre die Ableitungsfunktion $\begin{eqnarray*} f'_n :\ x \to n \cdot x^{n - 1}\ \end{eqnarray*}$ .
Nun ist $\begin{eqnarray*} f_{n\ +\ 1} : \ x \to x^{n + 1}\ = x \cdot x^n \end{eqnarray*}$ . Das rechts stehende Produkt kann nach dem Satz 6 und gemäß der Induktionsannahme differenziert werden. Man erhält
$\begin{eqnarray*} f'_{n\ +\ 1} :\ x \to x^{n + 1} = x^n + x \cdot n \cdot x^{n - 1} = x^n(1 + n) \end{eqnarray*}$
Damit ist gezeigt, dass die Potenzregel für den Exponenten n + 1 gilt, wenn sie für den Exponenten n richtig war. Aus I) und II) folgt somit die Gültigkeit der Differenziationsregel für alle Potenzfunktionen, deren Exponenten natürliche Zahlen sind.

Jetzt noch Informationen dazu:
Für 1 und 2 wurde es vorher bereits mithilfe des Differentialquotienten bewiesen. Der Satz 6 ist folgender:

Zitat:

Wenn die Funktion $\begin{eqnarray*} f :\ x \to f(x) \end{eqnarray*}$ differenzierbar ist in D, dann ist auch die Funktion $\begin{eqnarray*} g :\ x \to x \cdot f(x) \end{eqnarray*}$ differenzierbar in D und es gilt $\begin{eqnarray*} g' = f(x) + xf'(x) \end{eqnarray*}$ .

Dafür gibts nen Beweis, den ich auch verstanden habe, deswegen will ich den nicht posten.

Meine Hauptfrage ist dazu also, wie schon oben gesagt:

Wenn man schon bei

$\begin{eqnarray*} \sum_{k=1}^{n+1}~k =\frac {(n+1) \cdot (n+2)} {2} \end{eqnarray*}$

ist, warum ist man dann nicht schon fertig?? Kann man nicht einfach substituieren:

(n+1)=z ; (n+2)=z+1

Und daraus folgt

$\begin{eqnarray*} \sum_{k=1}^{z}~k =\frac {(z) \cdot (z+1)} {2} \end{eqnarray*}$

Warum muss man da beides beweisen bzw. das, was Deakandy da auch noch gemacht hat??

Bei dem Beweis, den ich zitiert habe, hat man ja eigentlich das gemacht, was ich hier jetzt auch gemacht habe, also nicht die Fassung von Deakandy. Das is alles voll verwirrend verwirrt

.

Danke für alle Antworten!!

Und noch was @Deakandy
Wär nett, wenn du dir mal folgenden Thread durchliest.

http://www.matheboard.de/thread.php?sid=&postid=38670#post38670

Ich hab ja in dem Workshop den Beweis gesehen, aber du hast gesagt, dafür bräuchte man ne Menge anderes Wissen. Ich verstehe den grad auch irgendwie nicht. Kann ich den schon verstehen bzw. welches Wissen meinst du denn, dass man es braucht??

01.06.2004, 23:24

Ben Sisko

Auf diesen Beitrag antworten »

Doch, da wäre man schon fertig. Allerdings sehe ich das

Zitat:

Original von Mathespezialschüler
$\begin{eqnarray*} \sum_{k=1}^{n+1}~k =\frac {(n+1) \cdot (n+2)} {2} \end{eqnarray*}$

bei Deakandy nirgendwo, ausser in der Behauptung.

Edit: Hast du das vielleicht überlesen?

Zitat:

Original von Deakandy
Das heißt man hat zu zeigen, das folgendes gilt:
$\begin{eqnarray*} \sum_{k=1}^{n+1}~k = \frac {(n+1) \cdot (n+1+1)} {2} =\frac {(n+1) \cdot (n+2)} {2} = \frac {n^2+3n+2} {2} \end{eqnarray*}$

01.06.2004, 23:28

Deakandy

Auf diesen Beitrag antworten »

Das ist an sich richtig
Nur gibt es andere beispiele, da kommste nicht einfach per Faktorisierung auf die behauptung zurück
Es ist nicht falsch auch wenn VLL ein wenig umständlich,..., jedoch ausführlich

01.06.2004, 23:31

Mathespezialschüler

Auf diesen Beitrag antworten »

Ja, aber wenn

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

dann gilt doch

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

oder nicht?? Wäre das nicht das Schema von dem Beweis, den ich zitiert habe??

01.06.2004, 23:34

Ben Sisko

Auf diesen Beitrag antworten »

Ja, natürlich, wenn du das bewiesen hast, bist du fertig.
Dein Post hört sich so an, als hätte Deakandy das bewiesen und danach noch weitergemacht. Das sehe ich aber nicht.

Gruß vom Ben

01.06.2004, 23:44

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von Ben Sisko
Ja, natürlich, wenn du das bewiesen hast, bist du fertig.
Dein Post hört sich so an, als hätte Deakandy das bewiesen und danach noch weitergemacht. Das sehe ich aber nicht.

Gruß vom Ben

Habe ich das mit meinem letzten Post nicht schon bewiesen oder hab ich da jetzt nur die Regel angewandt?? verwirrt

edit: Ok, ich glaub, ich habs verstanden. Danke! :] Mir ist aufgefallen, dass das, was ich in meinem letzten Post gemacht habe, ja genau die Benutzung der Formel für (n+1) ist, obwohl ich das gar nicht bewiesen habe. Dann habe ich mir überlegt, wie ich das beweisen könnte und bin darauf gekommen, dass man ja bis zum Summanden n die Formel anwenden kann. Dann habe ich mir aber die Lösung aus dem Workshop nochmal angeguckt und sie dann zum ersten Mal richtig verstanden, denn ich habe festgestellt, dass das, was ich gemacht habe, genau das ist, was Deakandy in seinem Workshop gemacht hat. Das Problem war wieder das \sum, was mich noch irritiert, da ich damit noch nicht so oft gearbeitet habe. Das stört mich einfach oft. Deswegen habe ichs vorher nicht voll verstanden. Naja, auf jeden Fall (hoffentlich) habe ichs verstanden. Aber das wäre ja dann doch die gleiche Vorgehensweise wie in dem zitierten Beweis(, was ich ja anfangs nicht dachte) oder?

Aber dann verstehe ich Deakandys Aussage wiederum nicht, denn er hat ja geschrieben, dass das, was ich eben in meinem letzt Post geschrieben habe und was sich ja nun als falsch herausgestellt hat, richtig ist.

Zitat:

Original von Deakandy

Das ist an sich richtig
Nur gibt es andere beispiele, da kommste nicht einfach per Faktorisierung auf die behauptung zurück
Es ist nicht falsch auch wenn VLL ein wenig umständlich,..., jedoch ausführlich

Und noch eine Anmerkung:
In deinem Beweis kommst du irgendwann auf

(1) $\begin{eqnarray*} \frac {n \cdot (n+1)} {2} + \frac {2 \cdot (n+1)} {2} \end{eqnarray*}$

Du willst aber unbedingt auf

(2) $\begin{eqnarray*} \frac {n^2+3n+2} {2} \end{eqnarray*}$

und multpilizierst erst aus und addierst dann. Es sind zwar nur wenige Sekunden, aber du kannst bei (1) einfach ausklammern und bist sofort fertig:

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

Wie gesagt, is nur minimales Zeiteinsparen.

Und nochmal zu den anderen beiden Fragen:

1.

Zitat:

Original von Mathespezialschüler

@all
Aber ein wenig was erklärt haben, möchte ich schon noch. Ich habe Induktion ungefähr so verstanden:
Hat man in einer Menge für eine Teilmenge eine Eigenschaft/Satz etc. bewiesen, so heißt Induktion das Beweisen für die gesamte Menge durch Schließen darauf mithilfe der Eigenaschaft schon bewiesenen Eigenaschaft für die Teilmenge.

Is sicherlich nich so toll ausgedrückt, aber ich habs mir halt mal wieder selbst erarbeitet.
Und noch ne Frage:
Warum heißt es vollständige Induktion?? Gibt es auch eine unvollständige??

Zitat:

Original von Mathespezialschüler

Und noch was @Deakandy
Wär nett, wenn du dir mal folgenden Thread durchliest.

Beweis fürs Pascalsche Dreieck

Ich hab ja in dem Workshop den Beweis gesehen, aber du hast gesagt, dafür bräuchte man ne Menge anderes Wissen. Ich verstehe den grad auch irgendwie nicht. Kann ich den schon verstehen bzw. welches Wissen meinst du denn, dass man es braucht??

Kann mir jemand noch diese beiden Fragen beantworten?! Danke euch!!! :]

02.06.2004, 00:09

Ben Sisko

Auf diesen Beitrag antworten »

Wenn du es jetzt verstanden hast, dann lass uns die Diskussion beenden, das war glaub ich alles ein grosses Mißverständnis.

Damit es auch alle anderen verstehen: Im Induktionsbeweis, beim Induktionsschritt von n nach (n+1) darf man die Behauptung (also das was man beweisen will) für n benutzen, daraus muss man dann die Behauptung für (n+1) folgern.

Gruß vom Ben

02.06.2004, 00:54

Deakandy

Auf diesen Beitrag antworten »

Naja also für euch interessierenden weiss ich es auch nciht
Es ist einfach der Fakt
Der Indexverschiebung
War da auch Bernoulli drin...
?
Augenzwinkern

keinen bock nachzuschauen
Es ist einfach ne Menge Wissen drin
binomilakoeffizient und sowas braucht man z.B. nicht für jede Aufgabe ne...
Naja ihr seid klug genug und könnt den Satz, dass man ne Menge Wissen braucht weg lassen smile

Andy

02.06.2004, 01:06

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von Deakandy
Naja also für euch interessierenden weiss ich es auch nciht
Es ist einfach der Fakt
Der Indexverschiebung
War da auch Bernoulli drin...
?
Augenzwinkern

Andy

Man weiß zwar jetzt nicht genau, wovon du sprichst, aber ich denke mal, es geht um den Beweis des Binomischen Satzes.? Wie gesagt, Binomialkoeffizienten kann ich zwar grundsätzlich, aber hab ich noch so gut wie nie angewandt und für das Summenzeichen brauch ich auch immer ne Weile bis ich verstanden habe, welche Summe gemeint ist. Aber wenn ich es verstehen kann, dann is ja schön, ich versuch das dann morgen (bzw. heute *g*). Diese Indexverschiebung, ist das nicht ähnlich einer Substitution?? Bernoulli habe ich übrigens bis jetzt nur bei der Flugphysik gehört, auch schon gehört, dass der sich mit Mathe beschäftigt hat, aber halt nich, was genau. Was du da jetzt meinst, ist mir also nicht bekannt, falls das wichtig ist.

Naja, auf jeden Fall erstmal danke für die Hilfe euch beiden!! :] :] Prost

02.06.2004, 11:18

Ben Sisko

Auf diesen Beitrag antworten »

Die Bernoullis waren sogar ne ganze (Mathematiker-)Sippe soweit ich weiß, muss also nicht derselbe gewesen sein, von dem du gehört hast.

Gruß vom Ben

02.06.2004, 18:27

Guevara

Auf diesen Beitrag antworten »

wie berechnet man die ersten n Quadratzahlen.

z.B. 1^2+2^2+3^2+4^2 wenn n=4

02.06.2004, 18:40

Mathespezialschüler

Auf diesen Beitrag antworten »

Die Formel ist

(n*(n+1)(2*n+1))/6

Steht auch in jeder Formelsammlung. Für 4:

(4*(4+1)(2*4+1))/6

@Deakandy
bzw. "1." @all

Zitat:

Original von Mathespezialschüler

Aber dann verstehe ich Deakandys Aussage wiederum nicht, denn er hat ja geschrieben, dass das, was ich eben in meinem letzt Post geschrieben habe und was sich ja nun als falsch herausgestellt hat, richtig ist.

Zitat:

02.06.2004, 22:00

SirJective

Auf diesen Beitrag antworten »

Induktion ist eine logische Schlussregel: "ein Schluss vom Besonderen auf das Allgemeine."

Sie besagt, dass etwas, was für einige Objekte einer bestimmten Art gilt, auch für alle anderen Objekte dieser Art gelten muss. Das ist aber logisch nicht notwendig der Fall.

Wenn man nachgeprüft hat, dass das der Ausdruck
n^2 + n + 41
für die Zahlen n = - 37, -36, ..., -1, 0, 1, ..., 37 stets eine Primzahl ergibt, dann könnte man auf die Vermutung kommen, dass das für alle ganzen Zahlen n gilt. Dies ist ein induktiver Schluss.
Aber diese Vermutung ist falsch. Für n=40 ist 40^2 + 40 + 41 = 41^2 keine Primzahl.

Ganz im Gegensatz dazu ist die vollständige Induktion eine Schlussregel, die allgemein richtig ist. Sie ist - genau genommen - eine deduktive Schlussregel: "Ein Schluss vom Allgemeinen auf das Besondere".

Gruss,
SirJective

03.06.2004, 01:10

Ben Sisko

Auf diesen Beitrag antworten »

Die Induktion kommt also quasi im Beweis zum Tragen (Schliessen von der Induktionsverankerung (dem besonderen Fall) auf den allgemeinen Fall im Induktionsschritt) und die Deduktion dann bei der Anwendung des Bewiesenen (Anwenden der allgemeinen Regel auf den besonderen Fall).

Gruß vom Ben

03.06.2004, 01:12

Mathespezialschüler

Auf diesen Beitrag antworten »

ok, danke euch beiden :] Wink

03.06.2004, 11:14

Guevara

Auf diesen Beitrag antworten »

Ich habe gerade die Formel 2^1+2^2+2^3+2^4...+2^n= (2*2^n)-2 hergeleitet indem ich ein LGS erstellt habe. Dann bewies ich es mit der Volständigen Induktion.
2*2^n -2+2^(n+1) =2*2^(n+1) -2
Dabei ist mir aufgefallen dass die Formel auch (2*2^n)-1000 heißen könnte und ich hätte sie trotzdem bewießen.
Oder wie oder was oder warum?

03.06.2004, 11:17

Ben Sisko

Auf diesen Beitrag antworten »

Zitat:

Original von Guevara
2^1+2^2+2^3+2^4...+2^n= 2*2^n-2

Steht rechts $\begin{eqnarray*} 2 \cdot 2^{n-2} \end{eqnarray*}$ ?

03.06.2004, 11:20

Mathespezialschüler

Auf diesen Beitrag antworten »

Ne!

$\begin{eqnarray*} 2 \cdot 2^n-2 \end{eqnarray*}$

03.06.2004, 11:25

Ben Sisko

Auf diesen Beitrag antworten »

OK, vielleicht sollte ich erst denken und dann schreiben.

@Guevara: Mit $\begin{eqnarray*} 2^{n+1}-1000 \end{eqnarray*}$ könntest du das nicht beweisen, denn da funktioniert schon die Induktionsverankerung nicht.

Gruß vom Ben

03.06.2004, 11:29

Mathespezialschüler

Auf diesen Beitrag antworten »

Vielleicht wollte er aber auch nur fragen, ob man es nicht auf dem gleichen Weg machen könnte, wenn die Formel dafür 2*2^n-1000 heißen würde. Also, dass sozusagen das Absolutglied für den Beweis völlig egal ist.

03.06.2004, 11:38

Guevara

Auf diesen Beitrag antworten »

2^0+2^1+2^3...2^n= 2*2^n-1. Das lässt sich auch beweißen. Aber woher weiß die vollständige Induktion welche der beiden Formeln bewießen weden soll. Es kann nur bewießen werden
dass -2+2*2^n+2^(n+1) =-2 +2*2(n+1). Aber wenn man zusätlich zum Beispiel 2*2^3-2 = 2+4+8 angibt müsste die Formel doch bewießen sein.

03.06.2004, 11:44

Mathespezialschüler

Auf diesen Beitrag antworten »

Das lässt sich nicht beweisen, da wie BenSisko schon gesagt hat, die induktionsannahme falsch ist. Du musst ja erstmal ein n finden, für das diese Formel gilt und erst dann kannst du von diesem n auf (n+1) schließen. Hier findest du aber kein n für das diese Formel gilt, weil sie ja nunmal falsch ist.

03.06.2004, 14:08

SirJective

Auf diesen Beitrag antworten »

Zitat:

Original von Ben Sisko
Die Induktion kommt also quasi im Beweis zum Tragen (Schliessen von der Induktionsverankerung (dem besonderen Fall) auf den allgemeinen Fall im Induktionsschritt) und die Deduktion dann bei der Anwendung des Bewiesenen (Anwenden der allgemeinen Regel auf den besonderen Fall).

Gruß vom Ben

Nicht ganz. Auch der Schluss von n auf n+1 ist ja ein deduktiver Schritt: Von einem Spezialfall auf den naechsten Spezialfall.

Ohne das Prinzip der vollstaendigen Induktion kann ich nur sagen: Die Behauptung gilt fuer alle natuerlichen Zahlen, fuer die ich diesen Schluss durchgefuehrt habe.

Das Prinzip der vollstaendigen Induktion liefert einem die Aussage, dass die Behauptung fuer alle natuerlichen Zahlen gilt, fuer die ich diesen Schluss fuehren koennte (genug Zeit und Papier vorausgesetzt).

Auch die Anwendung der allgemeinen Induktionsregel auf die spezielle Induktionsregel, mit der ich meine Behauptung beweisen will, ist ein deduktiver Schritt.
Also der Uebergang von der allgemeinen Induktionsregel

Fuer jede Eigenschaft(*) P gilt: $\begin{eqnarray*} (P(0) \wedge \forall n \geq 0: (P(n) \Rightarrow P(n+1))) \Rightarrow \forall n\geq 0: P(n) \end{eqnarray*}$ , wobei alle Zahlen natuerliche Zahlen sind,

auf den Spezialfall

Fuer die Eigenschaft $\begin{eqnarray*} p(n) := \left( \sum_{k=0}^{n} (2k+1) = (n+1)^2 \right) \end{eqnarray*}$ gilt: $\begin{eqnarray*} (p(0) \wedge \forall n\geq 0: (p(n) \Rightarrow p(n+1))) \Rightarrow \forall n: p(n) \end{eqnarray*}$

Aus der allgemeinen Induktionsregel ist (auf deduktivem Weg) eine Regel geworden, die fuer eine spezielle Eigenschaft gilt. Jetzt muss man nur noch die Voraussetzung dieser speziellen Regel beweisen, um zu dem (deduktiven) Schluss zu kommen, dass die Eigenschaft p(n) fuer alle natuerlichen Zahlen n gilt.

Die gesamte vollstaendige Induktion mit all ihren Teilschritten ist also formal deduktiv. Induktiv ist lediglich das Aufstellen der Vermutung, dass p(n) fuer jede natuerliche Zahl n gilt. Der Beweis dieser Vermutung ist rein deduktiv (und muss es sein, um als Beweis zu gelten).

Gruss,
SirJective

(*): Der Begriff "Eigenschaft" muss dabei natuerlich noch definiert werden. Was wir hier vor allem brauchen ist, dass eine "Eigenschaft" fuer jede natuerliche Zahl entweder gilt oder nicht gilt.

03.06.2004, 14:41

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von Deakandy
Nun setzt man die Induktionvoraussetzung ein
$\begin{eqnarray*} (n+1)^3 + \left( \sum_{k=1}^n~k \right)^2 \end{eqnarray*}$ . Nun ein kleiner Trick, indem man den Satz von Gauß anwendet
$\begin{eqnarray*} (n+1)^3 +(\frac {n\cdot (n+1)} {2})^2 = (n+1)^3 + \frac {n^2 \cdot (n+1)^2} {4} = .......... = "\frac {n^4+6n^3+13n^2+12n+4} {4}" \end{eqnarray*}$ . Nun hat man eine Gleichung mit einer Unbekannten und müsste diese wieder auf die Form $\begin{eqnarray*} \left( \sum_{k=1}^{n+1}~k \right)^2 \end{eqnarray*}$ bringen.
Dies scheint jedoch nicht direkt ins Augenlicht zu fallen und deshalb räumt man das Feld von hinten auf und versucht $\begin{eqnarray*} \left( \sum_{k=1}^{n+1}~k \right)^2 \end{eqnarray*}$ auf die in Anführungsstriche gesetzte Form zu bringen.
$\begin{eqnarray*} \left( \sum_{k=1}^{n+1}~k \right)^2 = \left( \frac {(n+1) \cdot (n+2)} {2} \right)^2 = \frac {(n+1)^2\cdot (n+2)^2} {4} = ......... =\frac {n^4+6n^3+13n^2+12n+4} {4} \end{eqnarray*}$
Ich habe die Zwischenschritte mal nicht hingeschrieben, da es sich lediglich um algebraische Umformungen handelt und diese von jedem selber nachgerechnet werden können.

Die behauptung folgt per induktionsprinzip q.e.d.

Du machst es dir aber auch oft kompliziert! Bei der Gaußformel hättest du schon ausklammern können, jetzt hast du auch erst alles ausmultipliziert. Hast du ausklammern verlernt?? Augenzwinkern

Du hättest es einfach so machen können:

$\begin{eqnarray*} (n+1)^3 + \left( \frac {n\cdot (n+1)} {2} \right)^2 = (n+1)^3 + \frac {n^2 \cdot (n+1)^2} {4} = (n+1)^2 \left( n+1+\frac{n^2}{4} \right) = \frac{(n+1)^2(n^2+4n+4)}{4}= \frac{(n+1)^2(n+2)^2}{4} \end{eqnarray*}$

$\begin{eqnarray*} \left( \sum_{k=1}^{n+1}~k \right)^2 = \left( \frac {(n+1) \cdot (n+2)} {2} \right)^2 = \frac {(n+1)^2 \cdot (n+2)^2} {4} \end{eqnarray*}$

Geht mMn viel schneller, als da erst riesig auszumultiplizieren und dann noch "das Feld von hinten aufzuräumen". Augenzwinkern

03.06.2004, 23:23

Ben Sisko

Auf diesen Beitrag antworten »

Zitat:

Original von SirJective
Nicht ganz. Auch der Schluss von n auf n+1 ist ja ein deduktiver Schritt: Von einem Spezialfall auf den naechsten Spezialfall.

Ist eine Deduktion nicht ein Schluss von einem allgemeinen Fall auf einen Spezialfall?

Davon abgesehen: Ist das noch ein Spezialfall, wenn n beliebig ist?

Gruß vom Ben

04.06.2004, 00:50

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von Deakandy
$\begin{eqnarray*} (a+b)^{n+1}=(a+b) \cdot (a+b)^n=(a+b) \cdot \sum_{k=0}^n~\begin{pmatrix} n \\ k \end{pmatrix} a^k b^{n-k}= \end{eqnarray*}$
$\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} 0 \\ k \end{pmatrix} a^{k+1} b^{n-k}+\sum_{k=0}^n~\begin{pmatrix} 0 \\ k \end{pmatrix} a^k b^{n+1-k} \end{eqnarray*}$

Warum hast du denn da eine 0 zu stehen? Muss an die Stelle der 0 im Binomialkoeffizienten nich das n?? verwirrt

Und in den letzten drei zahlen hast du dann ein i, obwohl du die Indexverschiebung mit j gemacht hast. Die meisten irritierts wahrscheinlich nich, aber mich das mit der 0 schon.

16.07.2004, 20:39

Auf diesen Beitrag antworten »

der letzte Beitrag ist zwar schon etwas her,aber eine kleine Frage zu dem dritten Beispiel hätte ich da noch (hab auch Deakandy gefragt,aber der scheint momentan etwas beschäftigt zu sein)

und zwar steht dort folgendes:

2n+2 über n+1= (2n+2)(2n+1)(2n)! (Zähler)

(n+1)^2 * (n!)^2 (Nenner)

oben wurde wohl mit n(n-1) etc gearbeitet,aber wie ist es unten im Nenner?

16.07.2004, 20:55

Mathespezialschüler

Auf diesen Beitrag antworten »

Oben wurde mit (2n+2)! gearbeitet! Ich hoffe, du kennst folgende Definition:

$\begin{eqnarray*} \begin{pmatrix} z \\ k \end{pmatrix} = \frac{z!}{k!\cdot (z-k)!} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \begin{pmatrix} 2n+2 \\ n+1 \end{pmatrix} = \frac{(2n+2)!}{(n+1)!\cdot (2n+2-(n+1))!} = \frac{(2n+2)(2n+1)\cdot 2n!}{(n+1)!\cdot (n+1)!} = \frac{(2n+2)(2n+1)\cdot 2n!}{(n+1)\cdot n!\cdot (n+1)\cdot n!} = \frac{(2n+2)(2n+1)\cdot 2n!}{(n+1)^2\cdot (n!)^2} \end{eqnarray*}$

Und das wars schon! Augenzwinkern

16.07.2004, 21:02

Auf diesen Beitrag antworten »

arrrrrrrrrgggggg,die Minus Klammer!!!!!!!!!!!!!!!!!!!!!
verwirrt

Wenn man so vertieft ist,vergisst man die leichtesten Dinge,die man wissen MÜSSTE!

Vielen Dank für die ausführliche Schreibweise MSS smile

19.07.2004, 12:27

Mazze

Auf diesen Beitrag antworten »

Ich haette da uebrigens auch noch eine Interessante Aufgabe zum Thema Induktion, die ist von unserer Mafi Klausur

Sei $\begin{eqnarray*} x_n \end{eqnarray*}$ eine Folge und wie folgt definiert

$\begin{eqnarray*} x_{n+1} = 1 + \frac{2}{x_n}\|x_0 \in [\frac{3}{2},4] \end{eqnarray*}$

Zu zeigen ist

fuer jedes n in N gelten folgende Aussagen

$\begin{eqnarray*} x_n \in [\frac{3}{2},4] \end{eqnarray*}$

und

$\begin{eqnarray*} | x_{n+1} - 2 | <= \frac{2}{3}*|x_n - 2| \end{eqnarray*}$

Ich werde den Beweis mal wenn ich Zeit hab genau hinschreiben, aber ihr koennt euch ja auch mal Gedanken machen, ich finde das is ne recht schoene Aufgabe Augenzwinkern

edit

So die erste Aussage zu beweisen ist relativ einfach, zu zeigen also ist das

$\begin{eqnarray*} x_n \in [\frac{3}{2},4] \end{eqnarray*}$

Induktionsanfang für n = 0: (die Mathematiker betrachten die 0 nich als natürliche Zahl weswegen der Beweis analog für n = 1 wäre, da x_0 == x_1 wäre)

zz.: $\begin{eqnarray*} x_0 \in [\frac{3}{2},4] \end{eqnarray*}$

gilt nach Vorraussetzung

Induktionsvorrausetzung:

$\begin{eqnarray*} \exists n \in N \| x_n \in [\frac{3}{2},4] \end{eqnarray*}$

Induktionsbehauptung: $\begin{eqnarray*} x_{n+1} \in [\frac{3}{2},4] \end{eqnarray*}$

$\begin{eqnarray*} x_{n+1} = 1 + \frac{2}{x_n} \end{eqnarray*}$

Nach IV gilt das ein $\begin{eqnarray*} x_n \end{eqnarray*}$ existiert mit $\begin{eqnarray*} x_n \in [\frac{3}{2},4] \end{eqnarray*}$

Es gilt also

$\begin{eqnarray*} 1 + 2*\frac{1}{4} <= 1+ 2*\frac{1}{x_n} <= 1 + 2*\frac{2}{3} \end{eqnarray*}$

<=>

$\begin{eqnarray*} 1 + \frac{1}{2} <= 1+ \frac{2}{x_n} <= 1 + 2*\frac{4}{3} \end{eqnarray*}$

<=>

$\begin{eqnarray*} \frac{3}{2} <= x_{n+1} <= \frac{7}{3} \end{eqnarray*}$

<=>

$\begin{eqnarray*} \frac{3}{2} <= x_{n+1} <= \frac{7}{3} < \frac{12}{3} = 4 \end{eqnarray*}$

=>

$\begin{eqnarray*} x_{n+1} \in [\frac{3}{2},4] \end{eqnarray*}$

21.10.2004, 17:09

Gast

Auf diesen Beitrag antworten »

RE: Übungen zur Vollständigen Induktion

Zitat:

Original von Deakandy
Übungen zu diesem Beispiel
Ein anderer Satz, der analog zum ersten Typen bewiesen werden kann, ist die Geometrische Summenformel
Für $\begin{eqnarray*} n \in \mathbb N^* \end{eqnarray*}$ und jede reelle (komplexe) Zahl $\begin{eqnarray*} q \neq 1 \end{eqnarray*}$ gilt:
$\begin{eqnarray*} \sum_{k=0}^n~q^k = 1+q+...+q^n = \frac{q^{n+1} -1} {q-1} \end{eqnarray*}$

Könntest du das obige einmal ausführlich hinschreiben, ich habe da irgendwie ein Brett vor dem Kopf...
Gott

bitte , bitte !!!!
Derdank einer Studentin im ersten Semester wäre dir gewiss.
Danke im Voraus...
"die Neue"

21.10.2004, 17:27

Blindy

Auf diesen Beitrag antworten »

Schön, wenn ihr euch alle da so gut auskennt....
Ich hätte da auch mal ne Aufgabe...

Zeige duch Induktion und direkte Rechnung für $\begin{eqnarray*} n \in N \end{eqnarray*}$

$\begin{eqnarray*} \frac{a^{n+1} - b^{n+1}} {a-b} = \sum_{v=0}^n~a^{n-v} b^{v} \end{eqnarray*}$ mit $\begin{eqnarray*} a\neq b \end{eqnarray*}$ und $\begin{eqnarray*} a,b\in \mathbb R \end{eqnarray*}$

Und sagt jetzt bitte nicht.... Das ist doch so einfach... Ich rechne da schon ewig rum und komm auf keinen Grünen Zweig....
Also bis dann

123 nächste Seite »

Neue Frage »

Antworten »

Fragen zu [Workshop]-[Vollständige Induktion]

Verwandte Themen