Лекция 7. Символы Ландау, эквивалентные последовательности, признак Даламбера, шкала роста

Продолжение лекции 6, которая закончилась критерием Коши. Сначала он ещё раз применяется к гармоническому ряду, а дальше лекция переходит от вопроса «сходится ли» к вопросу «как быстро растёт или убывает». Для этого вводятся символы Ландау $o$ и $O$, эквивалентные последовательности и признак Даламбера, а в конце строится шкала роста $\ln n\ll n^\alpha\ll a^n\ll n!\ll n^n$ — её постоянно используют при вычислении пределов.

1. Расходимость гармонического ряда

Частичные суммы гармонического ряда $S_n=\sum_{k=1}^n\frac1k=1+\frac12+\frac13+\dots+\frac1n.$

Напомним условие Коши и его отрицание в форме с шагом $p$: $\{x_n\}\ \text{фундаментальна}\iff\forall\varepsilon>0\ \exists N(\varepsilon)\in\mathbb N:\ \forall n>N\ \forall p\in\mathbb N\quad|x_{n+p}-x_n|<\varepsilon,$ $\{x_n\}\ \text{не фундаментальна}\iff\exists\varepsilon>0\ \forall N\in\mathbb N\ \exists n>N\ \exists p\in\mathbb N:\quad|x_{n+p}-x_n|\ge\varepsilon.$

Возьмём $\varepsilon_0=\dfrac12$, для данного $N$ положим $n=N+1$ и $p=n$. Тогда $|S_{2n}-S_n|=\sum_{k=n+1}^{2n}\frac1k=\frac1{n+1}+\frac1{n+2}+\dots+\frac1{2n}\ge\underbrace{\frac1{2n}+\frac1{2n}+\dots+\frac1{2n}}_{n}=\frac12.$ Каждое слагаемое не меньше последнего, $\frac1{2n}$, а их ровно $n$. Последовательность $S_n$ не фундаментальна и по критерию Коши расходится. Так как она возрастает, $S_n\to+\infty$.

2. Символы Ландау для последовательностей

2.1. o-малое

Определение 1. Последовательность $\{a_n\}$ называется o-малым от последовательности $\{b_n\}$ при $n\to\infty$ (пишут $a_n=o(b_n)$), если существует бесконечно малая $\{\alpha_n\}$, $\alpha_n\xrightarrow[n\to\infty]{}0$, такая, что $a_n=\alpha_n\cdot b_n.$

Смысл: $a_n$ пренебрежимо мала по сравнению с $b_n$. В частности, $a_n=o(1)$ означает просто $a_n\to0$.

Дополнение. Если $b_n\ne0$ (хотя бы начиная с некоторого номера), то определение равносильно условию $\dfrac{a_n}{b_n}\to0$: достаточно взять $\alpha_n=\dfrac{a_n}{b_n}$. Именно так $o$-малое обычно и проверяют.

2.2. O-большое

Определение 2. Последовательность $\{a_n\}$ называется O-большим от $\{b_n\}$ при $n\to\infty$ (пишут $a_n=O(b_n)$), если существует ограниченная последовательность $\{c_n\}$ такая, что $a_n=c_n\cdot b_n.$

Смысл: $a_n$ растёт не быстрее $b_n$ с точностью до постоянного множителя. При $b_n\ne0$ это значит, что отношение $\dfrac{a_n}{b_n}$ ограничено.

Дополнение. Из $a_n=o(b_n)$ следует $a_n=O(b_n)$: бесконечно малая $\alpha_n$ сходится, а сходящаяся последовательность ограничена. Обратное неверно, пример — ниже.

2.3. Примеры

1. $a_n=n$, $b_n=n^2$. Тогда $a_n=\dfrac1n\cdot b_n$, и $\dfrac1n\to0$, поэтому $n=o(n^2)$.
2. $a_n=\dfrac1{n^2}$, $b_n=\dfrac1n$. Тогда $a_n=\dfrac1n\cdot b_n$, поэтому $\dfrac1{n^2}=o\left(\dfrac1n\right)$. Для бесконечно малых $o$ означает «быстрее стремится к нулю».
3. $a_n=2n+1$, $b_n=5n-2$. Тогда $a_n=\dfrac{2n+1}{5n-2}\cdot b_n$, и $2n+1=O(5n-2)$, потому что $c_n=\dfrac{2n+1}{5n-2}$ ограничена: у неё есть предел, $\lim_{n\to\infty}\frac{2n+1}{5n-2}=\lim_{n\to\infty}\frac{n\left(2+\frac1n\right)}{n\left(5-\frac2n\right)}=\frac25,$ а сходящаяся последовательность ограничена. При этом $2n+1\ne o(5n-2)$: отношение стремится к $\frac25$, а не к нулю.

