Beweis einer Teilbarkeitsaussage

10.10.2021, 17:30

ilovemath

Beweis einer Teilbarkeitsaussage

Guten Abend, ich habe eine Frage zu einem Beweis. Könnt ihr mir dabei behilflich sein?

Zu zeigen ist, dass für $\begin{eqnarray*} n\in\mathbb{N} \end{eqnarray*}$ gilt: $\begin{eqnarray*} \dfrac{(2n)!}{n!^2} \end{eqnarray*}$ ist immer durch $\begin{eqnarray*} n+1 \end{eqnarray*}$ teilbar. Ich hab es auch zwei verschiedenen Wegen probiert, die mich beide nicht ganz zum Endergebnis führen:

(1) Vollständige Induktion
Im Induktionsschritt muss gezeigt werden, dass $\begin{eqnarray*} \dfrac{(2n+2)!}{(n+1)!^2} = 2\dfrac{2n+1}{n+1}\dfrac{(2n)!}{n!^2} \end{eqnarray*}$ durch $\begin{eqnarray*} n+2 \end{eqnarray*}$ teilbar ist. Nach Verwendung der Induktionsvoraussetzung komme ich nicht weiter.

(2) direkt
Mit Hilfe einer anderen Schreibweise $\begin{eqnarray*} \dfrac{(2n)!}{n!^2} = \dfrac{2^n}{n!}\cdot\dfrac{(2n)!}{2^nn!} = \dfrac{2^n}{n!}\prod_{k=1}^n(2k-1) \end{eqnarray*}$ ist zumindest ersichtlich, dass sich im Zähler der Term durch $\begin{eqnarray*} n+1 \end{eqnarray*}$ teilen lässt. Aber dann ist mir noch nicht klar, dass nach dem Dividieren durch $\begin{eqnarray*} n! \end{eqnarray*}$ wirklich eine natürliche raus kommt.

10.10.2021, 17:36

Leopold

Auf diesen Beitrag antworten »

Das ist ein Binomialkoeffizient, nämlich $\begin{align*} {{2n} \choose n} \end{align*}$ . Und Binomialkoeffizienten sind immer ganz. Allgemein gilt ja

$\begin{align*} {n \choose k} = \frac{n!}{k! (n-k)!} = \frac{(n)_k}{k!} \end{align*}$

wobei $\begin{align*} (n)_k = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1) \end{align*}$ gemeint ist. Nutze in deinem Fall die zweite Darstellung.

10.10.2021, 18:15

ilovemath

Auf diesen Beitrag antworten »

Danke Leopold für deine schnelle Antwort. Aus der Darstellung $\begin{eqnarray*} (2n)_n = 2n\cdot(2n-1)\cdot\dots\cdot(n+1) \end{eqnarray*}$ ist ersichtlich, dass der Zähler durch $\begin{eqnarray*} n+1 \end{eqnarray*}$ teilbar ist. Doch wieso ist für dich klar, dass der Bruch auch nach zusätzlichem Teilen durch $\begin{eqnarray*} n+1 \end{eqnarray*}$ weiterhin eine natürliche Zahl bleibt? Vielleicht war ja gerade dieser Faktor $\begin{eqnarray*} n+1 \end{eqnarray*}$ im Zähler wichtig, um sich am Ende vollständig mit dem $\begin{eqnarray*} n! \end{eqnarray*}$ im Nenner zu kürzen. Und da er jetzt weg ist, fehlt er doch vielleicht, oder?

10.10.2021, 19:25

Mathema

Auf diesen Beitrag antworten »

Siehe dort:

https://de.wikipedia.org/wiki/Catalan-Zahl

10.10.2021, 19:31

ilovemath

Auf diesen Beitrag antworten »

Das ist stark, damit hab ich jetzt nicht gerechnet xD

Habt ihr aber zusätzlich auch eine Idee, wie es mit dem Induktionsbeweis hätte weiter gehen können, wie in (1) beschrieben?

10.10.2021, 22:11

HAL 9000

Auf diesen Beitrag antworten »

Ist jetzt der Olympiade-Abgabeschluss SICHER verstrichen (ich hatte irgendwo mal gelesen, dass es in manchen Regionen erst der 15.10. ist)? Erstaunlicherweise war das ja eine diesjährige Erstrundenaufgabe (die hier im Forum in den letzten Wochen schon mehrfach gepostet wurde).

10.10.2021, 22:28

ilovemath

Auf diesen Beitrag antworten »

Haha ok ich hab keine Ahnung wovon du sprichst. Mir hat ein ehemaliger Nachhilfeschüler diese Aufgabe geschickt und ich war verwundert, warum ich nicht weiter komme.

Aber noch mal zurück zur Frage: Ist es nicht auch möglich mit vollständiger Induktion zu arbeiten oder ohne die Argumentation mit den Catalan Zahlen?

10.10.2021, 23:55

HAL 9000

Auf diesen Beitrag antworten »

Nachhilfeschüler und Mathematik-Olympiade - diese kuriose Kombination entlockt wiederum mir ein "Haha".

11.10.2021, 10:35

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Nachhilfeschüler und Mathematik-Olympiade - diese kuriose Kombination entlockt wiederum mir ein "Haha".

In der Tat kurios. Sehen wir es so: Wer Mathematik so liebt wie unser Fragesteller, kann auch Nachhilfeschüler zu Höchstleistungen motivieren. Da wird aus einer Eva Zwerg schnell ein Adam Riese. Augenzwinkern

11.10.2021, 14:28

HAL 9000

Auf diesen Beitrag antworten »

Ok, wenn ~~Leopold und~~ Mathema sich sicher ~~sind~~ ist, dass der Abgabeschluss vorüber ist, dann auch mal was zum Thema:

Nicht immer ist ein Induktionsbeweis eine gute Idee, eine Aussage zu natürlichen Zahlen zu beweisen: Manchmal funktioniert es einfach nicht, die Induktionsvoraussetzung in brauchbarer Weise zum Beweis der Induktionsbehauptung einzusetzen. Deinen Versuch (1) würde ich in diesem Rahmen einordnen - daher steig von dem Pferd ab, es ist tot.

Das soll nicht heißen, dass Induktionsbeweis hier generell eine schlechte Idee ist: Man kann per Vollständiger Induktion nachweisen, dass alle Binomialkoeffizienten ganze Zahlen sind (sofern man das nicht sowieso schon als bekannt voraussetzen darf) und nutzt dann die oben verlinkte Differenzdarstellung der Catalan-Zahl - schon ist man fertig.

EDIT: Korrigiert (s.u.), es ist nur Mathema. Der allerdings kennt wohl einen Gutteil der bisherigen Betrugsversuche hinsichtlich dieser Aufgabe.

11.10.2021, 20:06

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Ok, wenn Leopold und Mathema sich sicher sind, dass der Abgabeschluss vorüber ist

Dazu habe ich nichts gesagt. Mir war nicht bekannt, daß das eine Wettbewerbsaufgabe ist. Ich hatte auch nicht mitverfolgt, wie oft und in welcher Gestalt diese Anfrage bereits gestellt wurde.

11.10.2021, 21:48

HAL 9000

Auf diesen Beitrag antworten »

Ok, hab dich raus (und damit aus der Verantwortung) genommen. Augenzwinkern

Neue Frage »

Antworten »

Beweis einer Teilbarkeitsaussage

Verwandte Themen