Сборник задач по курсу «Теория вычислительных процессов» (стр. 2 )

Но здесь то же число п камешков и, следовательно, все они одного цвета. Отсюда следует, что и (п + 1) камешков будут одного цвета, т. к. известно, что камешки

одного цвета, а (п + 1)-й камешек того же цвета, что и п-й (даже больше, его цвет совпадает с цветом второго, третьего и т. д.). Отсюда и следует справедливость нашего утверждения.

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

Принцип строгой индукции

Пусть S(n) – некоторое высказывание о целом числе n и требуется доказать, что S(n) справедливо для всех положи­тельных n. Для этого необходимо:

1) доказать, что справедливо S(1);

2) доказать, что если справедливы S(1), S(2), S(3), ..., S(n) для всех положительных n, то справедливо и S(n + 1).

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

Пример 1.2. Рассмотрим последовательность чисел, называемых числами Фибоначчи. В нее входят  f0 = 0,  f1 = 1,  f2 = 1,  f3 = 2, ,  f4 = 3,  f5 = 5,  f6 = 8, ... , где (n + 1)-е число Фибоначчи определяется как  fn + 1= fn + fn – 1 (для n ≥ 1). Пусть  α = (1 +)/2 и требуется доказать, что  fn ≤ αn – 1 для любого неотрицательного числа α. Для доказательства используем метод строгой индукции по n. Так как доказывается высказывание о неотрицательных числах, а принцип индукции сформулирован для положительных, используем очевидную модификацию метода.

1. Для n = 0 необходимо показать, что f0 ≤ α0 – 1 . Это справедливо, так как f0 = 0 = α–1. Необходимо рассмотреть особый случай, когда n = 1. Здесь мы имеем  f1 = 1 ≤ 1=α0 = α1–1.

2. Предположим, что fm ≤ αm – 1 справедливо для всех неотрицательных целых чисел  m = 0, 1, 2,  ... , n. Нужно показать, что fn+1 ≤ α(n + 1) – 1 также справедливо. По гипотезе индукции fn ≤ αn – 1  и  fn–1 ≤ α(n – 1) – 1. Поэтому

fn + 1 = fn + fn – 1  ≤αn – 1 + αn – 2 = αn – 2 ⋅ (α+1).

Обратите внимание, что

α2 = α + 1.

Фактически мы так и выбирали  α, чтобы выполнялось условие  α + 1 = α2. Поэтому мы получаем

fn + 1 = fn + fn – 1 ≤ αn – 2 ⋅ (α+1) = αn – 2 ⋅ α2 = αn = α(n + 1) – 1 .

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

Отметим, что необходимо было знать, что и  fn, и  fn–1  удовлетворяют гипотезе индукции. Только в этом случае доказательство возможно. Одного только знания о справедливости высказывания для fn недостаточно. Таким образом, строгая индукция нам необходима по существу. Отметим также, что в данном частном случае нам потребовалось доказывать, что  f0 ≤ α0 и f1 ≤ α1; мы не можем записать f1 как f0 + f–1 ,  так как  f–1  не существует.

Упражнения

9. Простым числом называется положительное число, делящееся без остатка только на 1 и на само себя. Попытаться доказать самостоятельно, что каждое положительное число n можно представить в виде произведения одного и более простых чисел, используя строгую индукцию по n. (Подробное решение этой задачи приведено в [2], [3].)

10. Изменить приведенный в данном разделе принцип индукции для доказательства справедливости высказывания  S(n)  для целых чисел n, удовлетворяющих условию n ≥ n0, а не только для любых положительных целых чисел.

11. Используя простую индукцию, докажите справедливость следующих формул:

а) для всех неотрицательных целых n;

б) для любого положительного числа n;

в) всех неотрицательных целых чисел n.

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

а) , где для любого положительного α;

б) всех неотрицательных n.

13. Найдите ошибку в следующем доказательстве. Мы хотим доказать, что α n – 1 = 1 для любого положительного числа n. Используем строгую индукцию:

1. Для п = 1 эта формула справедлива, так как α n – 1 = α 1 – 1 = α 0 = 1.

2. Предположим, что высказывание справедливо для 1, 2, 3, ..., п, т. е. α 0 = 1, α 1 = 1, α 2 = 1, α n – 1 = 1. Нужно показать, что α (n +1) – 1 = 1:

α (n +1) – 1 = α n = α 1 · α n – 1 = 1 · 1 = 1.

(По гипотезе индукции)

14. Сформулируйте два варианта строгой индукции, которые можно использовать для доказательства справедливости S (п) при п, удовлетворя­ющих условию n0 ≤ n ≤ m0. Мы будем ссылаться на эти варианты как на строгую восходящую и строгую нисходящую индукцию. Соответствующие версии простой индукции рассмотрены выше.

Задания повышенной сложности

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

Определение. Говорят, что бинарное отношение < вполне упорядочивает множество X, или множество вполне упорядочено, если отношение < обладает следующими свойствами:

1) если x, y, z принадлежат X, а х < у и у < z, то х < z;

2) для х и у из X справедлива одна и только одна из трех возможностей: либо х < у, либо у < х,  либо х = у;

3) если А – любое непустое подмножество X, то в А существует некоторый элемент х, такой, что х ≤ у для любого у, принадлежащего А. Другими словами, любое непустое подмножество X содержит «наименьший элемент».

Отметим, что это определение касается обобщения структуры положительных (неотрицательных) целых чисел. Множество положительных целых чисел вполне упорядочено относительно обычного отношения <.

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

Принцип обобщенной индукции

Пусть X – вполне упорядоченное относительно < множество, а S(х) – некоторое высказывание, касающееся элемента х из X. Если требуется доказать справедливость S(х) для всех х, принадлежащих X, то необходимо:

1) доказать, что справедливо S(х0), где х0 – наименьший элемент в X;

2) доказать для всех х в X, удовлетворяющих условию х0 < х, что если справедливо S (у) для всех  у < х, то справедливо и S(х).

Отметим, что если X – множество положительных целых чисел, а отношение < имеет обычный смысл, то принцип обобщенной индукции идентичен принципу строгой индукции.

Пример 1.3. Рассмотрим последовательность чисел, определенную следу­ющим образом: S0, 0 = 0, а для любой другой пары неотрицательных чисел m, n

Например, первые элементы этой последовательности:

S0, 0 = 0, S1, 0 = S0, 0 + 1 = 0 + 1 = 1,

S0, 1 = S0, 0 + 1 = 1, S1, 1 = S1, 0 + 1 = 1 + 1 = 2,

S2, 0 = S1, 0 + 1 = 2, S2, 1 = S2, 0 + 1 = 3, ... .

Нужно доказать, что  Sm, n = m + n  для любых неотрицательных целых m, n. Используем принцип обобщенной индукции на множестве X упорядоченных пар неотрицательных целых чисел. Множество упорядочено на основе лексикографического порядка, описанного в примере 3. Чтобы доказать справедливость Sm, n = m + n для любых < m, n > в X, необходимо:

1. Доказать, что Sm, n = m + n справедливо, если < m, n > – наименьший элемент в X. Но так как наименьший элемент – пара < 0, 0 >, то нужно показать, что S0, 0 = 0 + 0 = 0. Это очевидно по определению S0, 0.

2. Доказать, что если Sm’, n’ = m’ + n’ справедливо для любых пар < m’, n’ > < < m, n >, то справедливо и Sm, n = m + n для любых< 0, 0 > < < m, n > в X. Предположим, что формула
Sm’, n’ = m’ + n’ верна для < m’, n’ > < < m, n >. Это гипотеза индукции. Нужно показать, что
Sm, n = m + n. Существует две возмо­жности: либо n = 0, либо n ≠ 0. Если n = 0, то по определению Sm, n = Sm–1, n + 1. Однако < m–1, n > < < m, n >, и, следовательно, по нашей гипотезе
Sm–1, n = (m – 1) + n. Поэтому Sm, n = Sm–1, n + 1 = (m – 1 + n) + 1 = m + n. Если n ≠ 0, то
Sm, n = Sm, n–1 + 1 по определению. Но < m, n–1 > < < m, n > и по гипотезе Sm, n–1 =
= m + (n – 1). Следовательно, в этом случае Sm, n = Sm, n–1 + 1 = (m + n – 1) + 1 =
= m + n, что и требовалось доказать.

Упражнения

15. Множество всех упорядоченных пар неотрицательных целых чисел вполне упорядочено с помощью отношения лексикографического порядка <. Это отношение можно определить так: отношение (n1, n2) < (n3, n4) справедливо, если и только если (n1 < n3) или (n1 = n3  и  n1 < n4). В качестве упражнения покажите, что такое отношение обеспечивает нужную упорядоченность.

16. Рассмотрим последовательность чисел, определяемую следующим образом:

s1, 1 = 5,

а для любой пары положительных чисел m, n, кроме пары 1, 1,