3. Эквивалентные последовательности

Определение 3. Последовательность $\{a_n\}$ эквивалентна последовательности $\{b_n\}$ при $n\to\infty$ (пишут $a_n\sim b_n$), если существует $\{x_n\}$ с $\lim\limits_{n\to\infty}x_n=1$ такая, что $a_n=x_n\cdot b_n.$

При $b_n\ne0$ это значит $\dfrac{a_n}{b_n}\to1$. Например, $n^2+n\sim n^2$, потому что $\dfrac{n^2+n}{n^2}=1+\dfrac1n\to1$. А $2n+1$ и $5n-2$ из примера 3 не эквивалентны: отношение стремится к $\frac25$.

Теорема 1 (об эквивалентных последовательностях). $a_n\sim b_n\iff a_n=b_n+o(b_n).$

Доказательство. Цепочка равносильностей: $a_n\sim b_n\iff\exists x_n\to1:\ a_n=x_nb_n\iff a_n=b_n(1+\alpha_n),\ \alpha_n\to0\iff a_n=b_n+\underbrace{\alpha_nb_n}_{o(b_n)}.$ Средний переход — замена $x_n=1+\alpha_n$: последовательность стремится к $1$ тогда и только тогда, когда $\alpha_n=x_n-1$ бесконечно малая. Последний переход — определение 1. $\blacksquare$

Словами: эквивалентные последовательности отличаются на величину, пренебрежимо малую по сравнению с ними самими. Например, $n^2+n=n^2+o(n^2)$.

4. Бесконечно большие последовательности

Определение 4. Последовательность $\{a_n\}$ называется бесконечно большой ($\lim\limits_{n\to\infty}a_n=\infty$), если $\forall E>0\ \ \exists N(E):\ \ \forall n>N\quad|a_n|>E.$

Словами: начиная с некоторого номера, все члены по модулю больше любого наперёд заданного числа. Бесконечно большая последовательность не сходится — предел $\infty$ лишь удобное обозначение.

На лекции дано упражнение: записать определения для $+\infty$ и $-\infty$.

Дополнение: определения для плюс и минус бесконечности

$\lim_{n\to\infty}a_n=+\infty\iff\forall E>0\ \exists N(E):\ \forall n>N\quad a_n>E,$ $\lim_{n\to\infty}a_n=-\infty\iff\forall E>0\ \exists N(E):\ \forall n>N\quad a_n<-E.$

Пример: $a_n=(-1)^nn$ бесконечно большая ($|a_n|=n$), но не стремится ни к $+\infty$, ни к $-\infty$ — члены всё время меняют знак.

Дополнение. Связь с бесконечно малыми: если $a_n\ne0$, то $a_n$ бесконечно большая тогда и только тогда, когда $\dfrac1{a_n}$ бесконечно малая. Действительно, $|a_n|>E\iff\left|\dfrac1{a_n}\right|<\dfrac1E$, а $\varepsilon=\dfrac1E$ пробегает все положительные числа.

5. Алгебра символов Ландау

Теорема 2. При $n\to\infty$:

Каждое равенство читается слева направо: «любая последовательность вида слева принадлежит классу справа».

Дополнение: доказательства правил

Везде $\alpha_n,\beta_n\to0$, а $c_n,d_n$ ограничены: $|c_n|\le C$, $|d_n|\le D$.

