Vollständige Induktion, Geom. < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
brauche nochmal Abstand von Graphen, also zurück zur Vollständigen Induktion :)
Beispiel:
http://www.mathe-online.at/materialien/matroid/files/vi/vi.html#9a
Anzahl der Diagonalen in einem n-Eck. Als konkretes Beispiel: 5-Eck
I.V.:
d(n) = n/2 * (n-3) n [mm] \ge [/mm] 3
I.A.:
d(3) = [mm] \bruch{3}{2} [/mm] * (3-3) = 0
Stimmt da es in einem Dreieck keine Diagonalen gibt.
I.S.:
Fragen zum Text, der Author schreibt:
1. Das Dreieck hat keine und das (n-1)-Eck hat d(n-1) Diagonalen (Induktionsvoraussetzung).
bedeutet d(n-1) in diesem Fall: d(5-1) = [mm] \bruch{5}{2} [/mm] * (5-3) = 5 ?
2. Die Auftelung des n-Ecks in ein Dreieck und restliche Eck - wofür?
I.S.:
Also es ist der Schritt von n auf n-1, mehr Erklärungen liefert der Author nicht.
Normalerweise würde ich n in der I.A. jetzt durch n-1 ersetzen, aber die Lösung des Authors sieht komplett anders aus:
z.B.: Es fehlt: [mm] \bruch{n}{2}
[/mm]
Folgt: d(n) = d(n-1) + (n-3) + 1
= (n-1)/2 * ((n-1)-3) + (n-3) + 1
= (n-1)*(n-4)/2 + n -2
= (n2-5n+4)/2 + n -2
= (n2-3n)/2
= (n * (n-3)) / 2
Wer hat eine Idee und kann die Gedanken des Verfassers nachvollziehen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:47 Sa 31.12.2011 | | Autor: | Fulla |
Hallo studentxyz,
> Hallo,
>
> brauche nochmal Abstand von Graphen, also zurück zur
> Vollständigen Induktion :)
>
> Beispiel:
>
> http://www.mathe-online.at/materialien/matroid/files/vi/vi.html#9a
> Anzahl der Diagonalen in einem n-Eck. Als konkretes
> Beispiel: 5-Eck
>
> I.V.:
> d(n) = n/2 * (n-3) n [mm]\ge[/mm] 3
>
> I.A.:
> d(3) = [mm]\bruch{3}{2}[/mm] * (3-3) = 0
>
> Stimmt da es in einem Dreieck keine Diagonalen gibt.
Der Induktionsanfang kommt vor der Induktionsvoraussetzung. (Aber der I.A. ist korrekt ![[ok]](/images/smileys/ok.gif "[ok]") )
> I.S.:
>
> Fragen zum Text, der Author schreibt:
> 1. Das Dreieck hat keine und das (n-1)-Eck hat d(n-1)
> Diagonalen (Induktionsvoraussetzung).
>
> bedeutet d(n-1) in diesem Fall: d(5-1) = [mm]\bruch{5}{2}[/mm] *
> (5-3) = 5 ?
Das Konzept der vollständigen Induktion funktioniert ja folgendermaßen: Du hast eine Aussage (hier: über die Anzahl der Diagonalen im n-Eck). Man zeigt, dass die Aussage für einen möglichst einfachen Fall (hier: Dreieck) gilt. Dann nimmt man an, die Aussage gilt auch für einen anderen Fall (hier: (n-1)-Eck) und folgert daraus die Gültigkeit für den nachfolgenden Fall (hier: n-Eck).
Wir haben hier also schon:
- Aussage gilt für das Dreieck (Induktionsanfang)
- Annahme: Aussage gilt für das (n-1)-Eck (Induktionsvoraussetzung)
Was uns noch fehlt ist:
- Wenn die Aussage für das (n-1)-Eck gilt, dann gilt sie auch für das n-Eck
Wenn wir das bewiesen haben, können wir schließen: wenn die Aussage für das k-Eck gilt, dann auch für das (k+1)-Eck. Also, wenn die Aussage für das Dreieck gilt (und das wissen wir ja schon), dann auch für das Viereck. Aber dann gilt sie auch für das Fünfeck. Und auch für das Sechseck, usw.
> 2. Die Auftelung des n-Ecks in ein Dreieck und restliche
> Eck - wofür?
Wir nehmen an, dass die Aussage für das (n-1)-Eck gilt (I.V.) und wollen jetzt eine Aussage über das n-Eck machen. Z.B. nehmen wir an, die Aussage gilt für das Fünfeck und wollen jetzt etwas über das Sechseck aussagen. Dazu schneiden wir vom Sechseck eine Ecke weg und haben ein Fünfeck und ein Dreieck, das "am Fünfeck dranklebt".
[Dateianhang nicht öffentlich]
An dem Bild siehst du, was ich meine: Man schneidet vom n-Eck eine Ecke weg und hat ein (n-1)-Eck und ein Dreieck. Vom (n-1)-Eck kennen wir die Anzahl der Diagonalen schon, nämlich d(n-1) - die Richtigkeit der Aussage über das (n-1)-Eck steht in der Indktionsvoraussetzung.
Wie viele Diagonalen kommen jetzt noch dazu? Das sind alle Verbindungen von der "abgeschnittenen" Ecke zu Punkten, die mind. 2 Punkte entfernt sind, also (n-3)-Stück (siehe Bild).
> I.S.:
> Also es ist der Schritt von n auf n-1, mehr Erklärungen
> liefert der Author nicht.
> Normalerweise würde ich n in der I.A. jetzt durch n-1
> ersetzen, aber die Lösung des Authors sieht komplett
> anders aus:
> z.B.: Es fehlt: [mm]\bruch{n}{2}[/mm]
>
> Folgt: d(n) = d(n-1) + (n-3) + 1
> = (n-1)/2 * ((n-1)-3) + (n-3) + 1
> = (n-1)*(n-4)/2 + n -2
> = (n2-5n+4)/2 + n -2
> = (n2-3n)/2
> = (n * (n-3)) / 2
Das ist jetzt die Rechnung dazu. Angenommen, die Aussage gilt für das (n-1)-Eck, dann gilt für das n-Eck:
d(n)=d(n-1)+ (Anzahl der Diagonalen von der abgeschnittenen Ecke aus) + (die abschneidende Diagonale)= d(n-1)+(n-3)+1.
Für d(n-1) können wir [mm] $\frac{(n-1)*(n-4)}{2}$ [/mm] einsetzen - das ist die I.V. Wenn wir den Term zusammenfassen, kommt [mm] $\frac{n*(n-3)}{2}$ [/mm] raus und genau das wollen wir ja!
Ich hoffe, das war einigermaßen verständlich... Wenn nicht, frag nochmal nach!
Lieben Gruß,
Fulla
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
|
