Divisionslemma < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Beweisen Sie das Divisionslemma mittels des starken Induktionsprinzips ( Hinweis: Unterscheiden Sie die beiden Fällen x<y und x [mm] \ge [/mm] y) |
Hallo zusammen,
ich bin auf folgende Aufgabe gestoßen, zu der ich einfach keinen Zugang finde.
Beweisen Sie das Divisionslemma mittels des starken Induktionsprinzips ( Hinweis: Unterscheiden Sie die beiden Fällen x<y und x [mm] \ge [/mm] y)
a) Bestimmen Sie die Stellen im Beweis, bei denen die Voraussetzung benutzt wurde.
b) Welche Sätze werden in dem Beweis verwendet?
c) Können Sie die Voraussetzungen n,a,b, sind Element der Natürlichen Zahlen oder ggT(n,a)=1 des Lemmas abschwächen?
Nachdem ich zwei Tage darüber gegrübelt habe, begann ich nach einer Lösung zu googeln,leider ohne Erfolg. Auch unsere lokale Bibliothek führt tatsächlich kein Buch, welches sichmit dem Induktionsbeweis des Divvisionslemma auseinandersetzt.
Eine Lösung wird im Buch leider nicht gegeben, ich will die Aufgabe aber nicht einfach übergehen.
Ich betreibe die Mathematik nur Hobbyweise, so dass mir evtl gewisse Vorkentnisse fehlen.
Mit den Teilaufgaben habe ich mich noch nicht beschäftigt, da ich schon die Hauptaufgabe nicht schaffe. Jedoch Verwundert mich die Teilaufgabe b), immerhin könnte die doch individuell unterschiedlich ausfallen, oder spielt der Autor hier auf ein unumgänglichen Satz an?
Mit der Teilaufgabe c) kann ich dann wieder nicht viel anfangen.
Viellicht kennt ja hier jemand eine Quelle, in der dies Hauptaufgabe detailliert erklärt wird,
oder hat die Geduld und Zeit mir die Aufgabe zu erklären.
Um wenigstenms einen Ansatz zuliefern:
Ich würde ersteinmal die Eindeutigkeit über einen Wiederspruchbeweis aufzeigen, was ja recht einfach ist.
Dann widme ich mich ganz allgemein der Induktionsanfang mit x=1
Dann erhalte ich 1=qy+r.
gilt dann aber q=1 und r = 1-y ist der Induktionsanfang wahr.
Zumindest dichte ich mir dasmal so zusammen.
Als Induktionsannahme liese sich ja nun A(x) voraussetzen, aber nun, besonders im Hinblick auf die Fallunterscheidung, kommeich nicht weiter.
Diese Aufgabe nagt wirklich sehr an mir, da die vorhergehenden deutlich unproblematischer waren und der Autor keine Lösung anbietet.
Vielen Dank im Voraus
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:44 Do 19.11.2015 | | Autor: | fred97 |
> Beweisen Sie das Divisionslemma mittels des starken
> Induktionsprinzips ( Hinweis: Unterscheiden Sie die beiden
> Fällen x<y und x [mm]\ge[/mm] y)
>
> Hallo zusammen,
>
> ich bin auf folgende Aufgabe gestoßen, zu der ich einfach
> keinen Zugang finde.
>
> Beweisen Sie das Divisionslemma mittels des starken
> Induktionsprinzips ( Hinweis: Unterscheiden Sie die beiden
> Fällen x<y und x [mm]\ge[/mm] y)
>
> a) Bestimmen Sie die Stellen im Beweis, bei denen die
> Voraussetzung benutzt wurde.
> b) Welche Sätze werden in dem Beweis verwendet?
> c) Können Sie die Voraussetzungen n,a,b, sind Element der
> Natürlichen Zahlen oder ggT(n,a)=1 des Lemmas
> abschwächen?
>
> Nachdem ich zwei Tage darüber gegrübelt habe, begann ich
> nach einer Lösung zu googeln,leider ohne Erfolg.
Schau mal hier:
http://www2.math.uni-wuppertal.de/~schuster/teaching/vorlesungen/vorkurs/kap5.pdf
Satz 1.4.
Google ist mein Freund ! Habe eingegeben "Division Lemma Induktionsprinzip".
FRED
> Auch
> unsere lokale Bibliothek führt tatsächlich kein Buch,
> welches sichmit dem Induktionsbeweis des Divvisionslemma
> auseinandersetzt.
> Eine Lösung wird im Buch leider nicht gegeben, ich will
> die Aufgabe aber nicht einfach übergehen.
> Ich betreibe die Mathematik nur Hobbyweise, so dass mir
> evtl gewisse Vorkentnisse fehlen.
>
> Mit den Teilaufgaben habe ich mich noch nicht beschäftigt,
> da ich schon die Hauptaufgabe nicht schaffe. Jedoch
> Verwundert mich die Teilaufgabe b), immerhin könnte die
> doch individuell unterschiedlich ausfallen, oder spielt der
> Autor hier auf ein unumgänglichen Satz an?
> Mit der Teilaufgabe c) kann ich dann wieder nicht viel
> anfangen.
>
> Viellicht kennt ja hier jemand eine Quelle, in der dies
> Hauptaufgabe detailliert erklärt wird,
> oder hat die Geduld und Zeit mir die Aufgabe zu
> erklären.
>
> Um wenigstenms einen Ansatz zuliefern:
>
> Ich würde ersteinmal die Eindeutigkeit über einen
> Wiederspruchbeweis aufzeigen, was ja recht einfach ist.
> Dann widme ich mich ganz allgemein der Induktionsanfang
> mit x=1
> Dann erhalte ich 1=qy+r.
> gilt dann aber q=1 und r = 1-y ist der Induktionsanfang
> wahr.
> Zumindest dichte ich mir dasmal so zusammen.
> Als Induktionsannahme liese sich ja nun A(x) voraussetzen,
> aber nun, besonders im Hinblick auf die Fallunterscheidung,
> kommeich nicht weiter.
>
> Diese Aufgabe nagt wirklich sehr an mir, da die
> vorhergehenden deutlich unproblematischer waren und der
> Autor keine Lösung anbietet.
> Vielen Dank im Voraus
>
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:37 Mo 23.11.2015 | | Autor: | Windbeutel |
Danke dir.
Komisch ich habe verzweifelt "gegoogelt"
Danke dir jedenfalls, jetzt komme ich hoffentlich weiter.
|
|
|
| |
|
| Aufgabe | Beweisen Sie mit Hilfe der starken Induktion das Divisionslemma:
Es seien x und y ganze Zahlen mit y>0
Dann gibt es eindeutig bestimmte ganze Zahlen q und r mit x=qy+r und 0 [mm] \le [/mm] r < y. Es müssen die Fälle x<y und [mm] x\gey [/mm] unterschieden werden. |
Nun muss ich doch noch einmal um Hilfe bitten, da ich hiermit einfach nicht weiter komme.
Inzwischen habe ich mich natürlich mit dem Link von fred97 auseinander gesetzt, und auch ein paar andere Beispiele betrachtet.
Leider komme ich einfach nicht weiter
Die Beispiele die ich finde gehen i.d.R. vom Zahlenbereich [mm] \IN [/mm] aus, während in meiner Aufgabe [mm] \IZ [/mm] gefordert ist.
Habe schon bögenweise Papier beschrieben und verworfen,aber die geforderte Fallunterscheidung bekomme ich nicht auf die Reihe.
Zudem ist in dem Angegebenen Link eine Fallunterscheidung nach r. Ich bin nur noch verwirrt.
Also bis zur Induktionsverankerung komme ich noch, aber der Induktionsschritt ist für mich ( mit der Fallunterscheidung) einfach nicht nachvollziehbar.
Ich bin wirklich für jede Hilfe , Links, Tipps, Literaturhinweise und Gedankenstützen dankbar.
So ich versuche mich jetzt weiter an dieser Aufgabe und danke jedem Helfer im Voraus
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:42 Mi 02.12.2015 | | Autor: | chrisno |
> ...
> Inzwischen habe ich mich natürlich mit dem Link von fred97
> auseinander gesetzt, und auch ein paar andere Beispiele
> betrachtet.
Was spricht gegen den Text, auf den Fred verwiesen hat?
>
> Leider komme ich einfach nicht weiter
> Die Beispiele die ich finde gehen i.d.R. vom Zahlenbereich
> [mm]\IN[/mm] aus, während in meiner Aufgabe [mm]\IZ[/mm] gefordert ist.
Der Text benutzt [mm]\IZ[/mm].
>
>
> Habe schon bögenweise Papier beschrieben und
> verworfen,aber die geforderte Fallunterscheidung bekomme
> ich nicht auf die Reihe.
> Zudem ist in dem Angegebenen Link eine Fallunterscheidung
> nach r. Ich bin nur noch verwirrt.
nicht im verwiesenen Text
>
> Also bis zur Induktionsverankerung komme ich noch, aber der
> Induktionsschritt ist für mich ( mit der
> Fallunterscheidung) einfach nicht nachvollziehbar.
Vorschlag: nimm den Text und arbeite ihn Schritt für Schritt durch. Kommentiere jeden Schritt ausführlich, soweit Du ihn verstanden hast, und lasse deine Kommentare hier bearbeiten.
|
|
|
| |
|
Ich danke dir für deinen Vorschlag, und nehme ihn nur zu gerne an.
Ersteinmal muss ich mich entschuldigen, da ich inzwischen so durcheinander gekommen bin,
dass ich behauptet habe das Beispiel von fred97 würde nicht mit ganzen Zahlen arbeiten.
Nach einer Woche an dieser Aufgabe stapeln sich bei mir die Schmierblätter und ich bin verwirrter als je zuvor.
Zur Aufgabe:
Um weitere Verwirrung meinerseits zu vermeiden habe ich die gegebenen unbekannten n und m entsprechend meiner Aufgabe umbenannt in n=x und m=y.
Seien x, y ganze Zahlen mit y>0.
Dann gibt es eindeutig bestimmte ganze Zahlen q und r mit x= qy+r und 0≤r<y.
Also dies entspricht der mir vorliegenden Definition, nur dass die Forderung nach der Fallunterscheidung x<y und x≥y nicht explizit erwähnt wird.
Beweis.
Sei zunächst x≥0
Die Behauptung wird durch Induktion über n gezeigt. Ist 0≤x<y, so ist
x= 0y+x
ein Darstellung der gewünschten Form.
Und schon beginnen die Probleme.Nach meinem Verständnis wird hier der Induktionsanfang gezeigt, dabei ist die Fallunterscheidung meiner Meinung nach noch nicht wichtig Man hat hier gemäß der starken Induktion einfach gezeigt, dass A(x) wahr ist. Wozu dann die Eingrenzung x<y in
0≤x<y stattgefunden hat verstehe ich nicht so ganz.
So, dies soll vorerst der erste Schritt sein, beide mich um Erleuchtung bitte
evtl komme ich dann selbstweiter, wenn ich diesen teil Verstanden habe.
Nochmals Danke an alle die mir hier ihre Zeit opfern.
|
|
|
| |
|
Hallo,
> s.o
> Ich danke dir für deinen Vorschlag, und nehme ihn nur zu
> gerne an.
> Ersteinmal muss ich mich entschuldigen, da ich inzwischen
> so durcheinander gekommen bin,
> dass ich behauptet habe das Beispiel von fred97 würde
> nicht mit ganzen Zahlen arbeiten.
> Nach einer Woche an dieser Aufgabe stapeln sich bei mir
> die Schmierblätter und ich bin verwirrter als je zuvor.
>
> Zur Aufgabe:
> Um weitere Verwirrung meinerseits zu vermeiden habe ich
> die gegebenen unbekannten n und m entsprechend meiner
> Aufgabe umbenannt in n=x und m=y.
Ok, das kannst du natürlich gerne machen ...
>
> Seien x, y ganze Zahlen mit y>0.
> Dann gibt es eindeutig bestimmte ganze Zahlen q und r mit
> x= qy+r und 0≤r<y.
>
> Also dies entspricht der mir vorliegenden Definition, nur
> dass die Forderung nach der Fallunterscheidung x<y und
> x≥y nicht explizit erwähnt wird.
Die wird aber doch direkt im Beweis gemacht.
Zunächst wird angenommen, dass [mm]0\leq x
Das ist dein erster Fall ...
Der ist aber trivial, denn dann ist [mm]x=0\cdot{}y+x[/mm] und der Rest [mm]x[/mm] erfüllt [mm]0\leq x
Dann kommt der Fall [mm]x>y[/mm] (x=y) ist ja ebenfalls trivial
>
>
> Beweis.
> Sei zunächst x≥0
> Die Behauptung wird durch Induktion über n gezeigt. Ist
> 0≤x<y, so ist
> x= 0y+x
> ein Darstellung der gewünschten Form.
>
> Und schon beginnen die Probleme.Nach meinem Verständnis
> wird hier der Induktionsanfang gezeigt, dabei ist die
> Fallunterscheidung meiner Meinung nach noch nicht wichtig
Naja, der erste Fall [mm]x
Die Darstellung ergibt sich doch automatisch ...
Die Induktion kommt erst im anderen Fall [mm]x>y[/mm] zum Tragen ...
> Man hat hier gemäß der starken Induktion einfach gezeigt,
> dass A(x) wahr ist. Wozu dann die Eingrenzung x<y in
> 0≤x<y stattgefunden hat verstehe ich nicht so ganz.
Induktion (mit der erweiterten IV) wird erst im Fall [mm]x>y[/mm] benutzt ...
>
>
>
> So, dies soll vorerst der erste Schritt sein, beide mich um
> Erleuchtung bitte
> evtl komme ich dann selbstweiter, wenn ich diesen teil
> Verstanden habe.
> Nochmals Danke an alle die mir hier ihre Zeit opfern.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:35 Mo 07.12.2015 | | Autor: | Windbeutel |
Puh, ich glaube langsam blicke ich durch.
Insgesamt empfinde ich das ganze als etwas kompliziert verfasst, das mag daran liegen,dass ich keinen mathematischen Hintergrund habe.
Ich bedankemich auf jeden Fall ganz herzlich bei dir und allen, die mir hier geduldig weiter geholfen haben
Vielen Dank
|
|
|
|
