Индукция и комбинаторика

Метод математической индукции

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

Пусть P(n) - это некоторое утверждение, зависящее от целочисленного параметра n. Пусть, во-первых, утверждение P(n0) справедливо и пусть, во-вторых, для любого k >= n0 из справедливости P(k) следует справедливость P(k+1). Тогда утверждение P(n) справедливо для всех n >= n0.

Таким образом доказательство "по индукции" состоит из двух этапов.

Базис (или основание) индукции состоит в доказательстве утверждения P(n0) для некоторого начального значения n0 ( обычно n0=1, но это не обязательно).

Шаг индукции состоит в предположении справедливости P(n) при n=k >= n0 и доказательстве из этого предположения справедливости утверждения P(k+1) .

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

Пример 1. Доказать, что при n>= 1

$$1^3 +2^3 + \ldots + n^3 = \frac{(n(n+1))^2}{4}.$$

Базис индукции. При n=1 имеем

$$1^3=\frac{(1(1+1))^2}{4}$$.

Шаг индукции. Допустим, что при n=k

$$1^3 +2^3 + \ldots + k^3 = \frac{(k(k+1))^2}{4}.$$

Докажем тогда, что при n=k+1

$$1^3 +2^3 + \ldots + k^3 +(k+1)^3= \frac{((k+1)(k+2))^2}{4}.$$

Действительно,

$$1^3 +2^3 + \ldots + k^3 +(k+1)^3=\frac{(k(k+1))^2}{4} +(k+1)^3 =\\ (k+1)^2\cdot(\frac{k^2}{4}+k+1)= (k+1)^2\cdot \frac{(k+2)^2}{4}= \frac{((k+1)(k+2))^2}{4}.$$

Таким образом, наше утверждение выполненопри всех n>= 1.

Пример 2. Доказать, что для любого $$x > -1,\ x \ne 0$$, и натурального n>= 2 выполнено неравенство (1+x)n > 1 +nx (это неравенство называют неравенством Бернулли).

Базис индукции. При $$n=2$$, учитывая, что $$x^2 > 0$$, имеем (1+x)2=1 +2x +x2 > 1+2x.

Шаг индукции. Допустим, что при n=k неравенство справедливо, т.е. (1+x)k > 1 +kx. Покажем, что тогда оно выполнено и при n=k+1. Действительно, так как 1+x > 0, то умножив обе части на 1+x > 0, получим (1+x)k(1+x)=(1+x) k+1 > (1+kx)(1+x)=1+ (k+1)x +kx2> 1+(k+1)x, что и требовалось.

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

Отметим также, что приведенная формулировка принципа математической индукции допускает разные эквивалентные варианты. В ряде случаев мы будем использовать вариант, в котором шаг индукции состоит в предположении справедливости P(n) при всех n <= k и доказательстве из этого предположения справедливости утверждения P(k+1).

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

В дискретной математике и в информатике многие классы объектов определяются индуктивно. В таких определениях явно или неявно участвует некоторая функция, задающая "сложность" объекта, и индукция идет по значениям этой функции. На базисном шаге определяются объекты минимальной сложности (обычно они имеют сложность 0), а индукционный шаг определения заключается в том, что из объектов меньшей сложности с помощью некоторых операций (операторов, конструкций) строятся объекты большей сложности.

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

Базис индукции состоит в проверке требуемого свойства у объектов минимальной сложности.

Шаг индукции состоит в предположении справедливости доказываемого свойства

у всех объектов класса, имеющих сложность <= k, и проверке того, что все объекты большей сложности (обычно, сложности k+1 ), получаемые из них с помощью используемых при определении класса операций, также обладают требуемым свойством.

Рассмотрим эту схему на примере простых арифметических выражений.

Пример 2.1. Пусть V ={x, y, z} - множество переменных, O={+, -, *, / } - список операций. Определим индуктивно множество $$\mathcal{A}$$ выражений ( слов) в объединенном алфавите $$\Sigma = V \cup O \cup \{ ( , )\}$$, называемых арифметическими формулами. Одновременно будем определять меру сложности этих формул, назывемую их глубиной. Глубину формулы $$\phi$$ обозначим через $$d(\varphi )$$.

