TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 17

$a_{n}$ sei die größte Anzahl von Teilen, in die die Ebene duch $n$ Geraden zerlegt werden kann.

Zeigen Sie durch vollständige Induktion: $a_{n}=1+{\frac {n(n+1)}{2}}$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Vollständige Induktion

Vollständige Induktion

1. Induktionsanfang (IA)
2. Induktionsschritt (IS): Induktionsvoraussetzung (IV) $\Rightarrow$ Induktionsbehauptung (IB)

Lösungsvorschlag von samuelp

Induktionsanfang $n=0$

Wenn keine Gerade verwendet wird, ist die Ebene ein Teil. Auch die Formel liefert $a_{0}=1$.

Induktionsschritt $n\rightarrow n+1$

Induktionshypothese: mit $n$ Geraden kann die Ebene in $a_{n}=1+{\frac {n(n+1)}{2}}$ Teile zerschnitten werden

Induktionsbehauptung: mit $n+1$ Geraden kann die Ebene in $a_{n+1}=1+{\frac {(n+1)(n+2)}{2}}$ Teile zerschnitten werden

Aufgrund der $I.H.$ kann die Ebene in $a_{n}=1+{\frac {n(n+1)}{2}}$ Teile zerschnitten werden. Wir legen eine neue Gerade sodass:

• die neue Gerade ist zu keiner der $n$ Geraden parallel
• die neue Gerade geht durch keine der bisherigen Schnittpunkte. Dadurch entstehen $n$ neue Schnittpunkte.

Die $n$ neuen Schnittpunkte zerschneiden $n+1$ Gebiete und es entstehen dadurch $n+1$ neue.

${\begin{aligned}a_{n+1}&{\overset {I.H.}{=}}a_{n}+n+1\\&={\frac {n(n+1)}{2}}+{\frac {2(n+1)}{2}}\\&={\frac {n(n+1)+2(n+1)}{2}}\\&{\overset {1.}{=}}{\frac {(n+2)(n+1)}{2}}\\&=a_{n+1}\end{aligned}}$

Dadurch ist gezeigt, dass die Formel von $a_{n+1}$ auch wahr ist.

Erklärungen der einzelnen Umformungen

1. Herausheben von $(n+1)$ aus den Termen $n(n+1)$ und $2(n+1)$ zu $(n+2)(n+1)$