8Теорема Вейерштрасса, немного комбинаторики и число e

До сих пор у нас был единственный способ доказать, что некоторая последовательность имеет предел: угадать, чему этот предел равен, а затем использовать определение, чтобы доказать, что он действительно этому равен. В этой лекции мы познакомимся с утверждением, которое позволит доказать существование предела в ситуации, когда его значение неизвестно. Но начнём мы слегка издалека.

8.1Ограниченные множества

8.1.1Максимум и минимум

Определение 1. Пусть

X

— некоторое числовое множество,

X \subset R

. Пусть существует такое число

C

, что все элементы множества

X

не превосходят

C

\forall x \in X : x \leq C .

Тогда множество

X

называется ограниченным сверху.

Аналогично, с заменой неравенства $\leq$ на $\geq$ , определяется множество, ограниченное снизу.

Замечание 1. Для дальнейшего полезно ввести новые обозначения, позволяющие описывать множества, получаемые из других множеств по некоторым правилам. Проще всего объяснить их на примере.

${n^{2} ∣ n \in N}$ — множество всех квадратов всех натуральных чисел. Фигурные скобки подсказывают, что мы создаём новое множество, после вертикальной черты написано, какие значения пробегает переменная $n$ , а до черты — как из переменной $n$ изготовить элементы множества.
${n \in N ∣ \exists k \in N : k^{2} = n}$ — это тоже множество квадратов всех натуральных чисел, только записанное иначе. Здесь до вертикальной черты написано, из какого множества выбирается $n$ , а после — какому условию $n$ должно удовлетворять, чтобы быть включённым в наше новое множество.

Замечание 2. Пусть есть последовательность

{a_{n}}

. Рассмотрим множество всех её элементов:

{a_{n} ∣ n \in N}

. (В отличие от последовательности, это просто множество: в нём нет никакого порядка, и каждый элемент в него может входить только один раз. Например, для последовательности

{(- 1)^{n}}

получится конечное множество

{1, - 1}

; такое же множество получится для последовательности

{(- 1)^{n + 1}}

.) Это множество ограничено тогда и только тогда, когда последовательность ограничена. (Докажите!)

Определение 2. Рассмотрим произвольное числовое множество

X \subset R

. Его максимумом (соответственно, минимумом) называется такой элемент

X

, который не меньше (соответственно, не больше) всех элементов

X

\begin{matrix} max X = m \Leftrightarrow (m \in X) \land (\forall y \in X : m \geq y) . min X = M \Leftrightarrow (M \in X) \land (\forall y \in X : M \leq y) . \\ (8.1) (8.2) \end{matrix}

\begin{matrix} max X = m \Leftrightarrow \Leftrightarrow (m \in X) \land (\forall y \in X : m \geq y) . min X = M \Leftrightarrow \Leftrightarrow (M \in X) \land (\forall y \in X : M \leq y) . \\ (8.1) (8.2) \end{matrix}

Вопрос 1. Что будет, если заменить нестрогое неравенство на строгое?

Ничего не изменится, мы такое уже проходили.

Неверный ответ. В этот раз всё не так.

Определение потеряет свой смысл.

Верный ответ. Действительно, если потребовать строгое неравенство, условие будет всегда нарушаться: элемент не может быть строго больше или строго меньше самого себя.

Упражнение 1. Докажите, что если максимум (минимум) определён, он задан единственным образом.

Если множество конечное, у него всегда определён максимум и минимум, мы уже пользовались этим свойством. (Доказать это аккуратно с помощью индукции — полезное упражнение.) Если множество бесконечно, становится интереснее.

Если максимум множества $X$ существует, это множество обязательно ограничено сверху: действительно, сам этот максимум можно подставить в определение 1 в качестве $C$ . Аналогично, если существует минимум, множество ограничено снизу.

В обратную сторону, однако, это не работает: например, если множество ограничено сверху, ещё не факт, что у него есть максимум.

Пример 1. Пусть

X = [0, 1) = {x \in R ∣ 0 \leq x < 1}

— полуоткрытый интервал, включащий в себя

0

, но не включающий единицу. Это множество ограничено и сверху, и снизу. У него есть минимум — это число

0

, но нет максимума. Действительно, любое число

x \in [0, 1)

меньше 1 (см. рис. 8.1). Рассмотрим число

y = \frac{x + 1}{2}

— середину отрезка

[x, 1]

. Оно больше

x

, но меньше

1

(проверьте аккуратно с помощью неравенств). Значит,

x

не является максимумом.

Иллюстрация к доказательству утверждения о том, что у
полуинтервала $[0, 1)$ нет максимума, описание см. в тексте.

Рис. 8.1: У множества

[0, 1)

нет максимума.

Это неудачно: мы бы хотели как-то обобщить понятие максимума и минимума, чтобы они существовали для любого ограниченного с соответствующей стороны множества. Если ещё раз посмотреть на пример с полуоткрытым интервалом $[0, 1)$ , и задать вопрос, какое число подходит на роль его «обобщённого максимума», напрашивается ответ, что это число $1$ . Единственная причина, по которой $1$ не является максимумом на самом деле — то, что $1$ не принадлежит нашему множеству. Если бы мы могли снять это ограничение…

8.1.2Точная верхняя и нижняя грани

Что будет, если мы уберём в определении максимума требование, чтобы

M

принадлежал

X

. Для полуинтервала

[0, 1)

, число

1

будет удовлетворять новому определению. Однако, не только оно: любое число, большее 1, тоже ему будет удовлетворять. Мы лишились единственности. Однако, сделали важный шаг на пути к построению нужного нам понятия. Штука, которую мы определили, называется верхней гранью множества.

Определение 3. Верхней гранью множества

X

называется такое число

C

, которое не меньше всех элементов

X

\forall x \in X : x \leq C .

Аналогично (заменой неравенства

\leq

на

\geq

) определяетcя нижняя грань множества.

Множество всех верхних граней $X$ будем обозначать через $U B (X)$ (от англ. upper bound), а нижних — через $L B (X)$ (от lower bound).

Сравнивая определения 3 и 1, мы видим, что множество является ограниченным сверху (снизу) тогда и только тогда, когда у него есть верхняя (нижняя) грань, то есть $U B (X)$ непусто (соответственно, $L B (X)$ непусто). Собственно, верхняя грань (нижняя грань) — это ровно та самая константа $C$ , которая участвует в определении 1. Слово «грань» здесь следует понимать как «то, что ограничивает».

Вернёмся к задаче определения «обобщённого максимума» и примеру с полуинтервалом $[0, 1)$ . Множеством верхих граней этого интервала оказывается весь луч $[1, + \infty)$ , см. рис. 8.2. Какое число из этого луча в наибольшей степени достойно того, чтобы назваться «обобщённым максимумом» множества $[0, 1)$ ? Очевидно, самое маленькое: число $1$ .

Нарисован полуинтервал X=[0, 1). Его множеством нижних граней LB(X)
является луч (-∞, 0], а множеством верхних граней UB(X) является луч
[1, +∞).

Рис. 8.2: Множества верхних и нижних граней для

[0, 1)

Определение 4. Пусть

X \subset R

— некоторое числовое множество. Его точной верхней гранью называется самая маленькая верхняя грань, то есть минимум множества

U B (X)

. Аналогично, точной нижней гранью называется самая большая из нижних граней, то есть максимум множества

L B (X)

Точная верхняя грань также называется супремумом, а точная нижняя грань — инфимумом. В обозначениях:

sup X := min U B (X), inf X := max L B (X) .

Позвольте! — скажет тут читатель, — вы водите нас кругами! Обещали построить обобщение максимума и минимума, но вернулись в итоге к ним же самим: супремум определяется через минимум, а инфимум — через максимум. Казалось бы, мы должны столкнуться с теми же самыми трудностями, от которых стремились уйти: максимум и минимум могут быть не определены. Стоило ли тогда так мучаться?

Оказывается, да, стоило. Дело в том, что каким бы ни было множество $X$ , если множество его верхних граней $U B (X)$ не пусто, у него обязательно есть минимальный элемент $min U B (X)$ , и аналогично если непусто множество нижних граний, определён его максимум.

Давайте ещё раз вернёмся к полуинтервалу $[0, 1)$ . Его множество верхних граней — замкнутый луч $[1, + \infty)$ , содержащий единицу. Может показаться, что если мы теперь возмём вместо полуинтервала замкнутый отрезок $[0, 1]$ , множество верхних граней станет открытым лучом и лишится своего минимального элемента. Но нет! Из-за использования нестрого неравенства в определении 3, верхняя грань может принадлежать множеству $X$ (это не запрещено). Множеством всех верхних граней отрезка $[0, 1]$ по-прежнему является замкнутый луч $[1, + \infty)$ , и он по-прежнему содержит минимальный элемент — число $1$ . Здорово, правда?

Теорема 1. Если множество

X \subset R

