Binomialkoeffizient ist ganze Zahl, Beweis gesucht

19.12.2021, 16:58

Malcang

Binomialkoeffizient ist ganze Zahl, Beweis gesucht

Guten Tag zusammen smile

für meine Ausarbeitung suche ich einen Beweis, dass $\begin{eqnarray*} \begin{pmatrix}n\\k\end{pmatrix} \end{eqnarray*}$ für ganze Zahlen $\begin{eqnarray*} n,k \end{eqnarray*}$ wieder ganzzahlig ist.
Diesen möchte ich referenzieren und nicht nochmal in meiner Arbeit ausformulieren.
Bisher habe ich nur in

Zitat:

Griser, Daniel - Analysis 1

einen Beweis gefunden, allerdings in anderen Beweisen verschachtelt. Ich suche die Aussage als Satz, das wäre mir am liebsten.
Wisst ihr vielleicht gerade ein Buch?
Ich habe durchgesehen die Analysis 1 Bücher von Behrends, Forster und Walter.
Außerdem Grundwissen Mathematik von Arens et al, aber dort wurde ich leider nicht fündig.

Schönen Sonntag smile

19.12.2021, 17:07

Leopold

Auf diesen Beitrag antworten »

1. Der Binomialkoeffizient löst ein spezielles kombinatorisches Problem und ist aufgrund dessen von selbst eine positive ganze Zahl.

2. Mit der Rekursion $\begin{align*} {n \choose {k-1}} + {n \choose k} = {{n+1} \choose k} \end{align*}$ und den Randwerten $\begin{align*} {n \choose 0} = {n \choose n} = 1 \end{align*}$ folgt iterativ die Ganzzahligkeit.

19.12.2021, 17:11

Malcang

Auf diesen Beitrag antworten »

Hallo Leopold,

danke für deine Antwort.

Zitat:

Original von Leopold
1. Der Binomialkoeffizient löst ein spezielles kombinatorisches Problem und ist aufgrund dessen von selbst eine positive ganze Zahl.

In dieser Form ist es bei Grieser auch geführt, ich wollte das gerne etwas "analytischer" haben. Aber zur Not würde ich diesen Beweis referenzieren.

Zitat:

2. Mit der Rekursion $\begin{align*} {n \choose {k-1}} + {n \choose k} = {{n+1} \choose k} \end{align*}$ und den Randwerten $\begin{align*} {n \choose 0} = {n \choose n} = 1 \end{align*}$ folgt iterativ die Ganzzahligkeit.

Das erscheint mir wieder zu viel des guten. Dann müsste ich ja diese Rekursion wiederum definieren. Ich hatte gehofft, das mit einer Referenz erschlagen zu können Augenzwinkern

19.12.2021, 17:27

Leopold

Auf diesen Beitrag antworten »

Die Rekursion kannst du mit der Darstellung

$\begin{align*} {n \choose k} = \frac{(n)_k}{k!} = \frac{\prod_{j=0}^{k-1} (n-j)}{\prod_{j=0}^{k-1} (k-j)} \end{align*}$

sofort herleiten.

19.12.2021, 17:32

Mathema

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu

Zitat:

Original von Leopold
1. Der Binomialkoeffizient löst ein spezielles kombinatorisches Problem und ist aufgrund dessen von selbst eine positive ganze Zahl.

In dieser Form ist es bei Grieser auch geführt, ich wollte das gerne etwas "analytischer" haben. Aber zur Not würde ich diesen Beweis referenzieren.

Du wolltest doch aber $\begin{eqnarray*} n,k \in \mathbb{Z} \end{eqnarray*}$ haben, oder nicht? Du müsstest vll erstmal sagen, welche Definition du denn für den Binomialkoeffizient verwendest:

[attach]54180[/attach]

19.12.2021, 17:34

Malcang

Auf diesen Beitrag antworten »

Ich wollte halt gerne etwas schreiben wie
"Der folgende Beweis benutzt, dass $\begin{eqnarray*} \begin{pmatrix}n\\k\end{pmatrix} \end{eqnarray*}$ ganzzahlig ist. Dies lässt sich in [abc123] nachlesen."

19.12.2021, 17:47

