Vollst. Induktion; Flächen in einem Kreis

03.05.2009, 17:38	Kalysa	Auf diesen Beitrag antworten »
Vollst. Induktion; Flächen in einem Kreis Die Aufgabe lautet: Es sei A(n) die max. Anzahl von Flächen nnerhalb eines Kreises, die Sie erhalten können, wenn Sie auf dem Kreisrand n Punkte auswählen und alle Punkte paarweise durch Geraden verbinden. Die Anzahl der entstandenen Flächen ist maximal, wenn sich keine drei Geraden in einem Punkt schneiden. Es sei A(1)=1, A(n+1)= A(n) + SUMME (von k=1 bis n) (1+(k-1)(n-k)), n größer/gleich 1. Zeigen Sie: A(n) = n + $\begin{eqnarray} \begin{pmatrix} n \\ 4 \end{pmatrix} \end{eqnarray}$ + $\begin{eqnarray} \begin{pmatrix} n-1 \\ 2 \end{pmatrix} \end{eqnarray}$ Ich weiß, dass ich hierfür vollständige Induktion verwenden muss. Außerdem muss letzten Endes gelten: n + $\begin{eqnarray} \begin{pmatrix} n \\ 4 \end{pmatrix} \end{eqnarray}$ + $\begin{eqnarray} \begin{pmatrix} n-1 \\ 2 \end{pmatrix} \end{eqnarray}$ = A(n-1) + SUMME (von k=1 bis n-1) (1+(k-1)((n-1)-k)). Ich habe schon alles mögliche versucht, ich komme einfach nicht durch. Was übersehe ich Entscheidendes? Oder wie fange ich an? Ich habe mittlerweile es mit allen Seiten probiert, bleibe aber immer stecken. Mich irritiert, dass ich doch eigentlich nicht weiß, wie genau A(n-1) aussieht? Klar könnte ich in n + $\begin{eqnarray} \begin{pmatrix} n \\ 4 \end{pmatrix} \end{eqnarray}$ + $\begin{eqnarray} \begin{pmatrix} n-1 \\ 2 \end{pmatrix} \end{eqnarray}$ statt n immer n-1 einsetzen, aber dann würde ich ja schon das A(n) anwenden, und ich soll es ja erst beweisen. Kann mir jemand helfen und sagen, was ich falsch mache?
03.05.2009, 18:02	AD	Auf diesen Beitrag antworten »
Das eigentliche schwierige an der Aufgabe ist doch die Aufstellung der Rekursionsformel $\begin{eqnarray} A(n+1) = A(n) + \sum_{k=1}^n (1+(k-1)(n-k)) \end{eqnarray}$ , aber die hast du ja bereits (woher auch immer) vorliegen. Der Nachweis der expliziten Formel $\begin{eqnarray} A(n) = n + \binom{n}{4} + \binom{n-1}{2} \end{eqnarray}$ durch Induktion ist doch dann nicht mehr schwierig: Um im Induktionsschritt $\begin{eqnarray} n\to n+1 \end{eqnarray}$ dann $\begin{eqnarray} A(n+1) = n+1 + \binom{n+1}{4} + \binom{n}{2} \end{eqnarray}$ nachzuweisen, musst du doch nur die Übereinstimmung der Differenz $\begin{eqnarray} \left( n+1 + \binom{n+1}{4} + \binom{n}{2} \right) - \left( n + \binom{n}{4} + \binom{n-1}{2} \right) \end{eqnarray}$ mit der Summe $\begin{eqnarray} \sum_{k=1}^n (1+(k-1)(n-k)) \end{eqnarray}$ nachweisen. Also alles schön ausmultiplizieren und bei letzterer Summe die bekannten Summenformeln $\begin{eqnarray} \sum_{k=1}^n k = \frac{n(n+1)}{2}, \quad \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6} \end{eqnarray}$ nutzen. EDIT: Es gibt auch einen direkten kombinatorischen Beweis: Die $\begin{eqnarray} A(n) \end{eqnarray}$ Teilflächen unterteilen sich in $\begin{eqnarray} n \end{eqnarray}$ Kreissegmente und $\begin{eqnarray} F \end{eqnarray}$ innerhalb des $\begin{eqnarray} n \end{eqnarray}$ -Ecks liegende Polygonflächen. Letztere lassen sich über den Eulerschen Polyedersatz der Ebene $\begin{eqnarray} F=K-E+1 \end{eqnarray}$ bestimmen, dabei ist $\begin{eqnarray} K \end{eqnarray}$ die Kantenzahl und $\begin{eqnarray} E \end{eqnarray}$ die Anzahl der Ecken. Letztere ist $\begin{eqnarray} E=n+\binom{n}{4} \end{eqnarray}$ , erstere kann man über $\begin{eqnarray} 2K = 4\binom{n}{4} + n(n-1) \end{eqnarray}$ berechnen. Alles schön zusammengerührt zu $\begin{eqnarray} A(n)=n+F \end{eqnarray}$ kommt man auf die angegebene Anzahl.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »