- •Раздел I. Основы теории множеств. Системы счисления. Комбинаторика
- •Глава 1. Множества, операции с ними. Алгебра множеств
- •1.1. Элементы и множества
- •1.2. Отображения, функции, предикаты
- •1.3. Метод математической индукции
- •1.4. Способы задания множеств
- •Перечисление
- •Задание с помощью логических функций (предикатов)
- •1.5. Предметные операции на множествах. Формула множества
- •1.6. Операции сравнения — логические операции с множествами
- •1.7. Алгебра множеств. Ее формулы, теоремы и законы
- •Глава 2. Мощность множеств
- •2.1. Мощность. Счетные множества
- •2.2. Множества мощности континуум
- •Глава 3. Бинарные отношения на множествах
- •3.1. Определение и способы задания отношений
- •3.1.1. Перечисление (список пар)
- •3.1.2. Матрица
- •3.1.3. Задание отношений при помощи предикатов
- •3.2. Аксиомы на отношениях
- •3.3. Основные типы отношений
- •3.3.1. Отношение эквивалентности
- •3.3.2. Отношение нестрогого (частичного) порядка
- •3.3.3. Отношение строгого порядка
- •3.4. Проверка типов отношений. Решение задач
- •Контрольные задания по теме
- •I. Общая теория множеств
- •Глава 4. Системы счисления
- •4.1. Позиционные системы счисления с постоянными основаниями. Представления целых чисел Рассмотрим общие правила представления количественных величин в позиционных системах счисления.
- •4.2. Переводы целых чисел в позиционных системах счисления
- •4.2.1. Перевод целых чисел из произвольной системы с постоянным основанием р 10 в десятичную систему
- •4.2.2. Перевод целых чисел из десятичной системы счисления в системы с произвольными постоянными основаниями p 10
- •4.2.5. Представление двоичной байтовой информации в шестнадцатеричной и десятичной системах
- •4.3. Дробные и смешанные числа в позиционных системах счисления с постоянными основаниями
- •4.3.1 Перевод правильных десятичных дробей в систему счисления с иным основанием p 10
- •4.3.2 Перевод правильных дробей из системы с основанием p 10 в десятичную систему счисления
- •4.4. Арифметические действия с целыми числами в системах с произвольными основаниями. Их компьютерное представление
- •4.4.1 Сложение
- •4.4.2 Вычитание
- •4.4.3. Прямой и дополнительный коды целых чисел. Их представление в памяти компьютера, сложение и вычитание
- •4.5. Двоичные (булевы) векторы
- •4.6. Смешанные позиционные системы счисления. Факториальная система
- •4.6.1. Перевод целых чисел из десятичной системы в смешанную с основаниями р0, р1, ... , рk
- •Глава 5. Комбинаторика
- •5.1. Основная задача комбинаторики. Характеристики комбинаторных задач
- •5.2. Основные правила подсчета чисел комбинаторных множеств
- •5.2.1. Правило сложения
- •5.2.2. Формула включений-исключений
- •5.2.3. Правило умножения
- •5.2.4. Правило учета сходства и различия
- •5.3. Размещения (размещения с повторениями)
- •5.4. Перестановки и размещения без повторений различных объектов. Упорядоченность перестановок
- •5.5. Перестановки и размещения без повторений групп одинаковых объектов
- •5.6. Сочетания
- •5.7. Понятие вероятности
- •Контрольные задания по теме
- •II. Системы счисления. Комбинаторика
1.3. Метод математической индукции
Допустим, необходимо доказать справедливость бесконечной последовательности утверждений Р(n), зависящих от натуральной переменной n. Метод математической индукции — один из способов доказательства. Он заключается в следующем.
1. Вначале доказывают справедливость Р(n) при n=1 (базис индукции).
2. Затем доказывают, что из истинности Р(k) для любого натурального числа k следует истинность и Р(k+1) (индуктивный переход).
Если оба пункта доказаны, то утверждение Р(n) истинно для всех натуральных чисел. В тех случаях, когда доказывается справедливость Р(n) для всех n n0 >1, базис индукции доказывают при n = n0 .
Пример 1. Докажем методом математической индукции равенство 1+3+5+…+(2n-1)=n2.
Решение.
Базис индукции. n=1: 1=1 — равенство выполняется.
Индуктивный переход. Покажем, что из справедливости равенства для любого натурального числа k следует его истинность для (k+1) (индуктивный переход).
1 + 3 + 5 +…+ (2k–1) + (2(k+1) – 1) = k2 + (2(k+1) – 1) = k2 + 2k + 1 = (k+1)2.
Следовательно, по теореме о методе математической индукции равенство справедливо для всех натуральных чисел, что и требовалось доказать.
Пример 2. Докажем методом математической индукции неравенство logn 2 > 1/ n при n >1.
Решение. Для упрощения доказательства перейдем к следующему равносильному неравенству: 2n>n. Его получим, умножая обе части на n и возводя n в степени, стоящие в левой и правой частях.
Базис индукции. n=2: 4>2 — неравенство выполняется.
Индуктивный переход. Покажем, что из 2k > k для любого натурального числа k следует: 2(k+1) > k+1.
2(k+1) = 2 2k > 2 k ((k +1)/k) k = k +1.
Справедливость переходов следует из индуктивного допущения 2k>k и неравенства 2 ((k+1)/k), верного для всех натуральных k (так как при k 1 выполняется: 2 k k+1).
По теореме получим, что рассмотренное неравенство справедливо для всех натуральных чисел, больших 1, что и требовалось доказать.
Пример 3. Докажем методом математической индукции, что выражение 1+32n-1 при всех натуральных n делится нацело (без остатка) на 4.
Решение.
Базис индукции. n=1:1+32-1= 4 — делится нацело на 4.
Индуктивный переход. Покажем, что если 1+32k–1 для любого натурального числа k делится нацело на 4, то и 1+32(k+1)–1 делится нацело на 4 .
1 + 32(k+1) –1 = 1 + 32(k+1) -1– (1 + 32k–1) + 1 + 32k–1 = (32(k+1)–1 – 32k–1 ) + 1 + 32k–1 = 32k-1 (32 – 1) +1 + 32k–1 = 32k–1 8 +1 + 32k–1.
Число 1+32(k+1)–1 представлено в виде суммы двух слагаемых. Первое делится на 4 нацело по индуктивному допущению, второе содержит множитель 8. Следовательно, сумма также делится на 4. Индуктивный переход доказан.
По теореме получаем справедливость свойства для всех натуральных чисел, что и требовалось доказать.
ЗАДАЧИ
Доказать по методу математической индукции справедливость для натуральных n следующих соотношений:
1) 12 + 22 +…+ n2 = n(n+1)(2n+1)/6,
2) 13+ 23 +…+ n 3 = (1+ 2 +…+ n)2,
3) 72n–1+ 6 2n–1 + 1 кратно 14,
4) 22n–1+ 32n–1 + 1 кратно 6,
5) 25n – 52n кратно 7,
6) 1+ q +…+ qn = (1–qn+1)/(1–q) при q 1.