Базис индукции. Каждая переменная $$v \in V$$ является арифметической формулой глубины 0, т.е. $$v \in codecal\{ A\}$$ и d(v)=0.

Шаг индукции. Пусть $$\varphi _{1}$$ и $$\varphi _{2}$$ - арифметические формулы глубины $$d(\varphi _{1})$$ и $$d(\varphi _{2})$$, соответственно. Тогда выражения

(а) $$(\varphi _{1} + \varphi _{2})$$,

(б) $$(\varphi _{1} - \varphi _{2})$$,

(в) $$(\varphi _{1} * \varphi _{2})$$,

(г) $$(\varphi _{1} / \varphi _{2})$$,

также являются арифметическими формулами из $$\mathcal{A}$$ и каждая из этих формул имеет глубину $$max\{ d(\varphi _{1}),d(\varphi _{2}) \} +1$$.

Пусть w=w1w2 ... wn - произвольное слово в алфавите $$\Sigma.$$ Скажем, что скобки в w расставлены правильно, если для каждого i <= n число левых скобок в слове w(i)=w1w2 ... wi не меньше числа правых скобок, а во всем слове w число левых скобок равно числу правых.

Докажем, что в каждой арифметической формуле из $$\mathcal{A}$$ скобки расставлены правильно.

Базис индукции. $$d(\varphi )= 0$$. Формула глубины 0 является переменной $$v \in V$$. В ней нет скобок и поэтому они расставлены правильно.

