Frage zur Art des induktiven Beweises

Neue Frage »

zigzag Auf diesen Beitrag antworten »
Frage zur Art des induktiven Beweises
Meine Frage:
Hi Leute!
1) Beim Beweis (siehe Attachment) verstehe ich nicht ganz, wie man den Induktionsschritt macht : Einerseits steht da : "m-1 -> m", d.h ganz normaler Schritt nach vorne... Andererseits man geht im Bew. davon aus, dass die Aussage für m gilt, und zeigt, dass die Aussage für m-1 auch gilt, d.h der Induktion läuft quasi in entgegengesetzter Richtung "m -> m-1". Ist es überhaupt korrekt? Wenn ja, dann wieso?
[attach]28390[/attach]


2) Habe einen Beweis gesehen in einem Script zu Graphentheorie, wo man die Induktion parallel für mehrere Parameter macht, z.B im Bew. für die Eulersche Formel macht man Induktion gleichzeitig über Anzahl der Kanten und Anzahl der Knoten. Ist es mathematisch sauber?

Danke im voraus!


Meine Ideen:
...
weisbrot Auf diesen Beitrag antworten »
RE: Frage zur Art des induktiven Beweises
nein, die induktion läuft ganz normal über m (wobei n und r beliebig seien dürfen), wo siehst du da eine ind. in "entgegengesetzter richtung"?

Zitat:
2) Habe einen Beweis gesehen in einem Script zu Graphentheorie, wo man die Induktion parallel für mehrere Parameter macht, z.B im Bew. für die Eulersche Formel macht man Induktion gleichzeitig über Anzahl der Kanten und Anzahl der Knoten. Ist es mathematisch sauber?


kommt drauf an wie das genau aussieht. math. begründen kann man das sicherlich.

lg
zigzag Auf diesen Beitrag antworten »
RE: Frage zur Art des induktiven Beweises
Weisbrot, schau doch mal auf Induktionsschritt : Induktion läuft über Anzahl der Kanten (m). Aber anstatt eine Kante dazu zu nehmen (m->m+1), nimmt man eine Kante weg (siehe beide Unterscheidungsfälle). Für mich sieht so aus, als macht man den Schritt von m auf m-1. D.h Induktionsvoraussetzung hier ist : die Aussage gilt für m und man zeigt, dass die Aussage auch für m-1 gilt...Höchstwahrscheinlich verstehe ich das Ganze falsch...
weisbrot Auf diesen Beitrag antworten »
RE: Frage zur Art des induktiven Beweises
von einem m graphen auszugehen und eine kante dazuzunehmen wäre nicht unbedingt korrekt, weil erstmal nicht klar ist, dass man so jeden m+1 graphen bekommt - geschweige dessen dass das hier nicht gemacht wird.
man geht von einem m+1 graphen aus (für den man die aussage zeigen will) - man stellt sich vor man nimmt irgendwas weg, wodurch man die frage über den m+1 graph auf die über einen m graph (über den man nach ind.voraussetzung alles weiß) zurückgeführt hat.
wie wenn man den kleinen gauß beweisen will: man will die formel für 1+2+3+...+(n+1) zeigen, also schreibt man das ding zu (1+2+...+n) + (n+1) um - für den linken teil kennt man die formel nach ind.voraussetzung, dann fuchtelt man ein bisschen rum und bekommt die formel für 1+2+...+(n+1).
hier bekommt man eben aus einem graphen mit m, n und r dingern einen mit m-1, n-1 und r und dann gehts genauso (nur auf das rumfuchteln wird hier nicht genau eingegangen).
irgendwie klar?
lg
zigzag Auf diesen Beitrag antworten »
RE: Frage zur Art des induktiven Beweises
Danke für die schnelle Antwort, aber ich verstehe immer noch nicht, wie man es meint.
Vielleicht wäre es einleuchtender, wenn du den Beweis (Induktionsschritt) mit allen Formalitätten umschreibst.
weisbrot Auf diesen Beitrag antworten »
RE: Frage zur Art des induktiven Beweises
ne, ich denke das werd ich nicht machen, zumal ich auch nicht soviel ahnung von der thematik hab.
was genau verstehst du nicht? man nimmt einen graphen mit m kanten, entfernt ein blatt oder eine kante, bekommt so einen kleineren graphen mit m-1 kanten, und bekommt per ind.voraussetzung für diesen die gleichungen n-1 - (m-1) + r = 2 bzw. n - (m-1) + (r-1) = 2 - beide sind äquivalent zur zu zeigenden gleichung n - m + r = 2 , fertig!
lg
 
 
zigzag Auf diesen Beitrag antworten »
RE: Frage zur Art des induktiven Beweises
Mein Problem ist, dass ich nicht sehe, dass die Aussage für m bewiesen ist. Ich sehe nur folgendes :

IV) Dia Aussage A gelte für m-1
IB) A gilt auch für m
IS) man möchte A für m beweisen, aber man macht Reduktion und beweist A für m-1 und nicht für m!!! Wozu macht man das für m-1, wenn es IA???

Das einzige Szenario, was denkbar wäre :
IV) Die Aussage A gelte für m-1
IB) A gilt auch für m
IS) Man reduziert den m-Graph um 1 Kante und zeigt durch IV dass A für m-1-Graph gilt und (die folgende Erklärung fehlt im Bew.) wenn man die Reduktion zurücknimmt (d.h rekonstruiert den m-1-Graph zurück zu m-Graph, genauso, wie man es reduziert hat) bekommt man auch die Gültigkeit von A auch für m-Graph.

Meinst du sowas?
zigzag Auf diesen Beitrag antworten »
RE: Frage zur Art des induktiven Beweises
Zitat:
Wozu macht man das für m-1, wenn es IA???

Sorry, meinte natürlich IV und nicht IA
weisbrot Auf diesen Beitrag antworten »
RE: Frage zur Art des induktiven Beweises
Zitat:
IS) man möchte A für m beweisen, aber man macht Reduktion und beweist A für m-1 und nicht für m!!! Wozu macht man das für m-1, wenn es IA???

man beweist es nicht für m-1, sondern die aussage für m-1 gilt nach ind.voraussetzung.

Zitat:
[...] und (die folgende Erklärung fehlt im Bew.) wenn man die Reduktion zurücknimmt (d.h rekonstruiert den m-1-Graph zurück zu m-Graph, genauso, wie man es reduziert hat) bekommt man auch die Gültigkeit von A auch für m-Graph.

diese zurück-reduktion wird doch gemacht, wenn auch vielleicht nicht so wie dus dir vorstellst - man will doch zeigen, dass n - m + r = 2, und nach ind.voraussetzung bekommt man n-1 - (m-1) + r = 2 bzw. n - (m-1) + (r-1) = 2, also ist man sofort fertig.
die eigendliche arbeit im induktionsschritt besteht darin zu erkennen wie sich n,m und r verhalten wenn man (je nach fall) irgendwas wegnimmt.

lg
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »