Induktion (n^2 + n + 2)/2

Question

Aufgabe : Vollständige Induktion

Durch n Geraden in allgemeiner Lage in einer Ebene wird die Ebene in (n^2 + n + 2) / 2 Teile zerlegt.

Problem/Ansatz:

… ???? Ratlos

Comments

Was bedeutet "allgemeine Lage"?

---

Das bedeutet maximale Anzahl von Schnittpunkten

---

Es geht hier doch nicht um Schnittpunkte, dafür gäbe es für \(n\) geraden einfach \(\begin{pmatrix} n\\2 \end{pmatrix}\) Möglichkeiten. (wenn nicht parallel)

\(n\) Geraden teilen eine Ebene in \(\sum_{i=1}^m {n \choose i}\) Gebiete ein. Beipsiel für \(n=3\):

---

Da musst du aber schon sagen, wieso du in deiner Formel m UND N UND i verwendest...

---

Nachtrag:

m = Dimension der Hyperebene (in diesem Beispiel m=2)

Für \(n=3\) und \(m=2\) also \({3 \choose 2} + {3\choose 1} + {3 \choose 0}=7\).

Eine Ebene ist nicht zwingend die im Anschauungsraum, oder?

---

Ich bemerke gerade, dass das eine Verallgemeinerung der eigentlichen Frage darstellt. Für Ebenen im \(\mathbb{R}^2\) hat man:$$\begin{pmatrix} n\\2 \end{pmatrix}+\begin{pmatrix} n\\1 \end{pmatrix}+\begin{pmatrix} n\\0 \end{pmatrix}=\frac{n^2+n+2}{2}$$ Man kann das kombinatorisch begründen, da braucht man keine Induktion.

---

Damit formulierst du die gestellt Frage einfach nochmal. Das beantwortet dem Fragesteller nicht, warum das so ist.

---

@abakus

Das ist ein bisschen schwierig zu beschreiben.

Stell dir mal eine Menge von endlich vielen Geraden vor: Wir können dieses Sammelsurium so aussrichten, dass keiner Geraden parallel zur Horizontalen ist.

Wir betrachten zunächst nur den tiefsten Punkt (kartesisches Koordinanteystem) einer beliebigen Teilebene. Wenn diese Teilebene nach unten beschränkt ist (im Bild 2,3 und 1), so gibt es einen eindeutigen tiefsten Punkt: der Schnittpunkt zwischen zwei Geraden. Es gibt eine bijektive Abbildung zwischen Gebieten, die nach unten beschränkt sind und Schnittpunkten und damit \({ n \choose 2 } = \frac{n^2-n} {2}\) Gebiete.

Nun muss man sich noch die Frage stellen, wie viele Gebiete es gibt, die nicht nach unten beschränkt sind. Idee?

---

Warum fragst du MICH nach einer Idee zu deinem Ansatz?

jester hat eine Frage gestellt, die ich ihm bereits mit elementaren Mitteln beantwortet habe.

---

Ich kann meinen Ansatz auch selbst vervollkommnen, hast du dich nicht aber beschwert, wenn Forumsmitglieder abschreibfertige Antworten geben?

---

Ich bin nur etwas irritiert, dass du es für nötig hältst, bei einer Formel, die ich normalerweise die Schüler in einer Mathematik-AG der Klassenstufe 6 oder 7 finden lasse, so einen riesigen Aufriss mit Hyper-Super-Duper-Ebenen veranstaltest.

Ist das wirklich noch die Bereitschaft zu dem Fragesteller angemessener Hilfeleistung, oder gewinnt da ein wenig Selbstdarstellung die Oberhand?

---

Ist das wirklich noch die Bereitschaft zu dem Fragesteller angemessener Hilfeleistung, oder gewinnt da ein wenig Selbstdarstellung die Oberhand?

Beweise über vollständige Induktion macht man allenfalls auf der Oberstufe im Leistungskurs - und dann auch nur sehr kurz.

Ich dachte, dass es sich hier um eine universitäre Aufgabe handelt, so dass der Ebenenbegriff bereits auf \(n\) Dimensionen erweitert wurde. Außerdem ist nicht auszuschließen, dass jester die Bemerkung trotzdem interessant findet. Zudem lesen diese Frage auch andere Forumsmitglieder und möglicherweise auch Interessenten der Zukunft.

---

Ich dachte, dass es sich hier um eine universitäre Aufgabe handelt,

Ich habe es mir zur Angewohnheit gemacht, meist erst mal zu nachzuschauen, welche weiteren Fragen der Fragesteller zuletzt gestellt hat und wie er auf bisherige Antworten/Kommentare reagiert hat. Das hat zwei Vorteile: Man kann das Aufgabenumfeld (Schule/Studium) und das Niveau des Fragestellers einigermaßen abschätzen, und man erkennt zudem noch recht schnell vermutliche Ich-habe-keine-Lust-meine-Hausaufgaben-selbst-zu-machen-Schmarotzer. Letztere werden ignoriert oder -wenn ich gute Laune habe - mit Kommentaren aufgemuntert.

Das heißt jetzt nicht, dass ich immer so vorgehe. Wenn ich eine Aufgabe richtig "schön" finde, antworte ich auch ohne "Umfeldbegutachtung".

Answer 1

Bei der vollständigen Induktion muss man einfach anfangen.

$$(n^2+n+2)/2$$

Induktions Anfang

Eine Gerade teilt eine Fläche in zwei Teile.

$$T(1)=(1^2+1+2)/2=2$$

Nun sollten wir uns darüber verständigen, was in allgemeiner Lage bedeutet. Da es sonst sofort ein Gegenbeispiel gibt, bedeutet es, dass es keine Geraden gibt, die parallel verlaufen. Allgemeine Lage bedeutet aber auch, dass in jedem Punkt, sich immer nur zwei Geraden schneiden, denn sonst hätten wir das nächste Gegenbeispiel. Wenn ich eine n+1te Gerade einfüge, bekomme ich also n+ 1 mehr Flächen.

Induktions Annahme, die Aussage stimmt für n Geraden

$$T(n)= (n^2+n+2)/2$$

$$T(n+1)= (n^2+n+2)/2+n+1$$

$$T(n+1)= (n^2+2n+1+n+1+2)/2$$

$$T(n+1)= ((n^2+2n+1)+(n+1)+2)/2$$

$$T(n+1)= ((n+1)^2+(n+1)+2)/2$$

wzzw Induktionsschluss

Answer 2

Was ist denn hier los? Zwei Stunden und noch keine Antwort...

Die Gerade mit der Nummer n+1 schneidet die übrigen n Geraden. Dabei durchläuft sie n+1 bestehende Teilflächen

(die Fläche außerhalb der ersten geschnittenen Geraden,

die Fläche zwischen der ersten und zweiten geschnittenen Geraden,

die Fläche zwischen der zweiten und dritten geschnittenen Geraden,

...,

die Fläche zwischen der vorletzten und letzten (n-ten) geschnittenen Geraden

und die Fläche nach der letzten geschnittenen Geraden.)

Aus jeder dieser bestehenden (n+1) Teilflächen entstehen durch die Zerteilung also n+1 neue Teilflächen.

Die Anzahl der Teilflächen bei n+1 Geraden erhält man also, wenn man zur Anzahl der Teilflächen bei n Geraden die Zahl n+1 dazu addiert.