Vollständige Induktion | Beweisen Sie die Formel für die Anzahl Strecken, die n Punkte verbinden.

Question

Aufgabe:

\( \mathrm{S}(\mathrm{n}) \) sei die Anzahl der Strecken, die benötigt werden, um in einer Menge von \( \mathrm{n} \) Punkten jeden Punkt mit jedem anderen zu verbinden. Für alle \( \mathrm{n} \in \mathrm{IN} \) gilt:
\( S(n)=\frac{n(n-1)}{2} \)

Im Folgenden finden Sie den Beweis dieser Behauptung, jedoch ist der Induktionsschluss nicht vollständig dragestellt. Ergänzen Sie, was fehlt. Beweis durch vollständige Induktion:

Induktionsanfang: \( S(0)=0, \frac{0(0-1)}{2}=0 \)

Induktionsannahme: Für \( \mathrm{k} \in \mathrm{IN} \) gilt: \( \mathrm{S}(\mathrm{k})=\frac{\mathrm{k}(\mathrm{k}-1)}{2} \)
Induktionsschritt: Sei \( n=k+1 \).

Wir zeigen, dass dann \( S(n)=\frac{n(n-1)}{2} \) gilt:

Es ist nämlich \( S(n)=S(k+1)=S(k)+k= \)


Ich weiß, wie die vollständige Induktion bei der Gauß'schen Summenformel geht, hier komme ich aber nicht weiter.

Answer 1

S(n) = S(k+1) = S(k) + k       |Indvor. S(k) einsetzen

= k(k-1)/2 + k

=(k^2 - k)/2 + 2k/2

= (k^2 + k)/2

=(k+1)k/2 = S(k+1) qed. Induktionsschritt.

Comments

Dankeschön, da hab ich mich aber blöd angestellt... :|