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

Aus VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Version vom 19. April 2019, 15:49 Uhr von Samuelp (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{Beispiel|1= <math>a_n</math> sei die größte Anzahl von Teilen, in die die Ebene duch <math>n</math> Geraden zerlegt werden kann. Zeigen Sie durch vollstä…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Wechseln zu: Navigation, Suche

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