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

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

Формулировка принципа: Пусть требуется доказать истинность утверждения Р(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+1.

Тогда 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+1), т.е. | A ´ B _k+1 | = m^. (k+1) =| A |^.| B _{k +1} |. Значит тождество справедливо для всех подмножеств, содержащихся в В, а значит справедливо и для самого В, т.е. | 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|, если А₁, А₂,..., А_р - конечные множества.