ограничено сверху, у него есть точная верхняя грань. Если оно ограничено снизу — точная нижняя.

Эта теорема доказывается не очень сложно, хотя и немножко занудно. (Как-то я даже хотел рассказать доказательство на лекциях, но, прикинув масштабы бедствия, понял, что все быстро уснут, и отказался от этой идеи.) Например, доказательство можно найти в Википедии. Выглядит жутковато, но если сесть и аккуратно в нём разобраться, вы увидите, что оно не очень сложное. Тем не менее, мы не будем его подробнее обсуждать. Однако, стоит обсудить, почему эта теорема не так очевидна, как может показаться из рассмотрения примера с полуинтервалом.

Представьте себе, что мы переместились во времена Пифагора, когда про вещественные числа ещё ничего не знали. Рассмотрим множество

S := {x \in Q ∣ x^{2} < 2} .

Древние греки вполне могли такое множество рассмотреть: оно состоит из рациональных чисел, и в его определении никакие иррациональные числа не участвуют. Однако, если бы древний грек попытался найти точную верхнюю грань множества

S

, его бы постигла неудача. Действительно, он бы рассматривал только рациональные верхние грани (других чисел он не знает). Поскольку

\sqrt{2}

, как мы сейчас знаем, иррационален (см. теорему 2 из лекции 1), множество рациональных верхних граней для

S

не содержит минимального элемента: какое бы рациональное число, большее

\sqrt{2}

мы бы ни взяли, можно найти рациональное число поменьше, по-прежнему являющееся верхней гранью для

S

. (Это следует из плотности множества рациональных чисел, которую мы доказывали на семинарах.) Неудача!

Тот факт, что у любого ограниченного сверху подмножества множества вещественных чисел есть (вещественная) точная верхняя грань — пожалуй, главное, что отличает вещественные числа от рациональных.

8.2Теорема Вейерштрасса

Вернёмся к последовательностям.

Теорема 2. (Вейерштрасс) Пусть последовательность

{a_{n}}

ограничена сверху и неубывает. Тогда она имеет предел.

Нарисован график неубывающей последовательности, ограниченной
сверху числом C. Между C и максимальным изображенным элементом
последовательности есть заметный зазор.

Рис. 8.3: Иллюстрация к теореме 2. Неубывающая ограниченная последовательность. Здесь число

C

является какой-то из верхних граней (не обязательно точной) для множества всех членов последовательности.

Доказательство. Рассмотрим множество элементов последовательности

{a_{n} ∣ n \in N}

. Поскольку последовательность ограничена сверху, это множество тоже ограничено сверху. Возьмём его точную верхнюю грань (она существует по теореме 1) и обозначим её за

A

. Докажем, что

A

является пределом нашей последовательности.

Близкие элементы существуют. Сперва докажем более слабое утверждение: докажем, что элементы последовательности подходят к $A$ сколь угодно близко, см. рис. 8.4. Формально:

\begin{matrix} \forall ε > 0 \exists N \in N : | a_{N} - A | < ε . \\ (8.3) \end{matrix}

Это ещё не определение предела (мы ничего не говорим про бесконечный хвост последовательности, а говорим только про один элемент), но давайте начнём с этого.

Нарисован график неубывающей последовательности, ограниченной
сверху числом C и числом A < C. Между A и максимальным изображенным элементом
последовательности нет заметного зазора. Нарисована также прямая
y=A-ε и n=N. Все точки, начиная с n=N, лежат в коридоре между
y=A и y=A-ε.

Рис. 8.4: Иллюстрация к доказательству теоремы Вейерштрасса,

A = sup {a_{n} ∣ n \in N}

От противного, пусть это неверно. Запишем отрицание:

\exists ε > 0 \forall N \in N : | a_{N} - A | \geq ε

Заметим, что раз

A

— верхняя грань множества всех элементов последовательности, каждый из элементов не больше

A

и значит модуль раскрывается как

A - a_{N}

. Тогда нашлось такое

ε

, что все элементы последовательности удовлетворяют неравенству

A - a_{N} \geq ε,

или, иными словами,

a_{n} \leq A - ε

. Таким образом, все элементы

{a_{n}}

не превосходят

(A - ε)

, то есть

(A - ε)

— верхняя грань. (На рис. 8.4 в этом случае не было бы никаких точек последовательности выше

y = A - ε

.) Но

A - ε < A

, а мы предположили, что

A

точная верхняя грань, то есть минимум из всех верхних граней. Противоречие!

