Binomialkoeffizienten: Abschätzung

07.07.2015, 14:35	berserk	Auf diesen Beitrag antworten »
Binomialkoeffizienten: Abschätzung Hallo! Ich will folgende Abschätzung zeigen: $\begin{eqnarray} \binom{n-x}{k}\le \mathrm e^{-\frac{kx}{n}}\binom{n}{k} \end{eqnarray}$ Ich habe angefangen mit $\begin{eqnarray} \binom{n-x}{k}=\binom{n}{k}\frac{(n-x)!(n-k)!}{k!(n-k-x)!} \end{eqnarray}$ Es wäre also zu zeigen: $\begin{eqnarray} \frac{(n-x)!(n-k)!}{k!(n-k-x)!}\le\mathrm e^{-\frac{kx}{n}} \end{eqnarray}$ Hier habe ich es mit der Stirlingformel versucht, komme aber nicht auf das Ergebnis. Kann mir jemand weiterhelfen? Danke!
07.07.2015, 14:47	HAL 9000	Auf diesen Beitrag antworten »
Ich würde anders rangehen: Schaut man sich den Fall $\begin{align} k=1 \end{align}$ an, so führt der über äquivalente Umformungen zu $\begin{align} 1-\frac{x}{n} \leq e^{-\frac{x}{n}} \end{align}$ was aus $\begin{align} e^t\geq 1+t \end{align}$ für alle reellen $\begin{align} t \end{align}$ folgt. Verbunden mit einer zusätzlichen Abschätzung könnte man auch den Induktionsschritt eines Induktionsbeweises über $\begin{align} k \end{align}$ damit führen.
07.07.2015, 15:24	berserk	Auf diesen Beitrag antworten »
Ah, danke, auf die Idee bin ich gar nicht gekommen! Ich versuche mal den Induktionsschritt: $\begin{eqnarray} \binom{n-x}{k+1}=\binom{n-x}{k}\frac{n-x-k}{k+1} \end{eqnarray}$ Mit der Induktionsvoraussetzung ist das $\begin{eqnarray} \le \mathrm e^{-\frac{kx}{n}}\binom{n}{k}\cdot \frac{n-x-k}{k+1} \end{eqnarray}$ $\begin{eqnarray} = \mathrm e^{-\frac{(k+1)x}{n}}\cdot\mathrm e^{\frac{x}{n}}\binom{n}{k+1}\cdot \frac{k+1}{n-k}\cdot\frac{n-x-k}{k+1} \end{eqnarray}$ $\begin{eqnarray} \le \mathrm e^{-\frac{(k+1)x}{n}}\binom{n}{k+1}\cdot\mathrm e^{\frac{x}{n}} \end{eqnarray}$ Wenn das soweit stimmt, habe ich noch das $\begin{eqnarray} \mathrm e^{\frac{x}{n}} \end{eqnarray}$ stehen, das größer als 1 ist... Vielleicht gilt die Formel nur asymptotisch, wenn n sehr viel größer als x ist..?
07.07.2015, 15:31	HAL 9000	Auf diesen Beitrag antworten »
Bis zur vorletzten Zeile ist es Ok, aber dann schätzt du zu grob ab. Du musst lediglich noch $\begin{align} e^{\frac{x}{n}} \cdot \frac{n-x-k}{n-k} \leq 1 \end{align}$ nachweisen, äquivalent umgestellt $\begin{align} 1-\frac{x}{n-k} \leq e^{-\frac{x}{n}} \end{align}$ - dann wärest du fertig.
07.07.2015, 15:35	berserk	Auf diesen Beitrag antworten »
Super, dank dir hab ichs jetzt!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »