Zeige das (n über k) = Θ(nk)

Question

Aufgabe:

Zeige das (n über k) = Θ(n^k)

Problem/Ansatz:

Was ich mir bis jetzt überlegt habt: Binomialkoeffizient umformen und dann das k durch (n/2) ersetzen, da dass das größte Ergebnis für den Binomialkoeffizienten liefern kann(wenn man also beweist, dass der größte wert des binomialkoeffizienten kleiner ist als n^k dann müsste hätte man ja schonmal den 1. Teil des beweises wenn ich mich nicht irre). Jetzt weiß ich allerdings absolut nicht wie ich weiter verfahre(whrs. weil ich auf nem komplett falschem weg bin). Mir ist natürlich klar, dass ich eig. zeigen muss dass  (n über k) = Ο(n^k) und (n über k) =  Ω(n^k). Wie ich das mache weiß ich allerdings absolut nicht.

Answer 1

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)$$

Comments

Ich dank dir vielmals!!! Ich wollte gerade eben schlafen gesehen, weil ich bei der aufgabe net weiterkam