Иными словами, если элементы последовательности не подходят к $A$ сколь угодно близко, то между $A$ и этими элементами есть «зазор», и $A$ можно было бы уменьшить, сохранив его свойство быть верхней гранью. Это противоречит тому, что $A$ точная (самая маленькая) верхняя грань.

Монотонность. Заметим, что в силу монотонности, если $a_{N} > A - ε$ , то для всякого $n > N$ , $a_{n} \geq a_{N} > A - ε$ . Поскольку для всех элементов выполняется, что $a_{N} \leq A$ , отсюда следует, что для $| a_{n} - A | = A - a_{n} < ε$ .

Таким образом, утверждение доказано по определению предела: мы показали, что для всякого $ε$ найдётся такое $N$ (определяемое из формулы (8.3)), что для всех $n > N$ , $| a_{n} - A | < ε$ .∎

Замечание 3. Конечно, легко сформулировать и доказать теорему Вейерштрасса для ограниченных снизу невозрастающих последовательностей.

Замечание 4. В ходе доказательства получили, что предел неубывающей последовательности является точной верхней гранью всех её членов. Отсюда в частности следует, что все члены не превосходят предела: если

{a_{n}}

неубывает и имеет предел

A

, то для всех натуральных

k

a_{k} \leq A

. Конечно, мы могли бы получить этот результат и непосредственно: в силу неубывания, для всех

n > k

a_{k} \leq a_{n}

. Зафиксируем

k

и перейдём в этом неравенстве к пределу при

n \to \infty

. (Поскольку предел зависит только от «хвоста» последовательности, тот факт, что неравенство выполняется не для всех

n

, а только для тех, которые больше

k

, не является препятствием — можно просто выкинуть первые

k

элементов обеих последовательностей.) Получим

a_{k} \leq {lim}_{n \to \infty} a_{n} = A

8.3Биномиальные коэффициенты

8.3.1Упорядоченные наборы

Определение 5. Пусть есть множества

X

Y

. Декартовым произведением этих множеств называется множество упорядоченных пар

(x, y)

, где

x \in X

y \in Y

. Пишут:

X \times Y = {(x, y) ∣ x \in X, y \in Y} .

Пример 2. Рассмотрим множество

R^{2} = R \times R

— декартов квадрат множества вещественных чисел. Оно состоит из упорядоченных пар

(x, y)

, где

x

y

— вещественные числа. С этим объектом мы хорошо знакомы из школы: это обыкновенная декартова плоскость.

Вопрос 2. Пусть множества

X

Y

конечны: в

X

3 элемента, а в

Y

два. Сколько элементов в множестве

X \times Y

Верный ответ. Конечно: к каждому из трёх элементов $X$ можно приписать два элемента из $Y$ , значит всего шесть элементов.

Неверный ответ. Интересно, как это получилось?

Неверный ответ. Ой?

Неверный ответ. Откуда это могло взяться?

Можно рассматривать декартово произведение больше, чем двух множеств: оно состоит из упорядоченных наборов элементов, каждый из которых взят из соответствующего сомножителя. Например:

\begin{matrix} X \times Y \times Z = {(x, y, z) ∣ x \in X, y \in Y, z \in Z} . \end{matrix}

\begin{matrix} X \times Y \times Z = {(x, y, z) ∣ x \in X, y \in Y, z \in Z} . \end{matrix}

Можно было бы расставить скобки в выражении

X \times Y \times Z

и, например, получить множество

(X \times Y) \times Z

, элементами которого были бы упорядоченные пары

(w, z)

, где

z \in Z

w \in X \times Y

, то есть

w = (x, y)

— тоже упорядоченная пара. Но с практической точки зрения обычно нет никакой разницы между выражениями вида

((x, y), z)

(x, y, z)

Определение 6. Результат

k

-кратного декартова умножения множества

X

на себя называется $k$ -й декартовой степенью множества

X

и обозначается

X^{k}

. Оно состоит из упорядоченных

k

-элементных наборов элементов множества

X

\begin{matrix} X^{k} = {(x_{1}, x_{2}, \dots, x_{k}) ∣ x_{1} \in X, x_{2} \in X, \dots, x_{k} \in X} . \end{matrix}

\begin{matrix} X^{k} = {(x_{1}, x_{2}, \dots, x_{k}) ∣ x_{1} \in X, x_{2} \in X, \dots, x_{k} \in X} . \end{matrix}

Про упорядоченные наборы важно понимать следующее: элементы в них могут повторяться (никто не мешает вам рассмотреть точку $(1, 1) \in R^{2}$ ) и порядок следования элементов важен (точка $(1, 2)$ — это совсем не то же самое, что точка $(2, 1)$ ).