1. $a_n=\alpha_n\cdot(\beta_nb_n)=(\alpha_n\beta_n)b_n$, и $\alpha_n\beta_n\to0$.
2. $a_n=c_n\cdot(d_nb_n)=(c_nd_n)b_n$, и $|c_nd_n|\le CD$.
3. $\alpha_nb_n+\beta_nb_n=(\alpha_n+\beta_n)b_n$, и $\alpha_n+\beta_n\to0$.
4. $c_nb_n+d_nb_n=(c_n+d_n)b_n$, и $|c_n+d_n|\le C+D$.
5. Здесь $c_n$ — вторая база, а не ограниченный множитель: $O(b_n)\cdot o(c_n)=(d_nb_n)\cdot(\alpha_nc_n)=(d_n\alpha_n)\cdot b_nc_n$, а ограниченное на бесконечно малое — бесконечно малое: $|d_n\alpha_n|\le D|\alpha_n|\to0$.
6. $c_nb_n+\alpha_nb_n=(c_n+\alpha_n)b_n$; сходящаяся $\alpha_n$ ограничена, поэтому и $c_n+\alpha_n$ ограничена.

Отдельно полезны ещё два правила того же типа: $o(O(b_n))=o(b_n)$ и $O(o(b_n))=o(b_n)$ — оба следуют из «ограниченное на бесконечно малое — бесконечно малое».

6. Признак Даламбера для последовательностей

Теорема 3 (признак Даламбера). Пусть $\{x_n\}$ — последовательность, $x_n>0$, и существует $\lim_{n\to\infty}\frac{x_{n+1}}{x_n}=q.$ Тогда:

1. если $q<1$, то $\lim\limits_{n\to\infty}x_n=0$;
2. если $q=1$, признак ответа не даёт;
3. если $q>1$, то $\lim\limits_{n\to\infty}x_n=\infty$ (точнее, $+\infty$, так как $x_n>0$).

6.1. Доказательство для q меньше единицы

Доказательство. Так как $q<1$, найдётся число $r$ с $q<r<1$. Возьмём $\varepsilon=r-q>0$ в определении предела отношения: начиная с некоторого номера $N$, $\frac{x_{n+1}}{x_n}<q+\varepsilon=r,\quad\text{то есть}\quad x_{n+1}<r\,x_n\quad(n\ge N).$ Применяем это неравенство несколько раз подряд: $x_{N+1}<r\,x_N,\qquad x_{N+2}<r\,x_{N+1}<r^2x_N,\qquad\dots,\qquad x_{N+p}<r\,x_{N+p-1}<\dots<r^px_N.$ Пусть $n=N+p$, то есть $p=n-N$. Тогда $x_n<r^{n-N}x_N=r^n\cdot\underbrace{\frac{x_N}{r^N}}_{=:C}\qquad(n>N),$ где $C$ — число, не зависящее от $n$. Итак, $0<x_n<C\,r^n.$ Так как $0<r<1$, имеем $r^n\to0$ (упражнение с лекции, решение ниже), поэтому $Cr^n\to0$, и по теореме о двух милиционерах $x_n\to0$. $\blacksquare$

Дополнение: почему r в степени n стремится к нулю при модуле r меньше единицы

Упражнение с лекции: проверить по определению, что $\lim r^n=0$ при $|r|<1$.

При $r=0$ всё очевидно. Иначе запишем $\dfrac1{|r|}=1+h$, $h>0$. По неравенству Бернулли $(1+h)^n\ge1+nh>nh$, поэтому $|r^n-0|=\frac1{(1+h)^n}<\frac1{nh}.$ Для $\varepsilon>0$ возьмём $N=\left[\dfrac1{h\varepsilon}\right]$: при $n>N$ имеем $nh\varepsilon>1$, то есть $\dfrac1{nh}<\varepsilon$.

Дополнение: случаи q больше единицы и q равно единице

$q>1$. Возьмём $1<r<q$. Начиная с некоторого $N$, $\frac{x_{n+1}}{x_n}>r$, и так же, как выше, $x_n>C\,r^n$ с $C=\frac{x_N}{r^N}>0$. По Бернулли $r^n=(1+(r-1))^n\ge1+n(r-1)\to+\infty$, значит $x_n\to+\infty$.

$q=1$. Признак ничего не говорит, потому что при $q=1$ возможно всё:

• $x_n=\frac1n$: $\frac{x_{n+1}}{x_n}=\frac n{n+1}\to1$, а $x_n\to0$;
• $x_n=1$: отношение равно $1$, а $x_n\to1$;
• $x_n=n$: $\frac{n+1}n\to1$, а $x_n\to+\infty$.

7. Шкала роста бесконечно больших последовательностей

