Matematyka dyskretna 1/Ćwiczenia 9: Asymptotyka: Różnice pomiędzy wersjami

Aktualna wersja na dzień 21:48, 11 wrz 2023

Asymptotyka

Ćwiczenie 1

Posortuj podane niżej funkcje według asymptotycznego stopnia złożoności tak, by każda funkcja była asymptotycznie niemniejsza od następujących po niej.

51 n + 101, \frac{n^{3}}{7 \lg^{7} n}, \frac{n^{2} + 2}{\lg n}, (\sqrt{n} + 1)^{3}, \frac{\lg n}{n}, \frac{n}{\lg n}, \sum_{k = 0}^{n} k \sqrt{k}

Wskazówka

Porządek ten to:

\frac{\lg n}{n}, \frac{n}{\lg n}, 51 n + 101, (\sqrt{n} + 1)^{3}, \frac{n^{2} + 2}{\lg n}, \sum_{k = 0}^{n} k \sqrt{k}, \frac{n^{3}}{7 \lg^{7} n}

Ćwiczenie 2

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T (n) = 4 T (\frac{n}{2}) + n$

Wskazówka

Rozwiązanie

$a = 4$ , $b = 2$ , $f (n) = n$ ,
$n^{\log_{2} 4} = n^{2}$ , $f (n) \in O (n^{2 - ε})$ , np. dla $ε = 0.5$ ,
zatem, z pierwszego punktu Twierdzenia o rekursji uniwersalnej, mamy $T (n) = Θ (n^{2})$ .

Ćwiczenie 3

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T (n) = 4 T (\frac{n}{2}) + n^{2}$

Wskazówka

Rozwiązanie

$a = 4$ , $b = 2$ , $f (n) = n^{2}$ ,
$n^{\log_{2} 4} = n^{2}$ , $f (n) \in Θ (n^{2})$ ,
zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy $T (n) = Θ (n^{2} \lg n)$ .

Ćwiczenie 4

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T (n) = 4 T (\frac{n}{2}) + n^{2} \lg_{2} n$

Wskazówka

Rozwiązanie

$a = 4$ , $b = 2$ , $f (n) = n^{2} \lg n$ ,
$n^{\log_{2} 4} = n^{2}$ , $f (n) \in Ω (n^{2})$ , ale ...
$f (n) \in̸ Ω (n^{2 + ε})$ dla dowolnego $ε > 0$ ,
nie możemy w tym przypadku zastosować Twierdzenia o rekursji uniwersalnej.

Ćwiczenie 5

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T (n) = 4 T (\frac{n}{2}) + n^{3}$

Wskazówka

Rozwiązanie

$a = 4$ , $b = 2$ , $f (n) = n^{3}$ ,
$n^{\log_{2} 4} = n^{2}$ , $f (n) \in Ω (n^{3 + ε})$ , np. dla $ε = 0.5$ ,
zatem, z trzeciego punktu Twierdzenia o rekursji uniwersalnej, mamy $T (n) = Θ (n^{3})$ .

Ćwiczenie 6

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T (n) = T (\frac{n}{2}) + c$

Wskazówka

Rozwiązanie

$a = 1$ , $b = 2$ , $f (n) = c$ ,
$n^{\log_{2} 1} = 1$ , $f (n) = Θ (1)$ ,
zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy $T (n) = Θ (\lg n)$ .

Ćwiczenie 7

Dla

\begin{aligned} T (n) & = 7 T (\frac{n}{2}) + n^{2}, \\ T^{'} (n) & = a T^{'} (\frac{n}{4}) + n^{2} \end{aligned}

