Formel mithilfe des doppelten Abzählens beweisen

Question

Hallöchen,

ich soll folgende Formel mithilfe des doppelten Abzählens beweisen:

\( \left(\begin{array}{c}m+n \\ 2\end{array}\right)-\left(\begin{array}{c}m \\ 2\end{array}\right)-\left(\begin{array}{c}n \\ 2\end{array}\right)=m n \)

Leider fehlt mir glaube ich der richtige Ansatz, ich habe bereits probiert die linke Seite umzustellen, sodass sie mit der rechten übereinstimmt, bin daran aber auch gescheitert.

Answer 1

Rechnerischer Beweis

(m + n)·(m + n - 1)/2 - m·(m - 1)/2 - n·(n - 1)/2 = m·n
(m + n)·(m + n - 1) - m·(m - 1) - n·(n - 1) = 2·m·n
(m^2 + 2·m·n - m + n^2 - n) - (m^2 - m) - (n^2 - n) = 2·m·n
(m^2 + 2·m·n - m + n^2 - n) - (m^2 - m) - (n^2 - n) = 2·m·n
2·m·n = 2·m·n

Aber Achtung. Dieses ist nicht das Prinzip des doppelten Abzählens.

Beim doppelten Abzählen versucht man die Mächtigkeit zweier Mengen verschieden abzuzählen.

(m + n über 2) beschreibt die Anzahl der Möglichkeiten 2 Elemente aus einer einer m + n Elementigen Menge auszuwählen.

(m über 2) beschreibt die Anzahl der Möglichkeiten 2 Elemente aus einer m Elementigen Menge auszuwählen.

(n über 2) beschreibt die Anzahl der Möglichkeiten 2 Elemente aus einer n Elementigen Menge auszuwählen.

(m + n über 2) - (m über 2) - (n über 2) Da wir hier von der Gesamtanzahl der Möglichkeiten 2 Elemente auszuwählen die Abziehen bei denen beide Elemente aus den m Elementen oder den n Elementen stammen, bleiben die Möglichkeiten über ein Element aus den m Elementen und ein Element aus den n Elementen auszuwählen. Dieses sind aber genau m * n Möglichkeiten

Answer 2

(m+n)(m+n-1)/2 - m(m-1)/2 - n(n-1)/2 =

(m²+2mn-m+n²-n)/2- (m²-m)/2 - (n²-n)/2 = 2mn/2 = mn