Принцип полной математической индукции.

Одним из важнейших методов получения результатов, связанных со свойствами элементов конечных множеств, является принцип (метод) математической индукции. Заключается он в следующем:

Формулировка принципа: Пусть требуется доказать истинность утверждения Р(n) для любого натурального n, начиная с некоторого n₀. Если для некоторого натурального n₀ Î N (обычно n₀= 1, но не всегда) мы можем доказать истинность Р(n₀)- (I шаг) и для любого n Î N, такого что n ³ n₀, справедливость Р(n) влечет справедливость Р(n + 1)- (II шаг), то утверждение Р(m) справедливо для любого натурального m ³ n₀.

I шаг - основание индукции, II шаг - шаг индукции.

Доказательство этого принципа основано на одном интуитивно-ясном факте: Всякое подмножество множества N содержит свой минимальный элемент. Смысл его состоит в том, что между 1 и 2, 2 и 3, ..., n и n+1 нет элементов из N. Строгое доказательство этого факта основано на способе построения множества N и выходит за рамки данного курса (подробное обсуждение этих вопросов смотри в книгах [2] и [4] ).

Доказательство принципа математической индукции.

От противного.

Пусть S= {s | s Î N и P(s) неверно} Ì N не пусто. Тогда, согласно вышесказанному, S содержит наименьший элемент s₀. Тогда P(s₀)- ложно. Но P(s)- истинно для всех n₀ £ s < s₀, а значит оно истинно и для s₀ - 1. Тогда, применяя шаг индукции, получаем, что P(s₀) - истинно. Противоречие.

Пример 1.Доказать, что 1²+ 2²+... + n²= n(n+ 1)(2n+ 1)/ 6.

I. Основание индукции. При n = 1 имеем: 1²= (1^. 2^.3)/ 6= 1.

II. Шаг индукции.

Пусть при n = k утверждение 1²+ 2²+... +k²= — истинно. Обозначим эту сумму S_k. Докажем, что утверждение верно при n = k+1, т.е. 1²+ 2²+... +k²+ (k+1)²= = S_k₊₁.

Тогда S_k + (k+1)²= + (k+1)²= ´ [ k ( 2k+1) +

+ 6 (k+1)] = [ 2k²+ k+ 6k+ 6] = ( 2k²+ 7k+ 6 ) =

= ^.2 (k+2) (k+3/2) = .

Таким образом, мы доказали, что из истинности утверждения для n = k следует его истинность для n = k+ 1. Значит утверждение верно для любого натурального n.

Что и требовалось доказать.

Рассмотрим более сложный пример.

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

Теорема:Если А и В конечны, то | А ´ В | = | A | ^. | B |.

Доказательство: Пусть | A | = m и | B | = n, т.е. существуют биекции f: A ~ N_m и g: B ~ N_n. Будем вести индукцию по n - мощности В. От мощности А требуется конечность, поскольку мы предполагаем знакомство лишь с умножением конечных величин.

I. Основание индукции. Если В= Æ, то A x B= Æ, и поэтому имеем | A x B | = 0 = | A | ^.0 = | A | ^.| B |. При n = 1 : B = { b }, тогда отображение A ® A x B такое, что а ( а, в ), очевидно, биективно и поэтому

| A x B | = | A | = | A | ^.1 = | A | ^.| B |.

II. Шаг индукции. Индукцию будем вести по подмножествам множества В.

Предположим, что | A x B_k|= m ^. kÎ N. А значит $ биекция h: A x B_k ~ N_m_._k. Рассмотрим подмножество В мощности k + 1 = j. Поскольку B_k любое подмножество мощности k, то B_j- можно представить в виде: B_j = B_k È { x }, x Î B и x Ï B_k.

Определим отображение t: A x B_j ® N следующим образом: если b Î B_k, то t: (a, b) h (a, b). Во всех остальных случаях t: (a, x) f(a) + m^.k.

Тогда t (A ´{ x } ) = { 1 + m ^.k, 2 + m ^.k, ..., m+m ^.k}, при этом

t ( A ´ B_k ) = { 1, 2,..., m ^.k }.

Значит t есть биекция A ´ B _j на {1, 2, ..., m ^.k, m ^.k + 1, m ^.k +2, ..., m ^.k + m} = N _m _k₊_m, но m ^.k + m = m ( k + 1 ). Значит мы установили биекцию A ´ B _j на N_m₍_k₊₁₎, т.е. | A ´ B _k₊₁ | = m^. (k+1) =| A |^.| B _k ₊₁|. Значит тождество справедливо для всех подмножеств, содержащихся в В, а значит справедливо и для самого В, т.е. | A ´ B | = | A | ^. |B|.

Что и требовалось доказать.

Замечание 1. Если воспользоваться тем фактом, что если X и Y разбиение множества Z, а X и Y- конечны, то | Z | = | X | + | Y |, то доказательство можно провести и так: A ´ B _j = A ´ ( B _k È {x}) = [по свойству A ´ ( BÈ C) = ( A ´ B ) È ( A ´ C ) ] = A ´ B _k È A ´ {x} - это разбиение множества A ´ B _j, а значит

|A ´ B_J |= |A ´ B _k |+ |A ´{x}| = |A ´ B _k |+ |A|= m ^.k+ m = m (k+1). Однако, этот факт (|Z |= |X | + |Y |) вообще говоря, тоже надо доказывать по индукции, (докажите самостоятельно).

