Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Binomialkoeffizienten und Exponentialfunktion

Binomialkoeffizienten und Exponentialfunktion

Universität / Fachhochschule

Folgen und Reihen

Tags: Binomialkoeffizient, Exponentialfunktion, Folgen und Reihen

LeiderkeinNerd aktiv_icon

13:26 Uhr, 21.09.2019

Hallo zusammen,

ich schreibe gerade meine Zulassungsarbeit und benutze in einem Beweis folgende asymptotische Äquivalenz:

\frac{(\binom{(\binom{n - r}{2})}{N})}{(\binom{(\binom{n}{2})}{N})} \sim e^{\frac{- 2 r N}{n}}

für

N = O (n^{3 / 2}), r \in ℝ

.

Ich würde diese gerne beweisen, aber das Buch, aus welchem ich die Formel habe, gibt keinen Hinweis, wo ich einen Beweis dazu finden kann und gibt selbst nur sehr spärliche Hinweise, wie sie zu beweisen ist ("mit etwas Arbeit mit Stirlings Formel kann man zeigen..."). Es wird aus folgender asymptotischer Äquivalenz als Spezialfall gefolgert, was ich selbst auch noch nachvollziehen kann:

\frac{(\binom{a}{k})}{(\binom{b}{k})} \sim e^{\frac{(a - b) k}{b}}

für

k \frac{b - a}{b^{2}} \to 0

, sowie

k (\frac{b - a}{b - k})^{2} \to 0

und von n abhängigen Funktionen k, a, b.

Nun meine Frage: Kann mir jemand ein Buch/ einen Artikel o.ä. empfehlen, in dem ich Zusammenhänge zwischen der Exponentialfunktion und Binomialkoeffizienten finden kann? Oder weiß jemand, wie ich an den Beweis der oberen oder auch der unteren Äquivalenz herangehen kann? Ich nehme natürlich auch gerne fertige Beweise, freue mich aber wirklich über jeden Ratschlag!

Was ich selbst schon vermute: Die Exponentialreihe wird hierfür irgendwie umgeformt und scheinbar wird auch Stirlings Formel verwendet.

Der Autor schreibt ja selbst schon, dass es viel Arbeit macht und ich bin leider selbst kein Analysis-Genie, sodass mir für einen eigenen Beweis die nötigen Formeln für Umformungen fehlen.

Ganz liebe Grüße und schonmal vielen Dank für eure Hilfe!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Allgemeine Exponentialfunktion - Einführung
Allgemeine Exponentialfunktion - Fortgeschritten
Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

Zu diesem Thema passende Musteraufgaben einblenden

supporter aktiv_icon

15:11 Uhr, 21.09.2019

Hast die die Koeffizienten schon aufgelöst und zusammengefasst?

LeiderkeinNerd aktiv_icon

22:40 Uhr, 21.09.2019

Den zweiten Bruch würde ich so vereinfachen:

\frac{(\binom{a}{k})}{(\binom{b}{k})} = \frac{a! (b - k)!}{b! (a - k)!} = \frac{a (a - 1) . . . (a - k + 1)}{b (b - 1) . . . (b - k + 1)}

Ich denke, die erste Formel ist bei meinem Problem zweitrangig, da ich von der allgemeineren zweiten Formel schon die Schritte zur ersten gefunden habe. Aber für die erste Formel würde man dann

a = \frac{(n - r) (n - r - 1)}{2}

und

b = \frac{(n) (n - 1)}{2}

setzen.

Ich habe jetzt auch (in die übersichtlichere) mal Stirlings Formel eingesetzt, dann erhält man:

\frac{a! (b - k)!}{b! (a - k)!} \sim \frac{\sqrt{a (b - k)} a^{a} (b - k)^{b - k}}{\sqrt{b (a - k)} b^{b} (a - k)^{a - k}}

Jetzt wäre ja der nächste Schritt, die Voraussetzungen einzusetzen, aber das sieht noch nicht so aus, als würde das so leicht klappen. Kannst du mir dabei helfen?

HAL9000

11:29 Uhr, 23.09.2019

Zunächst mal schreiben wir die innerste Stufe mal aus:

a := \frac{(\binom{(\binom{n - r}{2})}{N})}{(\binom{(\binom{n}{2})}{N})} = \frac{(\binom{\frac{(n - r) (n - r - 1)}{2}}{N})}{(\binom{\frac{n (n - 1)}{2}}{N})}

.

Weiter umgeformt bekommt man

a = \prod_{k = 0}^{N - 1} \frac{\frac{(n - r) (n - r - 1)}{2} - k}{\frac{n (n - 1)}{2} - k} = \prod_{k = 0}^{N - 1} (1 - \frac{2 r n - r (r + 1)}{n (n - 1) - 2 k}) = \prod_{k = 0}^{N - 1} (1 - \frac{2 r - \frac{r (r + 1)}{n}}{n (1 - \frac{1}{n} - \frac{2 k}{n^{2}})})

Wegen

N = O (n^{3 / 2})

ist

\frac{k}{n^{2}} = O (n^{- 1 / 2})

, nutzt man außerdem

\exp (- x) = 1 - x + O (x^{2})

, dann steht die Behauptung da. Kann sein, dass man es mit Stirling auch hinkriegt - nötig ist die Anwendung der Stirlingformel aber nicht.

EDIT: Ich muss doch nochmal genau nachfragen: Steht da wirklich

N = O (n^{3 / 2})

oder doch eher

N = o (n^{3 / 2})

? Ersteres scheint mir nämlich nicht ausreichend, zweiteres hingegen schon.

LeiderkeinNerd aktiv_icon

23:39 Uhr, 23.09.2019

Vielen lieben Dank!

Oh, da hast du tatsächlich Recht! Muss

N = o (n^{3 / 2})

heißen.
Nur zum Verständnis: Durch

N = o (n^{3 / 2})

kann man im Nenner

n (1 - \frac{1}{n} - \frac{2 k}{n^{2}}) = n (1 - \frac{1}{n} - o (\frac{1}{\sqrt{n}})) = n (1 - o (1)) \sim n

rechnen?
Und mit

N = O (n^{3 / 2})

würde man nur

n (1 - \frac{1}{n} - \frac{2 k}{n^{2}}) = n (1 - \frac{1}{n} - O (n^{- 1 / 2})) = n (1 - o (1)) - O (\sqrt{n}) \sim n - O (\sqrt{n})

erhalten?

Und.. Die Frage ist hier vllt. etwas unpassend... Aber wie müsste ich das jetzt zitieren?

HAL9000

00:34 Uhr, 24.09.2019

Nein, die Rechnung geht so weiter:

\dots = \prod_{k = 0}^{N - 1} (1 - \frac{2 r}{n} \cdot \frac{1 - \frac{r + 1}{2 n}}{1 - \frac{1}{n} - \frac{2 k}{n^{2}}}) = \prod_{k = 0}^{N - 1} (1 - \frac{2 r}{n} \cdot (1 + o (n^{- 1 / 2}))) = \prod_{k = 0}^{N - 1} (1 - \frac{2 r}{n} + o (n^{- 3 / 2}))

= \prod_{k = 0}^{N - 1} \exp (- \frac{2 r}{n} + o (n^{- 3 / 2})) = \exp (- \frac{2 r N}{n} + N \cdot o (n^{- 3 / 2})) = \exp (- \frac{2 r N}{n} + o (1))

Mit

N = O (n^{3 / 2})

würde in der letzten Zeile nur

O (1)

statt

o (1)

stehen, was nicht ausreicht.

1480888

1480689

	Status: nicht eingeloggt	Noch nicht registriert?