Leopold

Auf diesen Beitrag antworten »

Daß Binomialkoeffizienten ganze Zahlen sind, ist Allgemeingut der Mathematiker. Da benötigt man keine Referenz, ebenso wenig wie darauf, daß minus mal minus plus ergibt.

19.12.2021, 17:48

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von Mathema

Zitat:

Original von ichwarneu

Zitat:

Original von Leopold
1. Der Binomialkoeffizient löst ein spezielles kombinatorisches Problem und ist aufgrund dessen von selbst eine positive ganze Zahl.

In dieser Form ist es bei Grieser auch geführt, ich wollte das gerne etwas "analytischer" haben. Aber zur Not würde ich diesen Beweis referenzieren.

Du wolltest doch aber $\begin{eqnarray*} n,k \in \mathbb{Z} \end{eqnarray*}$ haben, oder nicht? Du müsstest vll erstmal sagen, welche Definition du denn für den Binomialkoeffizient verwendest:

Hallo Mathema,

ich habe deine Antwort gerade erst gesehen.
Puh, das geht ja doch weiter als ich dachte.
Ich bräuchte eigentlich nichts anderes als die Darstellung $\begin{eqnarray*} \frac{n!}{k!(n-k)!} \end{eqnarray*}$ .
Hm ich muss wirklich nochmal überlegen, wie ich das aufbaue. Ich will ja auch nichts vergessen. Am nächsten kommt meinem Anliegen deine Definition (1)

19.12.2021, 17:50

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Daß Binomialkoeffizienten ganze Zahlen sind, ist Allgemeingut der Mathematiker. Da benötigt man keine Referenz, ebenso wenig wie darauf, daß minus mal minus plus ergibt.

Das mag sein, Leopold, aber in meiner Ausarbeitung muss ich beispielsweise auch den kleinen Fermat anführen oder die geometrische Summenformel. Auch wenn das natürlich Standardwerkzeug ist.

19.12.2021, 18:58

HAL 9000

Auf diesen Beitrag antworten »

Wenn man die inhaltliche Verbindung zu den Kombinationen im Beweis nicht bringen will, dann ist m.E. Variante 2 von Leopold die beste Beweisoption - ob du das nun "zuviel des guten" nennst oder nicht.

Alle Versuche, für $\begin{eqnarray*} \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdot \ldots (n-k+1)}{k!} \end{eqnarray*}$ "direkt" nachzuweisen, dass alle Faktoren des Nenners "irgendwie" weggekürzt werden sollen, enden in der Regel mit ziemlicher Pfuscherei - dergleichen habe ich schon viel zu oft auch hier im Forum besichtigen können/müssen. Nein, da ist diese o.g. Variante 2 die wesentlich angenehmere Idee.

19.12.2021, 19:35

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
2. Mit der Rekursion $\begin{align*} {n \choose {k-1}} + {n \choose k} = {{n+1} \choose k} \end{align*}$ und den Randwerten $\begin{align*} {n \choose 0} = {n \choose n} = 1 \end{align*}$ folgt iterativ die Ganzzahligkeit.

Wenn Du schon referierst, dann solltest Du auch das Pascalsche Dreieck erwähnen. Dabei wird die oben von Leopold angegebene Formel zum Aufbau verwendet.

19.12.2021, 19:39

HAL 9000

Auf diesen Beitrag antworten »

Man kann das Pascalsche Dreieck erwähnen, weil dort diese Rekursion eine Rolle spielt. Zum oben diskutierten Beweis nötig ist das aber nicht.

19.12.2021, 20:00

Malcang

Auf diesen Beitrag antworten »

Ich danke euch sehr, ihr Lieben. Das hat mir nicht nur tiefere Einsicht in meine Frage gegeben, ich habe sogar noch ein weiteres Problem in meiner Arbeit entdeckt. Dazu würde ich aber gerne einen neuen Thread aufmachen.
Was meine Frage hier betrifft, werde ich mich in der Tat der Rekursion zuwenden und die Definitionen vernünftig anführen.

Ich danke euch allen sehr smile

Neue Frage »

Antworten »

Binomialkoeffizient ist ganze Zahl, Beweis gesucht

Verwandte Themen