Шаг индукции. Пусть утверждение справедливо для всех формул из $$\mathcal{A}$$ глубины <= k и $$\phi$$ - произвольная формула глубины $$d(\varphi )= k+1$$. Тогда она имеет одну из четырех форм (а), (б), (в) или (г). Предположим, что $$\varphi = (\varphi _{1} + \varphi _{2})$$. Тогда из определения глубины следует, что $$d(\varphi _{1})\le k$$ и $$d(\varphi _{2}) \le k$$, и по индукционному предположению в обеих формулах $$\varphi _{1}$$ и $$\varphi _{2}$$ скобки расставлены правильно. Покажем, что и в $$\phi$$ скобки расставлены правильно. Пусть $$\varphi _{1}=\{v_{1}v_{2} \dots v_{m1}\}$$ и $$\varphi _{2}=\{w_{1}w_{2} \dots w_{m2}\}$$. Тогда $$\varphi =t_{1}t_{2} \dots t_{M}= (v_{1}v_{2} \dots v_{m1}+w_{1}w_{2} \dots w_{m2})$$, здесь M= m1+m2 +3 и все символы vi, wj принадлежат алфавиту $$\Sigma.$$ Для каждого 1 < i <= m1+1 число левых скобок в t1 ... ti на 1 больше числа левых скобок в v1... vi-1, и следовательно, больше числа правых скобок в этом слове, так все они входят в v1... vi-1. Это же справедливо для слова t1t2 ... tm1+2, заканчивающегося символом +. При m1+2 < i < M разница между числом левых и правых скобок в t1 ... ti не меньше 1, так как t1= (, а в $$\varphi _{1}$$ и $$\varphi _{2}$$ скобки расставлены правильно. Во всем слове $$\phi$$ число левых и правых скобок совпадает, так как к скобкам $$\varphi _{1}$$ и $$\varphi _{2}$$ добавилась одна левая и одна правая скобка. Таким образом, в $$\phi$$ скобки расставлены правильно. Случаи (б), (в) и (г) рассматриваются аналогично.

Задачи

Задача 2.1. Доказать, что

$$1^4 +2^4 + \ldots + n^4 = \frac{1}{30}n(n+1)(2n+1)(3n^2+3n-1).$$

Задача 2.2. Доказать, что

$$1\cdot 2 +2\cdot 3 + \ldots + n(n+1) = \frac{n(n+1)(n+2)}{3}.$$

Задача 2.3. Доказать, что

$$1 + x+ x^2 +x^3 + \ldots + x^n =\frac{x^{n+1}-1}{x - 1}.$$

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

Задача 2.5. Найдите ошибку в следующем доказательстве "по индукции" утверждения:

для всех n >= 1 справедливо неравенство 3n > 3(n +1) +1 .

Доказательство Пусть для некоторого k >= 1 неравенство справедливо, т.е. 3k > 3(k +1) +1 (*). Докажем, что оно верно и для n=k+1, т.е. 3k+1 > 3(k+2) +1. Для этого заметим, что для любого k >= 1 верно неравенство 2 cdot 3k > 3. Прибавив его левую и правую часть к соответствующим частям неравенства (*), получим 3k + 2 x 3k > 3(k +1) +1+3 или 3 k+1 > 3(k+2) +1, что и требовалось. Установите, при каких n справедливо неравенство 3n > 3(n +1)+1.

Элементы комбинаторики

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

Размещения, перестановки, сочетания

Многие классические задачи комбинаторики являются задачами определения числа способов размещения некоторых объектов в каком-то количестве "ящиков" так, чтобы выполнялись определенные ограничения. Более формально такие задачи можно сформулировать следующим образом. Даны множества X, Y, причем |X|=n, |Y|=m. Сколько существует функций f: X -> Y, удовлетворяющих заданным ограничениям? Здесь элементы X - объекты, а элементы Y - ящики, а каждая функция f: X -> Y определяет для каждого объекта $$x\in X$$ в какой ящик $$f(x) \in Y$$ он помещается.

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

Теорема 2.1. Если |X| = n, |Y|=m, то число всех функций f: X -> Y равно mn.

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

Пусть X={x1,... , xn}, Y={y1,... , ym}. Тогда каждая функция f: X -> Y однозначно определяется последовательностью своих значений f(x1), ... , f(xn). Пусть Fm(n) - число всех таких функций (последовательностей).

Базис индукции. Ясно, что при n=1 имеется ровно m различных функций: fi(x1)=yi, i=1,..., m, т.е. Fm(1)=m.

Шаг индукции. Предположим, что при n=k выполнено равенство Fm(k)=mk. Докажем, что тогда Fm(k+1)=mk+1.

Действительно, при n=k+1 каждая функция f: X -> Y - это последовательность f(x1), ... ,f(xk), f(x{k+1}). Положив X'={x1,... , xk}, ее можно рассматривать как функцию f':X' -> Y, заданную последовательностью f(x1), ... , f(xk), которая дополнена одним новым значением f(x{k+1}). Так как |X'|=k, то по предположению число таких различных функций f':X' -> Y равно Fm(k)=mk. Каждая из них имеет ровно m возможных расширений f(x{k+1}) = yi, i=1,... , m. Поэтому Fm(k+1)= Fm(k) x m =mk+1.

Следствие 2.1.1. Если |X|=n, то число всех подмножеств множества X равно |2X|= 2n.

Доказательство. Пусть X={x1,... , xn}. Сопоставим каждому подмножеству $$X' \subseteq X$$ функцию fX' : X -> {0,1} следующим образом:

$$$$ f_{X'}(x_i) = \left \{\begin{array}{ll} 1, \mbox{ если $ x_i \in X' $ }\\ 0, \mbox{ в противном случае} \end{array} \right. $$$$

(i=1, ... , n).

Ясно, что это сопоставление взаимно однозначное. Действительно, если $$X^{'} \ne X^{\{''\}}$$, то имеется элемент $$x_i \in X^\prime \dot{-} X^{\prime\prime}$$ и тогда $$f_{X'}(x_{i}) \ne f_{X''}(x_{i})$$. Таким образом, число всех подмножеств X равно числу всех функций f : X -> {0,1}. По теореме 2.1 это число равно 2n.

Следствие 2.1.2. Число всех слов длины n в алфавите A={a1, ..., am} из m символов равно mn.

Найдем теперь число размещений, для которых каждый ящик содержит не более одного объекта. Такие размещения соответствуют 1-1- функциям. Обозначим через Amn число всех 1-1-функций из n -элементного множетства в m -элементное множество. Это число называется числом размещений из m по n.

Теорема 2.2. Если |X| = n, |Y|=m, то число всех 1-1-функций f: X -> Y равно

$$A_m^n= m(m-1)\ldots (m-n+1)$$

Доказательство проведем индукцией по n (для каждого фиксированного m ).

Базис индукции. Поскольку при n=1 каждая функция является 1-1-функцией, то, как и в предыдущей теореме, число таких функций равно m, т.е. Am1=m.

Шаг индукции. Предположим, что при n=k выполнено равенство Amk=m(m-1)... (m-k+1). Докажем, что тогда Amk+1=m(m-1)... (m-k+1)(m-k).

Действительно, как и в предыдущей теореме, каждая 1-1-функция f: X -> Y является расширением некоторой 1-1-функции f':X' -> Y значением f(x{k+1}) ( напомним, что X'= X \ {x k+1} ). При этом в качестве этого значения можно взять любой элемент Y, не являющийся значением f', т.е. любой элемент из множества Y \ {f(x1),... , f(xk)}. При k < m таких элементов (m-k). Тогда каждую 1-1-функцию f':X' -> Y можно расширить (m-k) способами и, следовательно, Amk+1 =Amk (m-k). При k >= m 1-1-функций f: X -> Y не существует (почему?) и Amk+1=0, но в этом случае доказываемая формула также справедлива, поскольку один из сомножителей в ней равен 0.

В качестве простого следствия теоремы 2.2 получаем формулу для числа перестановок.

Теорема 2.3. Если |X| = n , то число всех перестановок f: X -> X равно n!

Число всех k -элементных подмножеств n -элементного множества обозначим через Cnk (часто используется также обозначение $${n \choose k} $$ ).

Это число называется числом сочетаний из n по k.

Теорема 2.4. При n >= k >= 0

$$C_n^k = A_n^k/ k! = \frac{ n!}{k! (n-k)!}$$

Доказательство. При n=k=0 у пустого множества имеется одно (пустое) подмножество. Поэтому $$C_0^0 = 1 = \frac{ 0!}{0! 0!}$$ (напомним, что по обычному соглашению 0!=1 ).

Пусть |Y| = n>= 1. Каждая 1-1-функция f: {1,... ,k} -> Y определяет k -элементное подмножество $$\rho _{f} =\{ y_{i} | f(i)=y_{i},\ i=1,\dots , k\} \subseteq Y$$. При этом одно и тоже такое подмножество получается при любой перестановке элементов $$\rho _{f}$$. Всего таких перестановок k! (по теореме 2.3), а 1-1-функций f: {1,... ,k} -> Y - Ank. Отсюда, используя теорему 2.2, получаем, что

$$C_n^k = A_n^k/ k!= \frac{n(n-1)\ldots (n-k+1)}{k!}= \frac{ n!}{k! (n-k)!}$$

Непосредственным следствием этой теоремы является свойство "симметричности" сочетаний: Cnk =Cnn-k, а также рекурентная формула Cnk = Cn-1k + Cn-1k-1, позволяющая организовать их эффективное вычисление путем последовательного получения элементов треугольника Паскаля:

$$$$\begin{array}{ccccccccc} 1 \\ 1 1 \\ 1 2 1 \\ 1 3 3 1 \\ 1 4 6 4 1 \\ \end{array} $$ \centerline{ .\ .\ . \ . \ .\ . \ . \ .\ . \ . \ . \ .\ . \ . \ .\ . \ . } $$

В n -ой строке этого треугольника стоят числа Cn0, Cn1, ..., Cnk, ... , Cnn и каждое из них является суммой двух стоящих над ним чисел предыдущей строки. Эти числа называются биномиальными коэффициентами, так как входят в формулу бинома Ньютона, выражающую n -ую степень бинома x+y :

$$(x+y)^n = \sum_{ k=0}^n C_n^k x^ky^{n-k}.$$

Справедливость этой формулы следует из того, что коэффициент при xkyn-k равен числу способов, которыми из n сомножителей (x+y)(x+y)... (x+y) можно выбрать k сомножителей.

Укажем несколько простых следствий этой формулы. Положив в ней x=1, y=1 , получаем:

$$\sum_{ k=0}^n C_n^k =2^n.$$

Так как сумма слева определяет число всех подмножеств n -элементного множества, то это еще одно доказательство следствия 2.1.1.

При x=1, y=-1 бином Ньютона дает равенство числа подмножеств четной и нечетной мощности:

$$\sum_{ k=0}^{[n/2]} C_n^{2k} =\sum_{ k=0}^{[n/2]} C_n^{2k+1}.$$