Beweise anhand direkter Rechnung

Question

Aufgabe:

Zeige für mn aus N mit m>n, dass \( \begin{pmatrix} m\\k \end{pmatrix} \) < \( \begin{pmatrix} n\\k \end{pmatrix} \) mit k von 1,…,n

Comments

Das zweite < muss > heißen, damit man das Zeigen kann.

---

Hopsi ich meine beides mal ein < zeichen

Answer 1

\( \begin{pmatrix} m\\k \end{pmatrix} \)=\( \frac{m·(m-1)·(m-2)·....}{1·2·...·k} \) k Faktoren im Zähler. Das Gleiche für n statt n. Dann beide mit 1·2·...·k multiplizieren. Dann hat für m>n \( \frac{m·(m-1)·(m-2)·....}{} \) die größeren k Faktoren.

Comments

Dann hat für m>n

Durch die Korrektur des Fragestellers muss die Antwort etwas ausführlicher ausfallen.

---

Hee, schaut das dann so aus?

m über k =(m*(m-1)*(m-2)…/k!)=(m*(m-1)*(m-2)…/k!)*k!= m*(m-1)*(m-2)…< n*(n-1)*(n-2)…=(n*(n-1)*(n-2)…/k!)*k! =(n*(n-1)*(n-2)…/k!)

Ist das ein Beweis, also wenn ich jz noch begründe das somit müberk <nüber k aufgrund der Voraussetzung das m<n ist, da ka m damit weniger faktoren besitzt?

---

Da stimmt einiges nicht.

---

Ja, aber was? Wie gehörts? ich dachte im kommentar oben stehts auch so

---

(m*(m-1)*(m-2)…)/k!< (n*(n-1)*(n-2)…)/k!

jetzt auf beiden Seiten · k!.

m*(m-1)*(m-2)…< n*(n-1)*(n-2)…

Anzahl der Faktoren auf beiden Seiten gleich. Weil m>n stehen links die höheren Faktoren.

---

Achso aber dann hatte ich grundsätzlich nur die argumentation falsch oder?

---

...vor allem die schrittweise Darstellung des Gedankenganges fehlte mir.

---

Naja eigentlich hab ich das schöner aufgeschrieben, aber hier kann ich das nicht so gut darstellen

---

Naja eigentlich hab ich das schöner aufgeschrieben, ...

schön aufgeschrieben könnte das so aussehen: $$m\lt n, \quad k \gt 0 \implies: \\ \begin{aligned} {m \choose k} &\stackrel{?}\lt {n \choose k} \\ \frac{m!}{k!(m-k)!} &\stackrel{?}\lt\frac{n!}{k!(n-k)!} &&|\,\cdot k!(m-k)!(n-k)!\\ m!(n-k)! &\stackrel{?}\lt n!(m-k)! \\ \prod\limits_{i=1}^{m}i\space \cdot \prod\limits_{i=1}^{n-k}i\space &\stackrel{?}\lt \prod\limits_{i=1}^{n}i\space \cdot \prod\limits_{i=1}^{m-k}i &&|\,\div m! \\ \prod\limits_{i=1}^{n-k}i\space &\stackrel{?}\lt \prod\limits_{i=m+1}^{n}i\space \cdot \prod\limits_{i=1}^{m-k}i &&|\,\div (m-k)! \\ \prod\limits_{i=m-k+1}^{n-k}i\space &\stackrel{?}\lt \prod\limits_{i=m+1}^{n}i &&|\,(i=j-k) \\ \prod\limits_{j=m+1}^{j=n}(j-k)\space &\lt \prod\limits_{i=m+1}^{n}i &&\checkmark \\ \end{aligned}$$beide Produkte haben offensichtlich die gleiche Anzahl \(a\) von Faktoren und man kann die Faktoren eindeutige \(a\) Paaren zuordnen, so dass der Faktor aus dem linken Produkt immer kleiner ist als der aus dem rechten Produkt.

---

Faktor aus dem linken Produkt immer kleiner ist als der aus dem rechten Produkt.

Das Problem, auf das ich oben schon hingewiesen habe, ist, dass k > m zugelassen ist, wodurch negative Faktoren auftreten können.
Nun ist zwar   -5<2 und -4<3  aber (-5)*(-4) > 2*3.

Mit meinem "etwas ausführlicher" oben meinte ich den Hinweis auf den Faktor 0 in einem solchen Fall.

---

Das Problem, auf das ich oben schon hingewiesen habe, ist, dass k > m zugelassen ist, ..

das war mir auch aufgefallen. Ich hielt das für einen Fehler in der Aufgabenstellung ;-). Sinvoll ist sicher \(k\in[1;\,m]\)

---

Dankeschön für die Hilfe

---

Ich hätte doch noch eine Frage, wie kommt man auf die letzte zeile durch indexverschiebung?

---

Ich hätte doch noch eine Frage, wie kommt man auf die letzte zeile durch indexverschiebung?

Möchtest Du wissen, wie man darauf kommt? D.h. welche Gedankengänge notwendig sind, um zu sehen, Aha! mit Indexverschiebung kommt man der Lösung näher?

Die Antwort wäre dann: ich habe in beiden Produkten die Anzahl der Faktoren bestimmt, und gesehen, dass diese identisch ist. Man kann auch einfach mal ein Zahlenbeispiel einsetzen. Das ist immer eine Möglichkeit.

---

Wie meinst du ds mit fakoren bestimmt?

---

Wie meinst du ds mit fakoren bestimmt?

Nicht die Faktoren, sondern deren Anzahl. Mache Dir das an Hand eines Zahlenbeispiels klar. Zum Beispiel für \(k=2\), \(m=4\) und \(n=7\):$$\begin{aligned}{4\choose 2 } &\lt {7\choose 2} \\ \frac{4!}{2! \cdot 2!} &\lt \frac{7!}{2! \cdot 5!}&&|\, \cdot(k! = 2!) \\ \frac{4!}{2!} &\lt \frac{7!}{5!} \\ \underbrace{3 \cdot 4}_{k\space \text{Faktoren}} &\lt \underbrace{6 \cdot 7}_{k\space \text{Faktoren}}\end{aligned}$$es bleiben auf beiden Seiten \(k\) Faktoren stehen, wenn man das \((m-k)!\) auf der linken und das \((n-k)!\) auf der rechten Seite gekürzt hat.

Und wenn man diese paarweies vergleicht - also in diesem Fall \(3 \lt 6\) und \(4 \lt 7\) - so steht rechts das größere Produkt.

---

Danke für die ausführliche erklärung jz is es klarer!