TU Wien:Analysis VU (diverse)/Übungen 2024S/Beispiel 103

Zeigen Sie die folgende asymptotische Beziehung für die Anzahlen der Kombinationen mit bzw. ohne Wiederholungen für festes $k$ und $n\to \infty$:

${\binom {n+k-1}{k}}\sim {\frac {n^{k}}{k!}}$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag

Wir wissen: $a_{n}\sim b_{n}$ ($a_{n}$ ist asymptotisch gleich $b_{n}$), falls $\lim _{n\to \infty }{\frac {a_{n}}{b_{n}}}=1$. Dies brauchen wir nur noch auf die Angabe anwenden.

${\binom {n}{k}}={\frac {n(n-1)\cdots (n-(k-1))}{k!}}$

$a_{n}={\binom {n+k-1}{k}}={\frac {(n+k-1)(n+k-2)\cdots (n+k-1-(k-1))}{k!}}$

Aus diesem Term kann man nun $n$ herausheben:

${\frac {n^{k}(1+{\frac {k-1}{n}})(1+{\frac {k-2}{n}})\cdots (1+{\frac {k-k}{n}})}{k!}}$

$b_{n}={\frac {n^{k}}{k!}}$

Wenn man nun den Grenzwert von ${\frac {a_{n}}{b_{n}}}$ berechnet, kürzt sich $n^{k}$ und $k!$ weg. Die Brüche gehen gegen $0$, wodurch nur mehr $1$ übrig bleibt:

$\lim _{n\to \infty }{\frac {a_{n}}{b_{n}}}=\lim _{n\to \infty }\left(\left(1+{\frac {k-1}{n}}\right)\left(1+{\frac {k-2}{n}}\right)\cdots \left(1+{\frac {k-k}{n}}\right)\right)=1$

Somit sind die beiden Terme asymptotisch gleich.

-- Berti933 (Diskussion) 12:44, 18. Mai 2015 (CEST)

Links

• TU Wien:Analysis UE (diverse)/Übungen SS13/Beispiel 102 (ähnliches Beispiel)