Kezdőlap


Cím:	Az n! becslése elemi eszközökkel
Szerző(k):	Pfeil Tamás
Füzet:	2002/május, 269 - 273. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az $n! = n (n - 1) (n - 2) \dots 3 \cdot 2$ kifejezéssel nagyon sok kombinatorikai feladatban (és számos más helyen) találkozhatunk, és nemegyszer szükség van arra, hogy a nagyságát az $n$ néhány egyszerűbb kifejezésének a segítségével meg tudjuk becsülni. Ezt a célt szolgálja az ún. Stirling-formula, amiről éppen a KöMaL előző havi számában lehetett olvasni.^{$^{*}$} Ennek a formulának a bizonyításához a valós analízis számos olyan módszerére van szükség, amely a középiskolás matematikán messze túlmutat. Sokszor megfelel azonban valamivel enyhébb becslés is; megmutatjuk, hogy például a minden $n$ -re fennálló

\begin{matrix} \frac{e}{\sqrt[]{2}} {(\frac{n}{e})}^{n} \sqrt[]{n} < n! < e \sqrt[]{2} {(\frac{n}{e})}^{n} \sqrt[]{n} \end{matrix}

(1)

egyenlőtlenség belátása a sorozatok határértékének fogalmán kívül semmi egyéb analízisbeli eszközt nem igényel.
Kezdjük mindjárt az (1)-ben előforduló

e

számnak, a természetes logaritmus alapszámának a bemutatásával. Ez a szám a

\begin{matrix} d_{n} = {(1 + \frac{1}{n})}^{n} és az f_{n} = {(1 + \frac{1}{n})}^{n + 1} \end{matrix}

sorozatok közös határártéke. A határértékek létezéséhez belátjuk, hogy

(d_{n})

szigorúan monoton növő,

(f_{n})

szigorúan monoton fogyó sorozat,

d_{n} < f_{n}

és

f_{n} - d_{n}

a nullához tart. Az első három tulajdonságból következik, hogy mindkét sorozatnak létezik határértéke, és miután a két sorozat különbsége 0-hoz tart, ez a két határérték megegyezik.
A

d_{n} < f_{n}

egyenlőtlenség nyilvánvaló. A

(d_{n})

sorozat monotonitása azt jelenti, hogy minden

n

pozitív egészre

\begin{matrix} {(1 + \frac{1}{n})}^{n} < {(1 + \frac{1}{n + 1})}^{n + 1}, azaz \sqrt[n + 1]{1 \cdot {(1 + \frac{1}{n})}^{n}} < \frac{n + 2}{n + 1} . \end{matrix}

Ez pedig valóban teljesül a számtani és mértani középre vonatkozó egyenlőtlenség miatt, hiszen az

1, (1 + \frac{1}{n}), (1 + \frac{1}{n}), ..., (1 + \frac{1}{n})

számok számtani közepe éppen

\frac{1 + n \cdot (1 + \frac{1}{n})}{n + 1} = \frac{n + 2}{n + 1}

. Hasonlóan igazolható az is, hogy az

(f_{n})

sorozat fogyó:

\begin{matrix} {(1 + \frac{1}{n - 1})}^{n} > {(1 + \frac{1}{n})}^{n + 1}, azaz \sqrt[n + 1]{1 \cdot {(\frac{n - 1}{n})}^{n}} < \frac{n}{n + 1}, \end{matrix}

mivel

1, \frac{n - 1}{n}, \frac{n - 1}{n}, ..., \frac{n - 1}{n}

számtani közepe

\frac{1 + n \cdot \frac{n - 1}{n}}{n + 1} = \frac{n}{n + 1}

. Ezzel beláttuk, hogy a monoton növő

(d_{n})

sorozat felülről korlátos, hiszen (minden

n

-re)

d_{n} < f_{n} < f_{1} = 4

; ezért létezik határértéke. A monoton fogyó

(f_{n})

sorozat pedig alulról korlátos:

f_{n} > d_{n} > d_{1} = 2

, így az

(f_{n})

sorozatnak is létezik határértéke. Mivel mindkét sorozat korlátos, és a hányadosuk:

\frac{f_{n}}{d_{n}} = (1 + \frac{1}{n})

az 1-hez tart, azért

f_{n} - d_{n}

a 0-hoz tart, és a két sorozat határértéke ugyanaz az

e

szám, amire nyilván

\begin{matrix} {(1 + \frac{1}{n})}^{n} < e < {(1 + \frac{1}{n})}^{n + 1} \end{matrix}

teljesül.
Vizsgálódásunkat egy újabb sorozattal folytatva azt mutatjuk meg, hogy

