Odhady faktoriálu a kombinačních čísel

Odhad faktoriálu

$e{\left(\frac{n}{e}\right)}^n\le n!\le en{\left(\frac{n}{e}\right)}^n$ Pro důkaz odhadu užijeme indukce a odhad rozdělíme na dva případy:

1. $n!\le en{\left(\frac{n}{e}\right)}^n$
   • $n=1$:

$$1!\le e\cdot 1\cdot {\left(\frac{1}{e}\right)}^1=1$$

Z indukčního předpokladu platí odhad pro $n-1$ a musíme dokázat platnost odhadu u $n$:

$$\begin{array}{rl}n!=n(n-1)!& {\le }^{\text{IP}}en(n-1){\left(\frac{n-1}{e}\right)}^{n-1}\\ & =en{\left(\frac{n}{e}\right)}^n{\left(\frac{e}{n}\right)}^n(n-1){\left(\frac{n-1}{e}\right)}^{n-1}\\ & =en{\left(\frac{n}{e}\right)}^n{\left(\frac{n-1}{n}\right)}^{n}e\end{array}$$

výraz ${\left(\frac{n-1}{n}\right)}^{n}e$ je menší než jedna:

$${\left(\frac{n-1}{n}\right)}^{n}e={\left(1-\frac{1}{n}\right)}^{n}e\le {\left(e^{-1/n}\right)}^{n}e=e^{-1}e=1$$

a tedy máme $n!\le en{\left(\frac{n}{e}\right)}^n{\left(\frac{n-1}{n}\right)}^{n}e\le en{\left(\frac{n}{e}\right)}^n$. 2. $e{\left(\frac{n}{e}\right)}^n\le n!$ - n = 1: $e\cdot {\left(\frac{1}{e}\right)}^1=1\le 1!$ - $n-1\to n$:

$$\begin{array}{rl}en{\left(\frac{n-1}{e}\right)}^{n-1}& \le n(n-1)!\\ en{\left(\frac{n}{e}\right)}^n{\left(\frac{e}{n}\right)}^n{\left(\frac{n-1}{e}\right)}^{n-1}& =\\ e{\left(\frac{n}{e}\right)}^n{\left(\frac{n-1}{n}\right)}^{n-1}e& =\end{array}$$

kde ${\left(\frac{n-1}{n}\right)}^{n-1}e\ge 1$: Nechť $m=n-1$. Potřebujeme:

$$(\frac{n-1}{n}{)}^{n-1}e\ge 1⟺(1+\frac{1}{m}{)}^m\le e.$$

Binomická věta:

$$(1+\frac{1}{m}{)}^m=\sum _{k=0}^m(\genfrac{}{}{0ex}{}{m}{k})\frac{1}{m^k}\le \sum _{k=0}^m\frac{1}{k!}\le \sum _{k=0}^{\infty }\frac{1}{k!}=e.$$ $$⟹(\frac{m}{m+1}{)}^{m}e\ge 1,$$

tedy pro $m=n-1$

$$(\frac{n-1}{n}{)}^{n-1}e\ge 1.$$

Odhad binomických koeficientů

Důkaz odhadů

$$(\frac{n}{k}{)}^k\le (\genfrac{}{}{0ex}{}{n}{k})\le (\frac{en}{k}{)}^k.$$

1. Výchozí vzorec

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n(n-1)\cdots (n-k+1)}{k!}=\prod _{j=1}^k\frac{n-j+1}{j}.$$

2. Dolní odhad
   Pro $j=1,2,\dots ,k$ platí

$$\frac{n-j+1}{j}\ge \frac{n}{k},$$

neboť funkce $j\mapsto \frac{n-j+1}{j}$ je rostoucí na $[1,k]$ a její nejmenší hodnota je
$\frac{n}{k}$ pro $j=1$.
Tudíž

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\prod _{j=1}^k\frac{n-j+1}{j}\ge (\frac{n}{k}{)}^k.$$

3. Horní odhad
   Zřejmé je i

$$\frac{n-j+1}{j}\le \frac{n}{j},$$

proto

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le \prod _{j=1}^k\frac{n}{j}=\frac{n^k}{k!}\le \frac{n^k}{(k/e{)}^k}=(\frac{en}{k}{)}^k,$$

kde jsme použili odhad $k!\ge (k/e{)}^k$:

• Logaritmický přechod

$$\ln (k!)=\sum _{i=1}^k\ln i\ge {\int }_1^k\ln xdx=[x\ln x-x{]}_1^k=k\ln k-k+1.$$

• Jednodušší odhad Protože pro $k\ge 1$ platí

$$k\ln k-k+1\ge k\ln k-k,$$

dostaneme

$$\ln (k!)\ge k(\ln k-1)=k\ln (\frac{k}{e}).$$ $$k!=\exp (\ln (k!))\ge \exp (k\ln (k/e))=(\frac{k}{e}{)}^k.$$

Odhad $\left(\genfrac{}{}{0ex}{}{2m}{m}\right)$

Pro odhad

$$2^{2m}/(2\sqrt{m})\le \left(\genfrac{}{}{0ex}{}{2m}{m}\right)\le 2^{2m}/\sqrt{2m}$$

si můžeme všimnout

$$\begin{array}{rl}P& =\frac{1\cdot 3\cdot 5\cdot \dots \cdot (2m-1)}{2\cdot 4\cdot 6\cdot \dots \cdot (2m)}\\ & =\frac{1\cdot 3\cdot 5\cdot \dots \cdot (2m-1)}{2^{m}m!}\frac{2\cdot 4\cdot 6\cdot \dots \cdot (2m)}{2\cdot 4\cdot 6\cdot \dots \cdot (2m)}\\ & =\frac{(2m)!}{2^{2m}(m!{)}^2}=\frac{\left(\genfrac{}{}{0ex}{}{2m}{m}\right)}{2^{2m}}.\end{array}$$

Teď nám tedy stačí ukázat

$$\frac{1}{(2\sqrt{m})}\le P\le \frac{1}{\sqrt{2m}},$$

to rozdělíme na horní a dolní odhad.

1. Pro horní odhad se nám hodí další kouzlení:

$$\begin{array}{rl}1& >\left(1-\frac{1}{2^2}\right)\cdot \left(1-\frac{1}{4^2}\right)\cdot \dots \cdot \left(1-\frac{1}{(2m{)}^2}\right)\\ & =\frac{1\cdot 3}{2\cdot 2}\cdot \frac{3\cdot 5}{4\cdot 4}\cdot \dots \cdot \frac{(2m-1)(2m+1)}{2m\cdot 2m}=P^2\cdot (2m+1)\end{array}$$

ze kterého nám vlastně přirozeně vypadlo, že $P<\frac{1}{\sqrt{2m+1}}<\frac{1}{\sqrt{2m+1}}$ 2. Spodní odhad je opět trikem z nerovnosti:

$$\begin{array}{rl}1& >\left(1-\frac{1}{3^2}\right)\cdot \left(1-\frac{1}{5^2}\right)\cdot \dots \cdot \left(1-\frac{1}{(2m-1{)}^2}\right)\\ & =\frac{2\cdot 4}{3\cdot 3}\cdot \frac{4\cdot 6}{5\cdot 5}\cdot \dots \cdot \frac{(2m-2)(2m)}{(2m-1)\cdot (2m-1)}=\frac{1}{P^2\cdot 2\cdot 2m}\end{array}$$

z čehož plyne $P>\frac{1}{2\sqrt{m}}$.

Oba triky nejsou kouzla z ničeho nic, oba staví na konstruování čísel podobných $P$, kde je vždy jen malý rozdíl v chybějících/přebývajících číslech.