+19 Beweise folgende Aussage mit vollständiger Induktion:
Durch n Geraden in allgemeiner Lage in einer Ebene wird die Ebene in (n^2 + n + 2) /2 Teile zerlegt.
Hinweis: Durch Hinzunahme einer weiteren Geraden wird eine bestimmte Anzahl der schon vorhandenen Gebiete in zwei Teile zerlegt.
+3976 Der Induktionsanfang ist ja wie gewohnt einfach: Eine Gerade teilt die Ebene in 2=(1²+1+2)/2 Teile.
Für den Induktionsschritt muss ich nochmal nachfragen: Was genau bedeutet "in allgemeiner Lage" hier? Soll kein Punkt von 3 oder mehr Geraden getroffen werden? Bin mir relativ sicher, dass das für die Aussage notwendig ist.
Ein Gegenbeispiel macht das ganz gut deutlich: Drei Ursprungsgeraden teilen die Ebene in 6 Stücke, aber (3²+2+2)/2=7.
Mit dieser Annahme klappt dann auch der Induktionsschritt:
Wir nehmen an, dass die ersten n Geraden die Ebene in (n²+n+2)/2 Teile teilt. Wir fügen dieser Konstellation nun eine Gerade hinzu. Diese schneidet die bisherigen n Geraden in jeweils einem Punkt, es gibt also nun n neue Schnittpunkte (weil sich ja nirgends mehr als 2 Geraden treffen.)
Die Abschnitte der neuen Geraden, die von jeweils 2 Schnittpunkten berandet sind, teilen genau ein Flächenstück in 2 Flächenstücke auf. Von solchen Abschnitten gibt es n-1 Stück, also n-1 "neue" Flächen. Die beiden "Endstücke" teilen ebenfalls ein Flächenstück auf, also gibt es noch 2 neue Flächenstücke mehr, insgesamt dann n+1.
Da es vorher (Induktionsannahme!) (n²+n+2)/2 Teile gab, gibt es mit einer Geraden mehr genau
\(\frac{n^2+n+2}{2}+n+1 = \frac{n^2+n+2+2n+2}{2} = \frac{n^2+2n+1+n+3}{2} =\frac{(n+1)^2+(n+1)+2}{2}\) Flächenstücke. Damit ist der Induktionsschritt abgeschlossen.
!