\begin{matrix} az a_{n} = {(1 + \frac{1}{n})}^{n} (1 + \frac{1}{2 n}) sorozat szigorúan monoton fogy. \end{matrix}

(2)

Írjuk a bizonyítandó

\begin{matrix} {(1 + \frac{1}{n - 1})}^{n - 1} (1 + \frac{1}{2 (n - 1)}) > {(1 + \frac{1}{n})}^{n} (1 + \frac{1}{2 n}) \end{matrix}

egyenlőtlenséget

\begin{matrix} {(1 + \frac{1}{n^{2} - 1})}^{n} = {(\frac{n^{2}}{n^{2} - 1})}^{n} > \frac{2 n + 1}{2 n - 1} = 1 + \frac{2}{2 n - 1} \end{matrix}

alakba. Az

{(1 + \frac{1}{n^{2} - 1})}^{n}

hatvány a binomiális tétel szerint

n + 1

darab pozitív tagnak az összege; ezt nyilván nem növeljük (

n \geq 2

), ha csupán az összeg első három tagját írjuk ki:

\begin{matrix} \begin{matrix} {(1 + \frac{1}{n^{2} - 1})}^{n} & \geq (\binom{n}{0}) + (\binom{n}{1}) \frac{1}{n^{2} - 1} + (\binom{n}{2}) \frac{1}{{(n^{2} - 1)}^{2}} = \\ = 1 + \frac{2 n^{2} + 3 n}{2 n^{3} + 2 n^{2} - 2 n - 2} > 1 + \frac{2}{2 n - 1} . \end{matrix} \end{matrix}

Az utóbbi egyenlőtlenséget átrendezve

\begin{matrix} 4 n^{3} + 4 n^{2} - 3 n > 4 n^{3} + 4 n^{2} - 4 n - 4, \end{matrix}

ami nyilván igaz.
Tudjuk, hogy a

(d_{n})

sorozat határértéke

e

, ezért az

a_{n} = d_{n} (1 + \frac{1}{2 n})

határértéke is

e

. Mivel ez a sorozat szigorúan monoton fogyó, azért a sorozat minden tagja nagyobb

e

-nél; így

\begin{matrix} {(1 + \frac{1}{n})}^{n} (1 + \frac{1}{2 n}) > e, azaz \frac{1}{e} {(1 + \frac{1}{n})}^{n} > \frac{2 n}{2 n + 1} . \end{matrix}

(3)

Tekintsük ezután a

b_{n} = {(1 + \frac{1}{n})}^{n} (1 + \frac{1}{2 n + 1})

sorozatot: belátjuk, hogy

\begin{matrix} (b_{n}) szigorúan monoton nő, így (3)-hoz hasonlóan \frac{1}{e} {(1 + \frac{1}{n})}^{n} < \frac{2 n + 1}{2 n + 2} . \end{matrix}

(4)

A bizonyítandó

\begin{matrix} {(1 + \frac{1}{n - 1})}^{n - 1} (1 + \frac{1}{2 (n - 1) + 1}) < {(1 + \frac{1}{n})}^{n} (1 + \frac{1}{2 n + 1}) \end{matrix}

egyenlőtlenséget írjuk át előbb

\begin{matrix} {(1 - \frac{1}{n^{2}})}^{n} = {(\frac{n^{2} - 1}{n^{2}})}^{n} > \frac{(2 n + 1) (n - 1)}{(2 n - 1) (n + 1)} \end{matrix}

alakba. A binomiális tétel szerint