Теорема 4. Пусть $\alpha>0$, $a>1$. Тогда при $n\to\infty$ $\ln n\overset{(1)}{=}o(n^\alpha),\qquad n^\alpha\overset{(2)}{=}o(a^n),\qquad a^n\overset{(3)}{=}o(n!),\qquad n!\overset{(4)}{=}o(n^n).$

Цепочку удобно помнить так: логарифм $\ll$ степень $\ll$ показательная $\ll$ факториал $\ll$ $n^n$. Каждая следующая растёт настолько быстрее, что отношение предыдущей к ней стремится к нулю. Насколько велик разрыв уже при небольших $n$, видно на схеме.

Все четыре утверждения — пределы отношений $\lim\frac{a_n}{b_n}=0$ (знаменатели положительны).

7.1. Логарифм и степень

Надо доказать $\lim\limits_{n\to\infty}\dfrac{\ln n}{n^\alpha}=0$.

Упражнение с лекции: доказать, что $\ln n<n$ (по индукции).

Дополнение: доказательство неравенства логарифм n меньше n

Неравенство $\ln n<n$ равносильно $n<e^n$. База: $1<e$. Шаг: если $n<e^n$, то $e^{n+1}=e\cdot e^n>e\,n=n+(e-1)n\ge n+1{,}7>n+1$.

Доказательство. Положим $\beta=\dfrac\alpha2>0$. Применим неравенство $\ln x<x$ к числу $x=n^\beta$: $\ln(n^\beta)<n^\beta\ \Longrightarrow\ \beta\ln n<n^\beta\ \Longrightarrow\ \ln n<\frac1\beta\,n^\beta.$ Разделим на $n^\alpha=n^{2\beta}$: $0\le\frac{\ln n}{n^\alpha}<\frac1\beta\cdot\frac{n^\beta}{n^{2\beta}}=\frac2\alpha\cdot\frac1{n^\beta}.$ Правая часть стремится к нулю, поэтому $\lim\dfrac{\ln n}{n^\alpha}=0$ по теореме о двух милиционерах. $\blacksquare$

7.2. Степень и показательная функция

Надо доказать $\lim\limits_{n\to\infty}\dfrac{n^\alpha}{a^n}=0$ при $a>1$.

Доказательство. Положим $x_n=\dfrac{n^\alpha}{a^n}>0$ и применим признак Даламбера: $\frac{x_{n+1}}{x_n}=\frac{(n+1)^\alpha}{a^{n+1}}\cdot\frac{a^n}{n^\alpha}=\frac1a\left(1+\frac1n\right)^\alpha\xrightarrow[n\to\infty]{}\frac1a<1,$ так как $\frac1n\to0$ и $\left(1+\frac1n\right)^\alpha\to1$. По признаку Даламбера $x_n\to0$. $\blacksquare$

7.3. Показательная функция и факториал

Надо доказать $\lim\limits_{n\to\infty}\dfrac{a^n}{n!}=0$.

Доказательство. Для $x_n=\dfrac{a^n}{n!}$: $\frac{x_{n+1}}{x_n}=\frac{a^{n+1}}{(n+1)!}\cdot\frac{n!}{a^n}=\frac a{n+1}\xrightarrow[n\to\infty]{}0<1,$ и по признаку Даламбера $x_n\to0$. $\blacksquare$

Условие $a>1$ здесь не нужно: доказательство проходит для любого $a>0$.

7.4. Факториал и n в степени n

Надо доказать $\lim\limits_{n\to\infty}\dfrac{n!}{n^n}=0$.

Доказательство. Распишем дробь как произведение $n$ множителей: $\frac{n!}{n^n}=\frac{1\cdot2\cdot\ldots\cdot n}{n\cdot n\cdot\ldots\cdot n}=\frac1n\cdot\underbrace{\frac2n\cdot\frac3n\cdot\ldots\cdot\frac nn}_{\text{каждый}\ \le1}\le\frac1n.$ Итак, $0<\dfrac{n!}{n^n}\le\dfrac1n\to0$, и по теореме о двух милиционерах предел равен нулю. $\blacksquare$

Дополнение: то же через признак Даламбера