Утверждение 1. Пусть

X

— конечное множество, состоящее из

n

элементов. Тогда

X^{k}

состоит из

n^{k}

элементов. Иными словами, количество

k

-элементных упорядоченных наборов из

n

-элементного множества равно

n^{k}

Доказательство. Совсем аккуратное доказательство проводится по индукции, но и без неё всё довольно наглядно. Пусть нам нужно выбрать

k

-элементный упорядоченный набор. Будем выписывать его по очереди. У нас есть

n

различных способов выбрать первый элемент, см. рис. 8.5. После того, как первый элемент выбран, к нему нужно приписать второй элемент, и это можно сделать

n

разными способами. Всего получается

n \times n

способов выписать первые два элемента. Когда первые два элемента зафиксированы, есть

n

способов выписать третий элемент, значит количество вариантов умножается на

n

и становится равно

n^{2} \times n = n^{3}

. И так далее до

k

-го элемента.

Иллюстрация к построению всех возможных упорядоченных наборов из
элементов 1 и 2. Из левой точки выходят две стрелочки, на одной
написано 1, на другой 2, они указывают в две новые точки. Из
каждой из этих точек выходят по две стрелочки (опять на одной
написано 1, на другой 2), которые ведут в четыре новые точки. Из
каждой из этих точек выходит по две стрелочки, получается 8
точек. Каждой из этих точек соответствует упорядоченный набор,
который считывается из цифр, написанных на стрелочках.

Рис. 8.5: Построение всевозможных трёхэлементных упорядоченных наборов из чисел

1

2

. Выбор каждого следующего элемента удваивает количество наборов.

∎

8.3.2Наборы без повторений

Рассмотрим теперь упорядоченные наборы без повторяющихся элементов.

Утверждение 2. Количество

k

-элементных упорядоченных наборов из

n

-элементного множества равно

n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!},

где

n! = 1 \times 2 \times 3 \times \dots \times n

—

n

