Aloha :)
Um zu zeigen, dass \(\binom{n}{k}\in\Theta(n^k)\) gilt, zeigen wir dass \(\binom{n}{k}\in O(n^k)\) und \(\binom{n}{k}\in\Omega(n^k)\) gilt.
Mit der folgenden Abschätzung:$$\binom{n}{k}=\frac{n!}{k!\cdot(n-k)!}=\frac{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)\cdot(n-k)!}{k!\cdot(n-k)!}$$$$\phantom{\binom{n}{k}}=\frac{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}{k!}\le\frac{n^k}{k!}$$können wir folgende weitere Abschätzung treffen:$$\lim\limits_{n\to\infty}\frac{\binom{n}{k}}{n^k}\le\lim\limits_{n\to\infty}\frac{\frac{n^k}{k!}}{n^k}=\lim\limits_{n\to\infty}\frac{1}{k!}=\frac{1}{k!}<\infty\implies\binom{n}{k}\in O(n^k)$$
Mit der weiteren Abschätzung:$$\binom{n}{k}=\frac{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}{k!}\ge\frac{(n-k+1)^k}{k!}$$können wir folgende weitere Abschätzung treffen:$$\lim\limits_{n\to\infty}\frac{\binom{n}{k}}{n^k}\ge\lim\limits_{n\to\infty}\frac{\frac{(n-k+1)^k}{k!}}{n^k}=\frac{1}{k!}\lim\limits_{n\to\infty}\left(1-\frac{k-1}{n}\right)^k=\frac{1}{k!}>0\implies\binom{n}{k}\in \Omega(n^k)$$