Для $x_n=\dfrac{n!}{n^n}$: $\frac{x_{n+1}}{x_n}=\frac{(n+1)!}{(n+1)^{n+1}}\cdot\frac{n^n}{n!}=\frac{n^n}{(n+1)^n}=\frac1{\left(1+\frac1n\right)^n}\xrightarrow[n\to\infty]{}\frac1e<1.$ Здесь пригодился второй замечательный предел из лекции 6.

Частые ошибки

1. Читать $a_n=o(b_n)$ как равенство. Это принадлежность классу; из $f=o(n)$ и $g=o(n)$ не следует $f=g$, а $o(b_n)-o(b_n)$ не равно нулю.
2. Путать $o$ и $O$. $2n+1=O(n)$, но не $o(n)$: отношение стремится к $2$, а не к нулю. Из $o$ следует $O$, обратное неверно.
3. Перемножать $o$ с одной базой. $O(b_n)\cdot o(b_n)=o(b_n^2)$, а не $o(b_n)$.
4. Делать вывод по Даламберу при $q=1$. Для $\frac1n$, $1$ и $n$ отношение стремится к $1$, а пределы разные.
5. Забывать, что в признаке Даламбера нужно $x_n>0$. Иначе отношение может быть не определено или менять знак.
6. Брать предел произведения растущего числа множителей. Теорема о пределе произведения — для фиксированного числа множителей; для $\frac{n!}{n^n}$ нужна оценка.
7. Считать, что бесконечно большая стремится к $+\infty$ или к $-\infty$. $(-1)^nn$ бесконечно большая, но ни к одной из бесконечностей не стремится.

Мини-тренажёр

1. Верно ли: а) $n^2=o(n^3)$; б) $3n^2+n=O(n^2)$; в) $3n^2+n=o(n^2)$; г) $\sin n=O(1)$?
2. Докажите, что $\sqrt{n^2+1}\sim n$, и запишите это в виде $\sqrt{n^2+1}=n+o(n)$.
3. С помощью признака Даламбера найдите $\lim\limits_{n\to\infty}\dfrac{n^3}{2^n}$ и $\lim\limits_{n\to\infty}\dfrac{3^n}{n!}$.
4. Почему признак Даламбера не решает вопрос о $\lim\limits_{n\to\infty}\dfrac{n^{10}}{n^{9}+1}$? Найдите этот предел другим способом.
5. Расположите по скорости роста: $n!$, $\ln n$, $2^n$, $n^n$, $\sqrt n$, $n^{100}$.
6. Найдите $\lim\limits_{n\to\infty}\dfrac{2^n+n^5}{3^n}$.
7. Найдите $\lim\limits_{n\to\infty}\dfrac{n!}{(n+1)^n}$.

Ответы

1. а) Да: $\frac{n^2}{n^3}=\frac1n\to0$. б) Да: $\frac{3n^2+n}{n^2}=3+\frac1n\to3$, ограничено. в) Нет: отношение стремится к $3$, а не к $0$. г) Да: $\sin n=\sin n\cdot1$, и $|\sin n|\le1$.
2. $\dfrac{\sqrt{n^2+1}}n=\sqrt{1+\frac1{n^2}}\to1$, значит $\sqrt{n^2+1}\sim n$, и по теореме 1 $\sqrt{n^2+1}=n+o(n)$. На самом деле разность ещё меньше: $\sqrt{n^2+1}-n=\dfrac1{\sqrt{n^2+1}+n}\to0$.
3. $\dfrac{x_{n+1}}{x_n}=\dfrac12\left(1+\frac1n\right)^3\to\dfrac12<1$, предел $0$. Для второго $\dfrac3{n+1}\to0$, предел $0$.
4. $\dfrac{x_{n+1}}{x_n}=\dfrac{(n+1)^{10}(n^9+1)}{n^{10}((n+1)^9+1)}\to1$ — случай $q=1$. Делим на $n^9$: $\dfrac{n}{1+\frac1{n^9}}\to+\infty$.
5. $\ln n\ll\sqrt n\ll n^{100}\ll2^n\ll n!\ll n^n$.
6. $\dfrac{2^n}{3^n}=\left(\dfrac23\right)^n\to0$ и $\dfrac{n^5}{3^n}\to0$ по шкале, предел $0$.
7. $\dfrac{n!}{(n+1)^n}<\dfrac{n!}{n^n}\to0$, предел $0$.

Шпаргалка