wskaż największą całkowitą wartość parametru $a$ taką, że $T^{'} (n) \in O (T (n))$ .

Wskazówka

Oszacuj asymptotyczny rząd wielkości funkcji $T (n)$ oraz $T^{'} (n)$ .

Rozwiązanie

Z Twierdzenia o rekursji uniwersalnej mamy:

T (n) = Θ (n^{\log_{2} 7})

Ponadto

\log_{2} 7 \approx 2.807

Przeanalizujmy teraz rząd wielkości funkcji $T^{'} (n)$ w zależności od parametru $a$ :

jeśli $a < 16$ , to $T^{'} (n)$ podpada pod trzeci punkt Twierdzenia o rekursji uniwersalnej i $T^{'} (n) = Θ (n^{2}) = O (n^{\log_{2} 7})$ ,
jeśli $a = 16$ , to $T^{'} (n)$ podpada pod drugi punkt Twierdzenia o rekursji uniwersalnej i $T^{'} (n) = Θ (n^{2} \lg n) = O (n^{\log_{2} 7})$ ,
jeśli zaś $a > 16$ , to z trzeciego punktu Twierdzenia o rekursji uniwersalnej mamy $T^{'} (n) = Θ (n^{\log_{4} a})$ . Zatem wartości $a$ , przy których $T^{'} (n) = O (T (n))$ muszą spełniać nierówność

\log_{2} 7 ⩾ \log_{4} a = \log_{2} \sqrt{a}

czyli $7 ⩾ \sqrt{a}$ , tzn. $a ⩽ 49$ .

Największą całkowitą wartością parametru $a$ taką, że $T^{'} (n) = O (T (n))$ jest więc $49$ .

Ćwiczenie 8

Udowodnij przez indukcję, że dla $n ⩾ 1$ zachodzi:

{(\frac{n}{e})}^{n} < n! ⩽ {(\frac{n}{e})}^{n} \sqrt{n} e

Wskazówka

Pomocne może być następujące oszacowanie liczby $e$ :

{(\frac{n + 1}{n})}^{n} < e < {(\frac{n + 1}{n})}^{n + \frac{1}{2}}

,

jeśli tylko $n > 0$ .

Rozwiązanie

Pokażemy jedynie indukcyjny dowód nierówności ${(\frac{n}{e})}^{n} < n!$ . Dla $n = 1$ mamy $\frac{1}{e} < 1$ . Wychodząc od lewej nierówności podanej we wskazówce, mamy kolejno:

\begin{aligned} {(\frac{n + 1}{n})}^{n} & < e, \\ {(\frac{n + 1}{n})}^{n} \frac{n + 1}{e} & < n + 1, \\ {(\frac{n + 1}{e})}^{n + 1} {(\frac{e}{n})}^{n} & < n + 1 . \end{aligned}

Mnożąc ostatnią nierówność przez nierówność ${(\frac{n}{e})}^{n} < n!$ , pochodzącą z założenia indukcyjnego, dostajemy ${(\frac{n + 1}{e})}^{n + 1} < (n + 1)!$ .

Matematyka dyskretna 1/Ćwiczenia 9: Asymptotyka: Różnice pomiędzy wersjami

Aktualna wersja na dzień 21:48, 11 wrz 2023

Asymptotyka

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
 ==Asymptotyka==
-{{cwiczenie|ex asymptotyka sort||
+{{cwiczenie|1|cw 1|
 Posortuj podane niżej funkcje
 według asymptotycznego stopnia złożoności tak,
 by każda funkcja była asymptotycznie niemniejsza od następujących po niej.
-<center><math>\displaystyle 51n+101, \quad
+<center><math>51n+101, \quad
 \frac{n^3}{7\lg^7{n}}, \quad
 \frac{n^2+2}{\lg{n}}, \quad
@@ Linia 13: / Linia 13: @@
 \frac{\lg{n}}{n}, \quad
 \frac{n}{\lg{n}}, \quad
-\sum_{k=0}^n k\sqrt{k}.
+\sum_{k=0}^n k\sqrt{k}</math></center>
-</math></center>
 }}
@@ Linia 21: / Linia 21: @@
 Porządek ten to:
-<center><math>\displaystyle \frac{\lg{n}}{n}, \quad
+<center><math>\frac{\lg{n}}{n}, \quad
 \frac{n}{\lg{n}}, \quad
 n+101, \quad
@@ Linia 27: / Linia 28: @@
 \frac{n^2+2}{\lg{n}}, \quad
 \sum_{k=0}^n k\sqrt{k}, \quad
-\frac{n^3}{7\lg^7{n}}.
+\frac{n^3}{7\lg^7{n}}</math></center>
-</math></center>
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 1||
+{{cwiczenie|2|cw 2|
+Oszacuj rząd wielkości funkcji <math>T</math> zadanej równaniem rekurencyjnym:
-Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
+<math>T(n)=4T\left( \frac{n}{2} \right)+n</math>
-<math>\displaystyle T(n)=4T\left( \frac{n}{2} \right)+n</math>
 }}
@@ Linia 44: / Linia 44: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-* <math>\displaystyle a=4</math>, <math>\displaystyle b=2</math>, <math>\displaystyle f(n)=n</math>,
+* <math>a=4</math>, <math>b=2</math>, <math>f(n)=n</math>,
-* <math>\displaystyle n^{\log_2{4}}=n^2</math>, <math>\displaystyle f(n)\in O(n^{2-\varepsilon})</math>, np. dla <math>\displaystyle \varepsilon=0.5</math>,
+* <math>n^{\log_2{4}}=n^2</math>, <math>f(n)\in O(n^{2-\varepsilon})</math>, np. dla <math>\varepsilon=0.5</math>,
-* zatem, z pierwszego punktu Twierdzenia o rekursji uniwersalnej,
+* zatem, z pierwszego punktu Twierdzenia o rekursji uniwersalnej, mamy <math>T(n)=\Theta(n^2)</math>.
-mamy <math>\displaystyle T(n)=\Theta(n^2)</math>.
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 2||
+{{cwiczenie|3|cw 3|
+Oszacuj rząd wielkości funkcji <math>T</math> zadanej równaniem rekurencyjnym:
-Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
+<math>T(n)=4T\left( \frac{n}{2} \right)+n^2</math>
-<math>\displaystyle T(n)=4T\left( \frac{n}{2} \right)+n^2</math>
 }}
@@ Linia 63: / Linia 61: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-* <math>\displaystyle a=4</math>, <math>\displaystyle b=2</math>, <math>\displaystyle f(n)=n^2</math>,
+* <math>a=4</math>, <math>b=2</math>, <math>f(n)=n^2</math>,
-* <math>\displaystyle n^{\log_2{4}}=n^2</math>, <math>\displaystyle f(n)\in\Theta(n^2)</math>,
+* <math>n^{\log_2{4}}=n^2</math>, <math>f(n)\in\Theta(n^2)</math>,
-* zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy
+* zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy <math>T(n)=\Theta(n^2\lg{n})</math>.
-<math>\displaystyle T(n)=\Theta(n^2\lg{n})</math>.
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 3||
+{{cwiczenie|4|cw 4|
+Oszacuj rząd wielkości funkcji <math>T</math> zadanej równaniem rekurencyjnym:
-Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
+<math>T(n)=4T\left( \frac{n}{2} \right)+n^2\lg_2{n}</math>
-<math>\displaystyle T(n)=4T\left( \frac{n}{2} \right)+n^2\lg_2{n}</math>
 }}
@@ Linia 82: / Linia 78: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-* <math>\displaystyle a=4</math>, <math>\displaystyle b=2</math>, <math>\displaystyle f(n)=n^2\lg{n}</math>,
+* <math>a=4</math>, <math>b=2</math>, <math>f(n)=n^2\lg{n}</math>,
-* <math>\displaystyle n^{\log_2{4}}=n^2</math>, <math>\displaystyle f(n)\in\Omega(n^2)</math>, ale ...
+* <math>n^{\log_2{4}}=n^2</math>, <math>f(n)\in\Omega(n^2)</math>, ale ...
-* <math>\displaystyle f(n)\not\in\Omega(n^{2+\varepsilon})</math> dla dowolnego <math>\displaystyle \varepsilon>0</math>,
+* <math>f(n)\not\in\Omega(n^{2+\varepsilon})</math> dla dowolnego <math>\varepsilon>0</math>,
 * nie możemy w tym przypadku zastosować Twierdzenia o rekursji uniwersalnej.
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 4||
+{{cwiczenie|5|cw 5|
+Oszacuj rząd wielkości funkcji <math>T</math> zadanej równaniem rekurencyjnym:
-Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
+<math>T(n)=4T\left( \frac{n}{2} \right)+n^3</math>
-<math>\displaystyle T(n)=4T\left( \frac{n}{2} \right)+n^3</math>
 }}
@@ Linia 101: / Linia 96: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-* <math>\displaystyle a=4</math>, <math>\displaystyle b=2</math>, <math>\displaystyle f(n)=n^3</math>,
+* <math>a=4</math>, <math>b=2</math>, <math>f(n)=n^3</math>,
-* <math>\displaystyle n^{\log_2{4}}=n^2</math>, <math>\displaystyle f(n)\in\Omega(n^{3+\varepsilon})</math>, np. dla <math>\displaystyle \varepsilon=0.5</math>,
+* <math>n^{\log_2{4}}=n^2</math>, <math>f(n)\in\Omega(n^{3+\varepsilon})</math>, np. dla <math>\varepsilon=0.5</math>,
-* zatem, z trzeciego punktu Twierdzenia o rekursji uniwersalnej,
+* zatem, z trzeciego punktu Twierdzenia o rekursji uniwersalnej, mamy <math>T(n)=\Theta(n^3)</math>.
-mamy <math>\displaystyle T(n)=\Theta(n^3)</math>.
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 5||
+{{cwiczenie|6|cw 6|
+Oszacuj rząd wielkości funkcji <math>T</math> zadanej równaniem rekurencyjnym:
-Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
+<math>T(n)=T\left( \frac{n}{2} \right)+c</math>
-<math>\displaystyle T(n)=T\left( \frac{n}{2} \right)+c</math>
 }}
@@ Linia 120: / Linia 113: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-* <math>\displaystyle a=1</math>, <math>\displaystyle b=2</math>, <math>\displaystyle f(n)=c</math>,
+* <math>a=1</math>, <math>b=2</math>, <math>f(n)=c</math>,
-* <math>\displaystyle n^{\log_2{1}}=1</math>, <math>\displaystyle f(n)=\Theta(1)</math>,
+* <math>n^{\log_2{1}}=1</math>, <math>f(n)=\Theta(1)</math>,
-* zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy
+* zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy <math>T(n)=\Theta(\lg{n})</math>.
-<math>\displaystyle T(n)=\Theta(\lg{n})</math>.
 </div></div>
-{{cwiczenie|ex asymptotyka dwie funkcje z parametrem a||
+{{cwiczenie|7|cw 7|
+Dla
-Dla
-<center><math>\displaystyle \aligned T(n)&=7T\left( \frac{n}{2} \right)+n^2,\\
+<center><math>\begin{align} T(n)&=7T\left( \frac{n}{2} \right)+n^2,\\
 T'(n)&=aT'\left( \frac{n}{4} \right)+n^2
-\endaligned</math></center>
+\end{align}</math></center>
-wskaż największą całkowitą wartość parametru <math>\displaystyle a</math> taką, że <math>\displaystyle T'(n)\in O(T(n))</math>.
+wskaż największą całkowitą wartość parametru <math>a</math> taką, że <math>T'(n)\in O(T(n))</math>.
 }}
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Oszacuj asymptotyczny rząd wielkości funkcji <math>\displaystyle T(n)</math> oraz <math>\displaystyle T'(n)</math>.
+Oszacuj asymptotyczny rząd wielkości funkcji <math>T(n)</math> oraz <math>T'(n)</math>.
 </div></div>
@@ Linia 146: / Linia 139: @@
 Z Twierdzenia o rekursji uniwersalnej mamy:
-<center><math>\displaystyle T(n)=\Theta(n^{\log_2{7}}).
+<center><math>T(n)=\Theta(n^{\log_2{7}})
 </math></center>
 Ponadto
-<center><math>\displaystyle \log_2 7 \approx 2.807.
+<center><math>\log_2 7 \approx 2.807
 </math></center>
-Przeanalizujmy teraz rząd wielkości funkcji <math>\displaystyle T'(n)</math> w zależności od parametru <math>\displaystyle a</math>:
-* jeśli <math>\displaystyle a<16</math>,
-to <math>\displaystyle T'(n)</math> podpada pod trzeci punkt Twierdzenia o rekursji uniwersalnej
-i <math>\displaystyle T'(n)=\Theta(n^2)= O(n^{\log_2{7}})</math>,
-* jeśli <math>\displaystyle a=16</math>,
-to <math>\displaystyle T'(n)</math> podpada pod drugi punkt Twierdzenia o rekursji uniwersalnej
-i <math>\displaystyle T'(n)=\Theta(n^2\lg{n})= O(n^{\log_2{7}})</math>,
-* jeśli zaś <math>\displaystyle a>16</math>, to z trzeciego  punktu Twierdzenia o rekursji uniwersalnej mamy
-<math>\displaystyle T'(n)=\Theta(n^{\log_4{a}})</math>.
-Zatem wartości <math>\displaystyle a</math>, przy których <math>\displaystyle T'(n)=O(T(n))</math> muszą spełniać nierówność
-<center><math>\displaystyle \log_2{7}\geqslant\log_4{a}=\log_2{\sqrt{a}},
+Przeanalizujmy teraz rząd wielkości funkcji <math>T'(n)</math> w zależności od parametru <math>a</math>:
+* jeśli <math>a<16</math>, to <math>T'(n)</math> podpada pod trzeci punkt Twierdzenia o rekursji uniwersalnej i <math>T'(n)=\Theta(n^2)= O(n^{\log_2{7}})</math>,
+* jeśli <math>a=16</math>, to <math>T'(n)</math> podpada pod drugi punkt Twierdzenia o rekursji uniwersalnej i <math>T'(n)=\Theta(n^2\lg{n})= O(n^{\log_2{7}})</math>,
+* jeśli zaś <math>a>16</math>, to z trzeciego  punktu Twierdzenia o rekursji uniwersalnej mamy <math>T'(n)=\Theta(n^{\log_4{a}})</math>. Zatem wartości <math>a</math>, przy których <math>T'(n)=O(T(n))</math> muszą spełniać nierówność
+<center><math>\log_2{7}\geqslant\log_4{a}=\log_2{\sqrt{a}}
 </math></center>
-czyli <math>\displaystyle 7\geqslant\sqrt{a}</math>, tzn. <math>\displaystyle a\leqslant 49</math>.
-Największą całkowitą wartością parametru <math>\displaystyle a</math> taką, że <math>\displaystyle T'(n)=O(T(n))</math> jest więc <math>\displaystyle 49</math>.
+czyli <math>7\geqslant\sqrt{a}</math>, tzn. <math>a\leqslant 49</math>.
+Największą całkowitą wartością parametru <math>a</math> taką, że <math>T'(n)=O(T(n))</math> jest więc <math>49</math>.
 </div></div>
-{{cwiczenie|ex asymptotyka indukcja||
+{{cwiczenie|8|cw 8|
+Udowodnij przez indukcję, że dla <math>n\geqslant 1</math> zachodzi:
-Udowodnij przez indukcję, że dla <math>\displaystyle n\geqslant 1</math> zachodzi:
-<center><math>\displaystyle \left( \frac{n}{e} \right)^n<n!\leqslant \left( \frac{n}{e} \right)^n\sqrt{n}e.
+<center><math>\left( \frac{n}{e} \right)^n<n!\leqslant \left( \frac{n}{e} \right)^n\sqrt{n}e</math></center>
-</math></center>
 }}
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Pomocne może być następujące oszacowanie liczby <math>\displaystyle e</math>:
+Pomocne może być następujące oszacowanie liczby <math>e</math>:
+<center><math>\left( \frac{n+1}{n} \right)^n<e<\left( \frac{n+1}{n} \right)^{n+\frac{1}{2}}</math>,</center>
-<center><math>\displaystyle \left( \frac{n+1}{n} \right)^n<e<\left( \frac{n+1}{n} \right)^{n+\frac{1}{2}},
-</math></center>
-jeśli tylko <math>\displaystyle n>0</math>.
+jeśli tylko <math>n>0</math>.
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Pokażemy jedynie indukcyjny dowód  nierówności <math>\displaystyle \left( \frac{n}{e} \right)^n<n!</math>.
+Pokażemy jedynie indukcyjny dowód  nierówności <math>\left( \frac{n}{e} \right)^n<n!</math>.
-Dla <math>\displaystyle n=1</math> mamy <math>\displaystyle \frac{1}{e}<1</math>.
+Dla <math>n=1</math> mamy <math>\frac{1}{e}<1</math>.
 Wychodząc od lewej nierówności podanej we wskazówce, mamy kolejno:
-<center><math>\displaystyle \aligned \left( \frac{n+1}{n} \right)^n&<e,\\
+<center><math>\begin{align} \left( \frac{n+1}{n} \right)^n&<e,\\
 \left( \frac{n+1}{n} \right)^n\frac{n+1}{e}&<n+1,\\
 \left( \frac{n+1}{e} \right)^{n+1}\left( \frac{e}{n} \right)^n&<n+1.
-\endaligned</math></center>
+\end{align}</math></center>
-Mnożąc ostatnią nierówność przez nierówność <math>\displaystyle \left( \frac{n}{e} \right)^n<n!</math>,
+Mnożąc ostatnią nierówność przez nierówność <math>\left( \frac{n}{e} \right)^n<n!</math>,
 pochodzącą z założenia indukcyjnego, dostajemy
-<math>\displaystyle \left( \frac{n+1}{e} \right)^{n+1}<(n+1)!</math>.
+<math>\left( \frac{n+1}{e} \right)^{n+1}<(n+1)!</math>.
 </div></div>