![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Метод математической индукции.
Заметим, что метод математической индукции достаточно широко используется в математике. В линейной алгебре этот метод особенно эффективен, так как алгебраические конструкции очень часто используют параметр последовательности Приведённая ниже теорема устанавливает правило доказательства утверждений, учитывающих параметр
► Допустим противное: найдётся такое Но, в соответствии с теоремой, мы получали: Рассмотрим несколько примеров, иллюстрирующих применение метода математической индукции. ☺ ☺ Пример 1 – 01: Пусть имеем последовательность: 1, 2, ..., Решение: 1). Проверим условие: для 2). Пусть 3). Тогда утверждение (формула) верно для всех Ответ: выражение для утверждения Пример 1 – 02: Пусть имеем последовательность: 1, 2, 4,..., Решение: 1). Учитывая что 2). Пусть 3). Тогда утверждение (формула) верно для всех Ответ: выражение для утверждения Пример 1 – 03: Пусть имеем последовательность: 12, 22,..., Решение: 1). Проверяем при 2). Пусть 3). Тогда утверждение (формула) верно для всех Ответ: выражение для утверждения ••• ≡ ••• Пример 1 – 1.3: Методом математической индукции доказать, что при любом натуральном Решение: 1). Проверим равенство при значении 2). Пусть для некоторого значения 3). Результат: формула Ответ: доказано! Пример 2 – 1.6: Методом математической индукции доказать, что при любом натуральном Решение: 1). Проверим равенство при значении 2). Пусть для некоторого значения 3). Результат: формула Ответ: доказано! Пример 3 – 1.29: Методом математической индукции доказать, что при любом натуральном Решение: 1). Проверим равенство при значении 2). Пусть для некоторого значения 3). Результат: формула Ответ: доказано! Пример 4 – 1.33: Методом математической индукции доказать, что при любом натуральном Решение: 1). Проверим неравенство 2). Пусть для некоторого значения 3). Применяя тождественные преобразования к неравенству (2), получим: 4). Результат: неравенство в виде формулы Ответ: доказано! Пример 5 – 1.39: Методом математической индукции доказать, что при любом натуральном Решение: 1). Проверим утверждение при значении 2). Пусть для некоторого значения 3). Результат: утверждение верно для любого натурального Ответ: доказано! Элементы комбинаторики. В практической деятельности различных специалистов часто возникают задачи, в которых рассматриваются те или иные комбинации букв, цифр, каких-то других объектов. Возникает вопрос: сколько комбинаций, отвечающих определённым условиям, можно в этих случаях составить? В общем виде можно поставить вопрос шире: имеем множество M некоторых элементов, и из него требуется выделить подмножества ▫ важен порядок следования элементов; ▫ порядок следования элементов неважен. Бывает важно знать сколькими способами можно из множества M элементов выделить подмножества с определёнными свойствами. Область математики, в которой изучаются способы подсчёта различных комбинаций, удовлетворяющих заданным условиям, из заданных объектов, называется комбинаторикой. Первые проявления комбинаторики относят к 16 веку: итальянский математик Тарталья первый занялся подсчётом числа различных комбинаций при игре в кости. В дальнейшем развитии этой науки принимали участие Яков Бернулли, Лейбниц, Эйлер. Но и их разработки в основном относились к азартным играм. Сегодня комбинаторика бурно развивается и в теории, и в приложениях. При изучении разделов высшей алгебры часто приходится обращаться к комбинаторике: использовать такие понятия, как размещения, перестановки, сочетания! Весёлая задача. Любители-велосипедисты организовали клуб. Каждому члену клуба выдали членский билет. Председателю достался билет с номером 008. Через некоторое время председатель обратил внимание на то, что на колёсах его велосипеда часто появляются восьмёрки! Так как колесо с восьмёркой очень похоже на цифру 8, то председателю это показалось подозрительным! Подозрение распространилось и на 0, так на велосипеде с колесом, похожим на 0, тоже далеко не уедешь! Чтобы защититься от нечистой, председатель решил заменить билеты так, чтобы эти плохие цифры не портили колёса! Оказалось, что билетов с трёхзначными номерами без 0 и 8 ровно столько, как и членов клуба! Сколько было велосипедистов в этом клубе? Решение задачи. В рассмотренной задаче: имеем множество цифр M ={1, 2, 3, 4, 5, 6, 7, 9}. Из этого множества выбираем три подмножества Так как свойства элементов множества M для нас безразличны, то достаточно знать только их количество – восемь. Каждое место трёхзначного номера билета цифры множества M могут заполнять восьмью вариантами. В таком случае всего вариантов заполнения номера билета N= 83 =512. Столько было членов этого клуба! Ответ: N= 83 =512. Рассмотренная задача относится к определённому типу задач комбинаторики. Построим её формальную модель, принимая, что индивидуальные свойства объектов множества M для нас несущественны. Это значит, что в качестве объектов множества M можно принять: {1, 2,..., n}. Из элементов этого множества составляют Для наглядности будем считать, что для элементов подмножества выделено место заполнения. Рассмотрим случай, когда в место под номером [ 1 ] можно поместить любой из элементов множества {1, 2,..., n}. В этом случае число вариантов заполнения места [ 1 ] равно ☺ ☺ Пример 1 – 04: Догадаться, почему азбука Морзе, составленная из точек: Решение: 1). Так как индивидуальные свойства знаков 2). Тогда при помощи четырёх знаков можно передать только 24 =16 букв! Но в русском алфавите 32 буквы, а ещё есть цифры и знаки препинания!.. Это значит, что не хватит и совокупности кодов с одним знаком, двумя, тремя, четырьмя знаками, так как суммарное количество символов, передаваемых с их помощью N ≤ 21 +22 +23 +24 = 30. 3). А вот с добавлением пяти знаков можно передавать 30 +25 = 62 символа. Ответ: доказано, см. текст! Пример 1 – 05: На флоте применяют морской семафор флажками. Большинство букв сигнальщик передаёт, располагая оба флажка по разные стороны от тела. А вот при передаче букв: {Б, Д, К, Х, Ю, Я} оба флажка располагаются по одну сторону. Почему сделано такое исключение? Решение: 1). Для каждой руки сигнальщика хорошо различимы 5 положений: -900, -450, 00, 450, 900. Это значит множество, что множество объектов можно отобразить как {1, 2, 3, 4, 5}. 2). Это значит, двумя руками сигнальщик может передать 52 =25 символов. Ещё следует учесть, что для разделения слов используют положение оба флажка вниз! Остаётся 24 комбинации. 3). Принятые для букв {Б, Д, К, Х, Ю, Я} положения флажков позволяют передать 30 символов. А где ещё два? Оказывается, буквы Е, Ё, Э передают одинаково (их легко воспринимают по смыслу передаваемых слов и предложений)! Ответ: ответ обоснован, см. текст! ☻ Пусть теперь из множества M ={1, 2,..., n} составляют всевозможные расстановки
В этом случае число вариантов заполнения места [ 1 ] равно Если мест заполнения k=n, то размещения без повторений из n по n называют n-перестановками и обозначают Если из размещений Часто бывает полезно знать свойства сочетаний 1*: 2*:
☺ ☺ Пример 1 – 06: В группе 25 студентов. Надо избрать: старосту, профорга, физорга, культорга и ответственного по успеваемости. Сколькими способами можно выбрать названных лидеров, если каждый может исполнять только одну обязанность? Решение: 1). В этом случае мы имеем задачу размещений без повторений из n =25 по k =5, то есть необходимо вычислить число: 2). В результате имеем: Ответ: Пример 1 – 07: Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг? Решение: 1). Если бы девушки становились не в круг, а в шеренгу, то различных способов было бы столько, сколько перестановок из 7 по 7, то есть 2). Так как девушки становятся в круг для хоровода, то шеренга девушек имеет возможность вращаться. Это значит, что каждая перестановка девушек, не меняясь, может занимать 7 положений на круге. В таком случае для ответа на поставленный вопрос требуется разделить Ответ: N=720. Пример 1 – 08: В урне находятся 25 белых шаров с номерами {1, 2,..., 25}. Сколькими различными способами можно вынуть из урны 5 шаров? Решение: 1). Очевидно, для нас неважен порядок номеров на вынутых шарах: номера должны быть разными. Тогда мы имеем случай применения k-сочетания: 2). В нашем случае: Ответ: N=720. ☻ Бином Ньютона. Этот параграф интересен не только том, что мы сможем увидеть ещё одно симпатичное применение результатов комбинаторики. Мы исправим несправедливость забвения бинома Ньютона в школах России! Бином Ньютона – это формула: Нестрогое доказательство: 1) Запишем 2) При фиксированном значении k слагаемых вида: Формальное (алгебраическое) доказательство: 1) Воспользуемся методом математической индукции. Учтём известные всем формулы:
2) Видим, при n утверждение (формула)
или, раскрывая скобки и приводя подобные:
или, учитывая свойства сочетаний:
3). Формула верна для любого n. ☺ ☺ Пример 1 – 09: Получить общую формулу для разложения: Решение: 1). Воспользуемся общей формулой: 2). В результате имеем: Ответ: Пример 1 – 10: Найти коэффициент при x3 в разложении Решение: 1). Воспользуемся разложением: 2). Вычислим нужный коэффициент (учитывая свойство сочетаний):
Ответ: 7680. Пример 1 – 11: Найти коэффициент при x11 в разложении Решение: 1). Запишем общий член разложения: 2). Используя исходные данные примера, запишем равенство: 3). Воспользуемся общим членом разложения для k=6 и вычислим: Ответ: 2268. •• ☻ ☻ ••
Вопросы для самопроверки: 1. Что такое метод математической индукции? 2. Как применяют метод математической индукции? 3. Что такое комбинаторика? 4. Определение числа размещений из 5. Формула для вычисления числа сочетаний из 6. Бином Ньютона. Общая формула разложения. Треугольник Паскаля. Задачи для самоподготовки: Пример C1 – 1: Методом математической индукции доказать, что при любом натуральном Пример C1 – 2: Методом математической индукции доказать, что при любом натуральном Пример C1 –3: Методом математической индукции доказать, что при любом натуральном Пример C1 – 4: Методом математической индукции доказать, что при любом натуральном Пример C1 – 5: Методом математической индукции доказать, что при любом натуральном Пример C1 – 6: Методом математической индукции доказать, что при любом натуральном
•• ☻ ☻ •• Популярное:
|
Последнее изменение этой страницы: 2016-03-16; Просмотров: 1878; Нарушение авторского права страницы