TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 17

Aus VoWi
Zur Navigation springen Zur Suche springen

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}


Hilfreiches[Bearbeiten]

Vollständige Induktion
Vollständige Induktion[Bearbeiten, WP]
  1. Induktionsanfang (IA)
  2. Induktionsschritt (IS): Induktionsvoraussetzung (IV) \Rarr Induktionsbehauptung (IB)

Lösungsvorschlag von samuelp[Bearbeiten]

Induktionsanfang n=0[Bearbeiten]

Wenn keine Gerade verwendet wird, ist die Ebene ein Teil. Auch die Formel liefert a_0=1.

Induktionsschritt n \rightarrow n+1[Bearbeiten]

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+\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{align}
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{align}

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)