vollständige Induktion, Knotenseile

Question

Kann mir bitte jemand helfen :( ich scheitere schon beim Unduktionsanfang.

Also 2.1.1 / 

1Fall: n=n   so 3 Knoten = 3 Teile

2Fall: n= n-1 also 3 Knoten= 2Teile

Aber wie beginne ich nun den jeweiligen Induktionsanfang?  n=n ist doch schon bewiesen oder? und wie kann n=n-1 sein? Oder liege ich da voll daneben?

Comments

Du liegst voll daneben. Die Sache mit der vollstaendigen Induktion wirst Du schon noch mal gruendlich nacharbeiten muessen.

---

Wie sieht den nun der Induktionsanfang aus ?

---

Du hast ja noch nicht mal eine vernuenftige Aussage formuliert, die man dann beweisen koennte. Das ist der Anfang, nicht der Induktionsanfang.

---

Ja das meit ich ja , ich weiß nicht wie ich anfangen soll. denn bei 2.1.1.

1 Fall n=n

2Fall n=n+1

Kann ich nun einfach irgendeine Behauptung aufstellen wie zB  n=

 weil diese in 2.1.2. soll ja wahr sein und sich auf 2.1.1 beziehen :(

---

Mir ist ganz schleierhaft, was Deine beiden Faelle vorstellen sollen. Oder was gar mit n = n - 1 gemeint sein soll -- diese Gleichung ist doch einfach nur immer falsch!

Die Aussage für das geschlossene Seil lautet: Von n Knoten wird es in n Teilstuecke zerlegt.

Und für das offene Seil mit Knoten an den Enden: Von n Knoten wird es in n - 1 Teilstuecke zerlegt.

---

Ja Das hätte ich auch noch hinbekommen :D


ich versteh nicht was ich bei einer vollständigen induktion gegenüberstellen soll bei 2.1.2 weil es ja wie von dir "gelösten" behauptungen sich beziehen soll.

---

Beide aufgestellten Behauptungen sind (jeweils einzeln) noch zu beweisen. Beide einmal per vollstaendiger Induktion und beide noch einmal mit einer alternativen Methode Deiner Wahl.

Deine allererste Aufgabe lautet:

Behauptung: Ein geschlossenes Seil wird von n Knoten in n Teile zerlegt.

Beweis: Per vollstaendiger Induktion. (Ist von Dir auszufuehren.)

Deine naechste Aufgabe lautet:

Behauptung: Ein offenes Seil mit Knoten an den Enden wird von n Knoten in n - 1 Teile zerlegt.

Beweis: Per vollstaendiger Induktion. (Ist von Dir auszufuehren.)

Answer 1

Hallo Sascha,

IMHO kommt es es hier weniger auf die Lösung (die ist trivial), als auf eine saubere Formulierung des Lösungswegs an.

Ich betrachte zunächst nur den Fall 1 - also das geschlossen Seil. Weiter ignoriere ich, dass es schwierig sein wird, in ein geschlossenes Seil einen einzelnen Knoten einzubringen ;-)

ich nenne $a$ die Anzahl der Teile im Seil, die durch zwei benachbarte Knoten begrenzt werden. Und $n$ die Anzahl der Knoten im Seil - nun ist offensichtlich die Anzahl der Teile eine Funktion von der Anzahl der Knoten:

$$a=a(n)$$

Die Behauptung soll sein:

$$a(n)=n$$

Das wird zunächst mit dem Induktionsanfang überprüft. Hier setze ich eine möglichst kleine Zahl ein - z.B. $n=1$ und überprüfe, ob das Sinn macht.

$$a(1)=1$$Ein Knoten in einem geschlossenen Seil - das Seil besteht immer noch aus genau einem Teil, welches durch keinen Knoten unterbrochen wird. Ok - Induktionsanfang passt!

Im Induktionsschritt gilt es jetzt, die Behauptung für $n+1$ zu beweisen, wobei $a(n)=n$ verwendet werden darf. Zu beweisen ist, dass

$$a(n+1)=n+1$$

ist. Dazu überlegt man sich, wie man von $a(n)$ zu $a(n+1)$ gelangt. Man beginnt z.B. mit

$$a(n+1)=a(n) + ...$$

da waren also schon $n$ Knoten und $a(n)$ Teile - jetzt kommt ein weiterer Knoten hinzu. Der zusätzliche Knoten teilt eines der Teilstücke in zwei Teile. D.h. aus 1 wird 2 - somit wird sich die Gesamtzahl der Teile um 1 erhöhen. Daraus folgt:

$$a(n+1)=a(n) + 1$$

Nun nutzt man aus, dass man hier $a(n)=n$ verwenden darf und erhält

$$a(n+1)=a(n) + 1=n+1$$

genau die Aussage, die es zu zeigen gilt (s.o.).

Du solltest es jetzt alleine schaffen, dass auf den Fall 2 zu übertragen. Falls Du da Probleme hast, so frage bitte nach.

zu 2.1.2) hast Du noch eine andere Begründung ohne Induktion? Tipp: Wie viele Teile liegen links und rechts von jedem Knoten und durch wie viele Knoten wird ein Teil jeweils begrenzt?

zu 2.1.3) Ein weitaus schwieriger Fall wäre die Frage: In wie viele Teile wird ein Seil geteilt, wenn zwar jedes Teil wieder durch zwei Knoten begrenzt wird, aber selber beliebig viele zusätzliche Knoten enthalten darf?

Gruß Werner