\begin{matrix} \begin{matrix} {(1 - \frac{1}{n^{2}})}^{n} = \sum_{i = 0}^{n} {(- 1)}^{i} (\binom{n}{i}) \frac{1}{n^{2 i}} = \\ = {\begin{matrix} \sum_{k = 0}^{[\frac{n}{2}]} [(\binom{n}{2 k}) \frac{1}{n^{4 k}} - (\binom{n}{2 k + 1}) \frac{1}{n^{4 k + 2}}], & hanpáratlan, \\ \sum_{k = 0}^{[\frac{n}{2}] - 1} [(\binom{n}{2 k}) \frac{1}{n^{4 k}} - (\binom{n}{2 k + 1}) \frac{1}{n^{4 k + 2}}] + (\binom{n}{n}) \frac{1}{n^{2 n}}, & hanpáros. \end{matrix} \end{matrix} \end{matrix}

Itt

\begin{matrix} \begin{matrix} (\binom{n}{2 k}) \frac{1}{n^{4 k}} - (\binom{n}{2 k + 1}) \frac{1}{n^{4 k + 2}} = \\ = \frac{n!}{(2 k + 1)! (n - 2 k)!} \frac{1}{n^{4 k + 2}} (n (n - 1) + 2 k (n^{2} + 1)) \geq 0. \end{matrix} \end{matrix}

Ezért bármely

n

esetén

\begin{matrix} {(1 - \frac{1}{n^{2}})}^{n} \geq (1 - (\binom{n}{1}) \frac{1}{n^{2}}) + ((\binom{n}{2}) \frac{1}{n^{4}} - (\binom{n}{3}) \frac{1}{n^{6}}) . \end{matrix}

Így (4) állítását

n \geq 3

esetén igazolja az

\begin{matrix} (1 - (\binom{n}{1}) \frac{1}{n^{2}}) + ((\binom{n}{2}) \frac{1}{n^{4}} - (\binom{n}{3}) \frac{1}{n^{6}}) > \frac{(2 n + 1) (n - 1)}{(2 n - 1) (n + 1)} \end{matrix}

egyenlőtlenség, azaz

\begin{matrix} \begin{matrix} \frac{6 n^{6} - 6 n^{5} + 3 n^{3} (n - 1) - n (n - 1) (n - 2)}{6 n^{6}} & > \frac{(2 n + 1) (n - 1)}{(2 n - 1) (n + 1)}, \\ 12 n^{8} - 6 n^{7} - 6 n^{6} + n^{5} - n^{4} + 3 n^{3} - 5 n^{2} + 2 n & > 12 n^{8} - 6 n^{7} - 6 n^{6}, \\ n^{4} (n - 1) + n^{2} (3 n - 5) + 2 n & > 0, \end{matrix} \end{matrix}

ami valóban igaz;

b_{1} < b_{2}

pedig nyilvánvaló.
Szükségünk lesz még a következő egyenlőtlenség(ek)re:

\begin{matrix} \frac{(2 n - 1)!!}{(2 n)!!} < \frac{1}{\sqrt[]{2 n + 1}} < \frac{(2 n)!!}{(2 n + 1)!!} \end{matrix}

(5)

Itt

(2 n - 1)!! = (2 n - 1) (2 n - 3) \dots 5 \cdot 3

(ez a

2 n - 1

szemifaktoriális) és hasonlóan

(2 n)!! = 2 n (2 n - 2) \dots 4 \cdot 2

. Az (5) egyenlőtlenség mindössze azon múlik, hogy

\begin{matrix} \frac{(2 n - 1)!!}{(2 n)!!} = \prod_{k = 1}^{n} \frac{2 k - 1}{2 k} < \prod_{k = 1}^{n} \frac{2 k}{2 k + 1} = \frac{(2 n)!!}{(2 n + 1)!!} = \frac{1}{2 n + 1} \cdot {(\frac{(2 n - 1)!!}{(2 n)!!})}^{- 1}, \end{matrix}

amiből az (5) első fele átszorzással és négyzetgyökvonással adódik. A bizonyítandó egyenlőtlenség második fele ennek csupán átrendezett alakja.
Immár minden rendelkezésre áll (1) bizonyításához. Legyen

c_{n} = \frac{n^{n}}{e^{n} n!}

. Erre a sorozatra

\begin{matrix} \frac{c_{k + 1}}{c_{k}} = \frac{1}{e} {(1 + \frac{1}{k})}^{k}, \end{matrix}

így (3) és (4) alapján

\begin{matrix} \frac{2 k}{2 k + 1} < \frac{c_{k + 1}}{c_{k}} < \frac{2 k + 1}{2 k + 2} . \end{matrix}

1 \leq k \leq n - 1

esetén kapott egyenlőtlenségek szorzatát véve

\begin{matrix} \frac{(2 n - 2)!!}{(2 n - 1)!!} < \frac{c_{n}}{c_{1}} < \frac{2 (2 n - 1)!!}{(2 n)!!}, \end{matrix}

amiből (5) figyelembevételével

\begin{matrix} \frac{1}{\sqrt[]{2 n - 1}} < \frac{c_{n}}{c_{1}} < \frac{2}{\sqrt[]{2 n + 1}}, \end{matrix}

ezért (az alsó becslés értékét csökkentve, a felsőét pedig megnövelve)

\begin{matrix} \frac{1}{e} \cdot \frac{1}{\sqrt[]{2 n}} < c_{n} < \frac{1}{e} \cdot \sqrt[]{\frac{2}{n}}, \end{matrix}

ez pedig éppen (1)-et adja.

^{$^{*}$}Lóczi Lajos: A faktoriális alsó és felső becslései, KöMaL 2002/4. szám, 195. old.