-факториал. (По определению полагают, что

0! = 1

Доказательство. Доказательство очень похоже на доказательство утверждения 1, см. рис. 8.6 Будем выписывать набор последовательно. Есть

n

способов выбрать первый элемент. После того, как первый элемент выбран, остаётся

(n - 1)

способ выбрать второй элемент (потому что повторяться нельзя, и значит множество допустимых элементов сокращается на

1

). Значит, есть

n \cdot (n - 1)

способов выбрать первые два элемента. И так далее. Получится

k

сомножителей, начиная с

n = (n - 0)

. Значит, последний сомножитель будет

(n - (k - 1)) = (n - k + 1)

. (Чтобы не запутаться, всегда полезно подставить какое-нибудь конкретное значение — например,

k = 2

— и посмотреть, что получится.)

Иллюстрация к построению всех возможных упорядоченных наборов из
элементов 1, 2, 3, 4 без повторений длины 3. Из левой точки
выходят четыре стрелочки, на них написано 1, 2, 3, 4, они
указывают в четыре новые точки. Из каждой из этих точек выходят по
три стрелочки, на каждой из которых написана цифра, которая не
написана на входящей стрелочке. Получается 12 новых точек. Из
каждой из них выходит по две стрелочки с двумя оставшимися
цифрами, получается 24 точки. Каждой из этих точек
соответствует упорядоченный набор, который считывается из цифр,
написанных на стрелочках.

Рис. 8.6: Построение всевозможных трёхэлементных упорядоченных наборов без повторений из чисел

1

2

3

4

. На каждом следующем шаге число возможных элементов уменьшается на 1.

∎

8.3.3Неупорядоченные наборы без повторений

Сколько существует

k

-элементных подмножеств данного

n

-элементного множества? Если выписать элементы подмножества в строчку, получится

k

-элементный набор без повторений. Однако, между упорядоченными наборами и подмножествами есть важное различие: множество не упорядочено. Наборы

(1, 2)

(2, 1)

— разные наборы, множества

{1, 2}

{2, 1}

— одно и то же множество. Поэтому количество упорядоченных наборов больше количества подмножеств. Во сколько раз?

Вопрос 3. Пусть есть

k

-элементное множество. Сколькими способами его элементы можно упорядочить (выстроить в ряд)? Иными словами, сколько есть различных

k

-элементных наборов без повторяющихся элементов из элементов данного

k

-элементного множества?

Ответ на этот вопрос содержится в утверждении 2: нужно просто подставить $n = k$ . Видно, что в этом случае $(n - k) = 0$ , а по определению $0! = 1$ . Значит, искомое число способов равно $k!$ .

Утверждение 3. Обозначим количество

k

-элементных подмножеств

n

-элементного множества через

C_{n}^{k}

. Тогда

\begin{matrix} C_{n}^{k} = \frac{n (n - 1) \dots (n - k + 1)}{k!} = \frac{n!}{k! (n - k)!} . \\ (8.4) \end{matrix}

\begin{matrix} C_{n}^{k} = \frac{n (n - 1) \dots (n - k + 1)}{k!} = = \frac{n!}{k! (n - k)!} . \\ (8.4) \end{matrix}

Доказательство. Пусть мы выписали все

\frac{n!}{(n - k)!}

упорядоченных

k

-элементных наборов наборов из элементов нашего

n

-элементного множества (см. утверждение 2 ). Рассмотрим какой-нибудь из этих наборов. Его элементы можно переставлять

k!

разными способами, получая новые наборы из нашего списка (включая его самого). Все они задают одно и то же подмножество. Значит, если мы хотим посчитать подмножества, нужно все эти

k!

наборов посчитать один раз. Таким образом, чтобы получить количество подмножеств из количества наборов, надо количество наборов разделить на

k!

. (Поскольку каждому подмножеству соответствует ровно

k!

упорядоченных наборов.) Отсюда и следует формула (8.4).

Упорядоченные наборы с предыдущей картинки, которые задают одно
и то же множество, объединены. Например, множеству {1, 2, 3}
соответствует шесть наборов: (1, 2, 3), (1, 3, 2), (2, 1, 3),
(2, 3, 1), (3, 1, 2), (3, 2, 1).

Рис. 8.7: Построение всевозможных трёхэлементных подмножеств множества

{1, 2, 3, 4}

. Мы сначала построили всевозможные упорядоченные 3-элементные наборы без повторений, а потом объединили те из них, которые отличаются только порядком и следовательно задают одно и то же множество. На рисунке отмечены два таких объединения, в каждом по 6 наборов (здесь

6 = 3!

— число способов переставить три элемента). Напишите, какие два множества мы не указали, и отметьте все наборы, которые задают эти множества.

∎

Упражнение 2. Самый лучший способ понять все утверждения, сформулированные выше, такой: взять какое-нибудь небольшое

n

k

и пройти все шаги. Например,

n = 4

k = 2

. Выпишите все двухэлементные упорядоченные наборы без повторений с элементами из множества

X = {1, 2, 3, 4}

, руководствуясь алгоритмом из утверждения 2. Посчитайте, сколько их получилось. Затем объедините их в группы, так, чтобы в каждой группе наборы отличались только порядком (и следовательно задавали одно и то же множество). Сколько элементов в каждой группе? Сколько всего групп? Повторите эти действия, например, с

n = 5

k = 3

Замечание 5. Числа

C_{n}^{k}

называются биномиальными коэффициентами (почему так — будет ясно в следующем разделе) или числом сочетаний из $n$ элементов по $k$ . Другое обозначение:

(\frac{n}{k})

— обратите внимание, что в этом случае

n

ставится сверху.

8.3.4Бином Ньютона

Рассмотрим выражение

(a + b)^{n}

. Что получится, если раскрыть в нём скобки и привести подобные слагаемые?

Пример 3. Посмотрим, что происходит при небольших значениях

n

\begin{matrix} (a + b)^{2} = (a + b) (a + b) = a a + a b + b a + b b = a^{2} + 2 a b + b^{2}; \end{matrix}

\begin{matrix} (a + b)^{2} = (a + b) (a + b) = = a a + a b + b a + b b = = a^{2} + 2 a b + b^{2}; \end{matrix}

\begin{matrix} (a + b)^{3} & = (a + b) (a + b) (a + b) = (a + b) (a a + a b + b a + b b) = = a a a + a a b + a b a + a b b b a a + b a b + b b a + b b b = = a^{3} + 3 a^{2} b + 3 a b^{2} + b^{3} . \end{matrix}

\begin{matrix} (a + b)^{3} & = (a + b) (a + b) (a + b) = = (a + b) (a a + a b + b a + b b) = = a a a + a a b + a b a + a b b + b a a + b a b + b b a + b b b = = a^{3} + 3 a^{2} b + 3 a b^{2} + b^{3} . \end{matrix}

Мы видим, что если не приводить подобные слагаемые, каждый раз получается сумма всевозможных мономов, состоящих из $n$ сомножителей, каждый сомножитель — $a$ или $b$ — они выглядят как «слова» типа $a a b a$ . Так будет и дальше: каждый раз нужно умножить $(a + b)$ на $(a + b)^{n - 1}$ , то есть приписать слева к каждому «слову», получающемуся в $(a + b)^{n - 1}$ , букву $a$ (получили $(n - 1)$ новых «слов» длины $n$ ), а затем букву $b$ (получили ещё $(n - 1)$ новых «слов» длины $n$ ), и всё сложить. Если в разложении $(a + b)^{n - 1}$ были все $(n - 1)$ -буквенные «слова» из букв $a$ и $b$ , то в разложении $(a + b)^{n}$ будут все $n$ -буквенные слова из букв $a$ и $b$ .

Теперь нужно привести подобные слагаемые. Например, для $(a + b)^{2}$ мы замечаем, что $a b = b a$ и значит коэффициент при $a b$ равен двум. Для $(a + b)^{3}$ , чтобы посчитать коэффициент при $a^{2} b$ , нужно найти количество «слов», в которых две буквы $a$ и одна буква $b$ . Таких слов 3: $a a b$ , $a b a$ и $b a a$ . Значит, коэффициент при $a^{2} b$ равен трём.

Теорема 3. Если раскрыть собки и привести подобные слагаемые в выражении

(a + b)^{n}

, получится сумма мономов вида

a^{k} b^{n - k}

, коэффициент перед каждым таким мономом равен

C_{n}^{k}

(a + b)^{n} = n \sum k = 0 C_{n}^{k} a^{k} b^{n - k} .

Доказательство. Коэффициент при выражении

a^{k} b^{n - k}

— это количество различных «слов» длины

n

, в которых входит ровно

k

раз буква

a

и оставшиеся

(n - k)

раз буква

b

. Сколько таких слов существует? Поскольку мы знаем длину слова (она равна

n

), и знаем, что в слове бывают только буквы

a

b

, чтобы задать такое слово, нужно просто задать, на каких позициях стоят буквы

a

. Всего возможных позиций

n

, из них

k

позиций нужно заполнить буквами

a

. Чтобы выбрать эти позиции, нужно из

n

-элементного множества (всех позиций) выбрать

k

-элементное подмножество (тех позиций, на которых мы напишем

a

). Это можно сделать

C_{n}^{k}

различными способами.∎

Замечание 6. Разумеется, у этой теоремы есть строгое формальное доказательство через индукцию. Провести его — полезное упражнение. Однако, на мой взгляд, понять смысл из этого доказательство — довольно трудно. Поэтому я его здесь не привожу.

8.4Число $e$

Рассмотрим следующий предел

lim n \to \infty {(1 + \frac{1}{n})}^{n} .

Чему он равен? Если вы попробуете применить арифметику пределов, то заметите, что основание степени стремится к

1

, а показатель — к бесконечности. Чему «равняется»

1^{\infty}

? Увы, это неопределенность. Лобовой метод тут не работает. Мы пока даже не знаем, существует этот предел, или нет. Однако, скоро узнаем.

Утверждение 4. При всех

n

{(1 + \frac{1}{n})}^{n} < 3.

Доказательство. Случай

n = 1

разбирается явно. Пусть

n > 1

. Раскроем скобки по биному Ньютона (ага! пригодился!). Имеем:

\begin{matrix} {(1 + \frac{1}{n})}^{n} = 1^{n} + \frac{n}{1!} \frac{1}{n} + \frac{n (n - 1)}{2!} \frac{1}{n^{2}} + \frac{n (n - 1) (n - 2)}{3!} \frac{1}{n^{3}} + \dots + \frac{n (n - 1) (n - 2) \dots 1}{n!} \frac{1}{n^{n}} . \\ (8.5) \end{matrix}

\begin{matrix} {(1 + \frac{1}{n})}^{n} = 1^{n} + \frac{n}{1!} \frac{1}{n} + + \frac{n (n - 1)}{2!} \frac{1}{n^{2}} + + \frac{n (n - 1) (n - 2)}{3!} \frac{1}{n^{3}} + \dots + + \frac{n (n - 1) (n - 2) \dots 1}{n!} \frac{1}{n^{n}} . \\ (8.5) \end{matrix}

Первые два слагаемые равны

1

. Рассмотрим

(k + 1)

-е слагаемое,

k > 2

. Оно имеет вид:

\begin{matrix} \frac{n (n - 1) \dots (n - k + 1)}{k!} \frac{1}{n^{k}} = \frac{n}{n} \frac{n - 1}{n} \dots \frac{n - k + 1}{n} \frac{1}{k!} = = (1 - \frac{1}{n}) \dots (1 - \frac{k - 1}{n}) \frac{1}{k!} \\ (8.6) \end{matrix}

\begin{matrix} \frac{n (n - 1) \dots (n - k + 1)}{k!} \frac{1}{n^{k}} = = \frac{n}{n} \frac{n - 1}{n} \dots \frac{n - k + 1}{n} \frac{1}{k!} = = (1 - \frac{1}{n}) \dots (1 - \frac{k - 1}{n}) \frac{1}{k!} \\ (8.6) \end{matrix}

Иными словами, оно состоит из

(k - 1)

сомножителя вида

1 - \frac{m}{n}

, где

m

меняется от

1

до

(k - 1)

, и последнего сомножителя

\frac{1}{k!}

Заметим, что каждый из сомножителей вида $1 - \frac{m}{n}$ меньше 1. Значит, всё слагаемое меньше $\frac{1}{k!}$ . Но с другой стороны $2^{k - 1} \leq k!$ для всех натуральных $k$ (проверьте, а ещё лучше — докажите по индукции, что это так) и значит $\frac{1}{k!} \leq \frac{1}{2^{k - 1}}$ . Имеем:

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

Слагаемые, начиная с третьего, образуют геометрическую прогрессию с положительным знаменателем, меньшим

1

. Её сумма меньше суммы соответствующей бесконечной геометрической прогрессии, которая в свою очередь равна 1. (Не нужно знать формулу суммы бесконечной геометрической прогрессии, чтобы это увидеть: если у вас была одна шоколадка, вы её разломали пополам, съели половину (то есть

1 / 2

), остаток разломали снова пополам, съели половину от половину (то есть

1 / 2^{2}

) и т.д., в каждый момент времени вы съедите меньше, чем целую шоколадку, а в пределе съедите её всю.) Значит, вся сумма меньше трёх.∎

Утверждение 5. Последовательность

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

монотонно возрастает.

Доказательство. Рассмотрим представление (8.5). Что произойдёт при увеличении

n

на единицу? Первые два слагаемые не изменятся. Добавится ещё одно неотрицательное слагаемое. Что произойдёт с остальными?

Первые два слагаемые равны 1, они не изменятся. Слагаемые, начиная с третьего, задаются формулой (8.6). Возьмём какое-то конкретное слагаемое, то есть зафиксируем какое-то $k > 2$ . Посмотрим на правую часть (8.6). Что произойдёт с ней, когда $n$ увеличится, а $k$ останется прежним? Во-первых, сомножитель $\frac{1}{k!}$ , стоящий в конце, не изменится. Во-вторых, количество сомножителей вида $1 - \frac{m}{n}$ тоже не изменится, их $(k - 1)$ штука. Наконец, каждый из сомножителей такого вида при увеличении $n$ увеличивается, поскольку дробь $\frac{m}{n}$ уменьшается, но перед ней стоит минус.

Итак, в результате увеличения $n$ на единицу к сумме (8.6) добавится положительное слагаемое, а остальные слагаемые не уменьшатся. Значит, сумма возрастёт.∎

Следствие. Таким образом, наша последовательность возрастает и ограничена сверху. Значит, по теореме Вейерштрасса, у неё есть предел.

Оказывается, этот предел не записывается в виде какого-либо простого арифметического выражения, и представляет собой иррациональное число. Оно обозначается буквой $e$ и играет важную роль в построении анализа.

8.5Заключение

Мы доказали теорему Вейерштрасса, позволяющую исследовать на сходимость монотонные ограниченные последовательности. С её помощью, а также с помощью бинома Ньютона, мы определили число

e

как предел некоторой последовательности. Оно нам ещё пригодится.

← Предыдущая глава Следующая глава →

Математический анализ Записки лекций

8Теорема Вейерштрасса, немного комбинаторики и число e

8.1Ограниченные множества

8.1.1Максимум и минимум

8.1.2Точная верхняя и нижняя грани

8.2Теорема Вейерштрасса

8.3Биномиальные коэффициенты

8.3.1Упорядоченные наборы

8.3.2Наборы без повторений

8.3.3Неупорядоченные наборы без повторений

8.3.4Бином Ньютона

8.4Число e

8.5Заключение

Математический анализ
Записки лекций

8.4Число $e$