Zeigen Sie für diese Aufgabe den Beweis

Question

Aufgabe:

Zeigen Sie für:

Problem/Ansatz:

c ∈ ℕ und n→∞:  (n! / (n-c)!)  ∼n^c

Comments

Hallo

was soll das ∼n^c bedeuten? wennn->oo geht kommt doch kein n mehr vor?

lul

---

Dazu habe ich leider keine Antwort. Die Aufgabe wurde mir so gestellt.

---

Vermutlich soll das heißen, dass der Grenzwert \(\displaystyle\lim_{n\to\infty}\frac{n!}{n^c\cdot(n-c)!}\)  existiert und gleich 1 ist.
Vgl. https://de.wikipedia.org/wiki/Asymptotische_Analyse.

---

https://de.wikipedia.org/wiki/Asymptotische_Analyse

Die Tilde f ~ g heißt je nach Kontext "f und g sind asymptotisch gleich/äquivalent" und ist definiert durch

$$ f \sim g \Leftrightarrow \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 $$

Wenn man weiß, dass

$$ \frac{n!}{(n-c)!} = n \cdot (n-1) \cdot ... \cdot (n-c+1) $$

Dann kann sich schnell überlegen, dass

$$ \frac{\frac{n!}{(n-c)!}}{n^c} = 1 \cdot \left(1-\frac{1}{n}\right) \cdot ... \cdot \left(1-\frac{c-1}{n}\right) $$

Und dann ist eigentlich recht klar, dass für festes c jeder Faktor gegen 1 und somit auch das gesamte Produkt gegen 1 geht.

---

Aber eigentlich steht da doch wirklich nirgends , dass durch n^c geteilt wird?

lul

---

Mein Kommentar war überflüssig.

---

Für das "und somit" fehlt hier die Begründung

Dann lassen wir den Fragesteller einfach darüber nachdenken.

Answer 1

Aloha :)

Das ist aber eine sehr grobe Abschätzung. Ich würde das Ungefähr-Zeichen eher durch ein Kleiner-Zeichen ersetzen, denn es gilt doch:

$$\frac{n!}{(n-c)!}=\frac{1\cdot2\cdot3\cdots(n-c-1)\cdot(n-c)\cdot(n-c+1)\cdot(n-c+2)\cdots(n-1)\cdot n}{1\cdot2\cdot3\cdots(n-c-1)\cdot(n-c)}$$Jetzt kürzen sich im Zähler und Nenner die ersten \(n-c\) Faktoren raus:

$$\frac{n!}{(n-c)!}=\frac{\cancel{1\cdot2\cdot3\cdots(n-c-1)\cdot(n-c)}\cdot(n-c+1)\cdot(n-c+2)\cdots(n-1)\cdot n}{\cancel{1\cdot2\cdot3\cdots(n-c-1)\cdot(n-c)}}$$und zurück bleiben \(c\) Faktoren, die alle \(\le n\) sind:

$$\frac{n!}{(n-c)!}=(n-c+1)\cdot(n-c+2)\cdots(n-1)\cdot n\le \underbrace{n\cdot n\cdots n}_{=\text{\(c\) Faktoren}}=n^c$$