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 \mathrm{\infty }$:

$(\genfrac{}{}{0ex}{}{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 $\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}=1$. Dies brauchen wir nur noch auf die Angabe anwenden.

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n(n-1)\cdots (n-(k-1))}{k!}$

$a_n=(\genfrac{}{}{0ex}{}{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:

$\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}=\underset{n\to \mathrm{\infty }}{lim}((1+\frac{k-1}{n})(1+\frac{k-2}{n})\cdots (1+\frac{k-k}{n}))=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)