Упражнение. Докажите по индукции, что для p³ 2, pÎ N

| A₁´A₂ ´... ´ A _p|= |A₁| ^. |A₂| ^. ...^.|A _p|, если А₁, А₂,... , А_р- конечные множества.

Пол и потолок.

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

Рассмотрим произвольное вещественное число – Х.

Определение: Для любого действительного числа Х, наибольшее целое число, меньшее или равное Х, называется «полом» числа Х и обозначается |_Х_|. Также |_Х_| называют целой частью любого действительного числа.

Определение: Для любого действительного числа Х, наименьшее целое число, большее или равное Х, называется «потолком» числа Х и обозначается |‾Х‾|.

Обозначения |_Х_| и |‾Х‾| введены Кеннетом Э. Айверсоном в начале 60-х годов. До недавнего времени чаще использовалась запись [Х] – для небольшого целого числа, которое ≤Х, а для обозначения наименьшего целого – символа не существовало.

Нужно отметить, что в некоторых калькуляторах имеется функция INT, определяемая как |_Х_| при положительном Х и как |‾Х‾| при отрицательном Х.

Определение: Для любого действительного числа Х, разность между числом Х и его полом |_Х_| называется дробной частью числа Х и обозначается: {Х}=Х-|_Х_|. (1)

Так если произвольное действительное число х=n+α, где n - целое число, а 0≤α<1, то можно сказать, что n = |_Х_|, а α = {Х}.

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

Справедливы следующие неравенства, для Х R; n z.

1°. x<n <=> |_Х_|<n

2°. n<x <=> n<|‾Х‾|

3°. x≤n <=> |‾Х‾|≤n

4°. n≤x <=> n≤|_Х_|.

Свойства 1°-4° очевидны и легко доказываются. Например, свойство 1°.

Доказательство: Если x<n, то очевидно, что |_Х_|<n, т.к. |_Х_|≤Х. И наоборот, если |_Х_|<n, то непременно x<n, т.к. х=|_Х_|+α, где 0≤α<1, а |_Х_|+α< n.

Аналогично доказываются свойства 2°-4°.

Рассмотрим функции пол и потолок графически. Графики функции пол и потолок располагаются лесенкой ниже и выше графика функции f(x)=X

Например, при х=- е и х=е из данного графика видно

|_е_|=2 |_-е_|=-3

|‾е‾|=3 |‾-е‾|=-2, т.к. е=2,71828…

из графика видно, что если функция пол лежит на и под диагональной линией f(x)=X, то |_Х_|≤Х, точно также |‾Х‾|≥Х, что соответствует определению этих понятий. В целых точках (х Z) обе эти функции совпадают:

|_Х_|=Х <=> Х Z <=> |‾Х‾|=Х.

Если х<Z, то потолок ровно на единицу выше пола:

|‾Х‾| - |_Х_| = 1.

Если сдвинуть график функции f(x)=X вниз на единицу, то она целиком окажется под функцией пол, отсюда следует, что х-1<|_Х_|;

Аналогично, получим х+1>|‾Х‾|, если сдвинуть график вверх на единицу.

Объединяя последние два неравенства, получаем, что

х-1<|_Х_|≤Х≤|‾Х‾|< х+1 (3)

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

|_-Х_|=-|‾Х‾| и |‾-Х‾| = - |_Х_| (4)

Таким образом, каждая из них легко выражается через другую. Это обстоятельство позволяет объяснить, почему функцию потолок прежде не имела собственного обозначения. Но потолки встречаются столь часто, что требует своего символьного знака отличия.

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

|_Х_| =n <=> n≤x<n+1, (a)

|_Х_| =n <=> x-1<n≤x, (b) (5)

|‾Х‾| =n <=> n-1<x≤n, (c)

|‾Х‾| =n <=> x≤n<x+1, (d)

где n Z, а Х R. Правила (а) и (с)- следствия определений пола и потолка; правила (b) и (d) - те же неравенства (а) и (с), разрешенные относительно n.

Рассмотрим ещё одно свойство. Целочисленное слагаемое можно вносить (выносить) в (за) скобки пола или потолка:

|_Х+n_| =|_Х_| +n, n Z (1)

|‾Х+n‾| =|‾Х‾| +n, n Z (2) (6)

Действительно в соответствии с правилом (а) равенство (1) можно представить в виде неравенства:

|_Х_| +n≤x+n|_Х_| +n+1.

Однако операция внесения (вынесения) за скобки, в общем случае недопустима. Так, |_nХ_| ≠n|_Х_|, когда n=2 и х=1/2. Это значит, что скобки пола и потолка недостаточно гибки, следовательно избавиться от них не так просто.

Равенства (1) и (2) не выполняются, если n – действительное число (n R).

В общем для |_х+у_| имеются две возможности. Если Х и У записать в виде:

Х=|_Х_|+{Х}; У=|_У_|+{У}, то получим |_х+у_|=|_х_|+|_у_|+|_{х}+{у}_|, т.к. 0≤{Х}+{У}<2, то оказывается в некоторых случаях |_х+у_|=|_х_|+|_у_|, а в остальных |_х+у_|=|_х_|+|_у_|+1

123 4 5 6

Не нашли, что искали? Воспользуйтесь поиском по сайту: