Fakultät und Binomialkoeffizient

Question

Aufgabe:

Beweisen Sie: Für jede natürliche Zahl n >=1 gilt

$$\binom{n}{k}\frac{1}{n^k} \leq \frac{1}{k!}$$

Problem/Ansatz:

Geht das nicht auch wieder mit Induktion? Oder gibt es eine andere Möglichkeit?

Comments

Geht das nicht auch wieder mit Induktion?

Versuch's mal.

Oder gibt es eine andere Möglichkeit?

Höchstwahrscheinlich.

Answer 1

Wenn du den Binomialkoeffizienten ausschreibst, steht dort

n!/(k!·(n - k)!·n^k) ≤ 1/k!

was sich umformen lässt zu

n!/(n - k)! ≤ n^k

Jetzt kann man die Gültigkeit der Gleichung doch schon unmittelbar sehen.

Es ist durchaus erlaubt und erwünscht ruhig mal mehrere Ansätze zu probieren bevor man um Hilfe bittet. Also probier auch ruhig mal die vollständige Induktion.

Answer 2

Aloha :)

$$\phantom=\binom{n}{k}\cdot\frac{1}{n^k}=\frac{n!}{k!\cdot(n-k)!}\cdot\frac{1}{n^k}$$$$=\frac{\overbrace{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)\cdot\red{(n-k)!}}^{=n!}}{k!\cdot\red{(n-k)!}}\cdot\frac{1}{n^k}$$$$=\frac{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}{k!}\cdot\frac{1}{n^k}$$$$=\frac{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}{n^k}\cdot\frac{1}{k!}$$$$=\underbrace{\underbrace{\frac{n}{n}}_{=1}\cdot\underbrace{\frac{n-1}{n}}_{<1}\cdot\underbrace{\frac{n-2}{n}}_{<1}\cdots\underbrace{\frac{n-k+1}{n}}_{<1}}_{\le1}\cdot\frac{1}{k!}\le\frac{1}{k!}$$