TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/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\to 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{array}{cc}{a}_{n+1}& \stackrel{I.H.}{=}{a}_n+n+1\\ & =\frac{n(n+1)}{2}+\frac{2(n+1)}{2}\\ & =\frac{n(n+1)+2(n+1)}{2}\\ & \stackrel{1.}{=}\frac{(n+2)(n+1)}{2}\\ & =a_{n+1}\end{array}$

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)$