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

⇐ ПредыдущаяСтр 2 из 4Следующая ⇒

Заметим, что метод математической индукции достаточно широко используется в математике. В линейной алгебре этот метод особенно эффективен, так как алгебраические конструкции очень часто используют параметр последовательности .

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

Теорема: (1.1)

Пусть

и для всякого

имеется высказывание (утверждение) –

, причём известно, что: 1) при значении параметра

высказывание

верно; 2) для всякого

: если из допущения

= (верно) →

= (верно). Тогда высказывание верно для всех натуральных чисел

► Допустим противное: найдётся такое , для которого утверждение неверно. Но, тогда утверждение = (верно).

Но, в соответствии с теоремой, мы получали: = (верно) → = (верно). Полученное противоречие означает: теорема доказана! ◄

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

☺ ☺

Пример 1 – 01: Пусть имеем последовательность: 1, 2, ..., . Если =1+2+... + , то (утверждение): = верно для любого .

Решение:

1). Проверим условие: для =1 имеем = =1 → высказывание верно.

2). Пусть верно. Проверим: = +( +1)= → для ( +1) высказывание также верно.

3). Тогда утверждение (формула) верно для всех .

Ответ: выражение для утверждения есть формула суммы чисел: 1+2+... + .

Пример 1 – 02: Пусть имеем последовательность: 1, 2, 4,..., . Если =1+2+...+ , то (утверждение): = -1 верно для любого .

Решение:

1). Учитывая что , видим: при =1 имеем =1 → высказывание верно.

2). Пусть верно. Проверим: = + = -1+ = -1 → для ( +1) высказывание также верно.

3). Тогда утверждение (формула) верно для всех .

Ответ: выражение для утверждения есть формула суммы чисел: 1+2+...+ .

Пример 1 – 03: Пусть имеем последовательность: 1², 2²,..., . Если =1²+2²+...+ , то (утверждение): = верно для любого .

Решение:

1). Проверяем при =1: =1 = → высказывание верно.

2). Пусть верно. Проверим: = +( +1)²=( +1) . После несложных преобразований: = → для ( +1) высказывание также верно.

3). Тогда утверждение (формула) верно для всех .

Ответ: выражение для утверждения есть формула суммы чисел: 1+2+...+ .

••• ≡ •••

Пример 1 – 1.3: Методом математической индукции доказать, что при любом натуральном верно равенство: = = . (1)

Решение:

1). Проверим равенство при значении : = = =2 – верно!

2). Пусть для некоторого значения верно равенство . Покажем, что будет верно также равенство . Запишем: = + . Применяя к последнему тождественные преобразования, получим: = = . Это значит, что выражение для равенства может быть получено из равенства формальной заменой параметра значением .

3). Результат: формула верна для любого натурального .

Ответ: доказано!

Пример 2 – 1.6: Методом математической индукции доказать, что при любом натуральном верно равенство: = = . (1)

Решение:

1). Проверим равенство при значении : = = = – верно!

3). Результат: формула верна для любого натурального .

Ответ: доказано!

Пример 3 – 1.29: Методом математической индукции доказать, что при любом натуральном верно равенство: = = . (1)

Решение:

1). Проверим равенство при значении : = = =1 – верно!

3). Результат: формула верна для любого натурального .

Ответ: доказано!

Пример 4 – 1.33: Методом математической индукции доказать, что при любом натуральном верно неравенство : < , . (1)

Решение:

1). Проверим неравенство при значении , то есть < . Применяя тождественные преобразования, получим: , или – верно!

2). Пусть для некоторого значения верно неравенство . Покажем, что будет верно также неравенство : < . Используя неравенство , запишем последнее в виде: ∙ < . (2)

3). Применяя тождественные преобразования к неравенству (2), получим: – верно! Это значит, что верно и неравенство , то есть выражение для неравенства может быть получено из неравенства формальной заменой параметра значением .

4). Результат: неравенство в виде формулы верно для любого натурального .

Ответ: доказано!

Пример 5 – 1.39: Методом математической индукции доказать, что при любом натуральном число, записанное в виде: , делится на 7. (1)

Решение:

1). Проверим утверждение при значении : = =7 – утверждение верно!

2). Пусть для некоторого значения верно утверждение , то есть число , делится на число 7. Покажем, что: = также делится на 7. Применяя к последнему формулу бинома Ньютона для случая, когда показатель степени бинома равен 7 и тождественные преобразования, получим: = . Так как каждое из чисел делится на число 7, то можно записать: = + . Но число также делится на число 7 (по предположению). Это значит, что выражение также делится на число 7.

3). Результат: утверждение верно для любого натурального .

Ответ: доказано!

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

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

В общем виде можно поставить вопрос шире: имеем множество M некоторых элементов, и из него требуется выделить подмножества , удовлетворяющие некоторым условиям. Различают подмножества, в которых:

▫ важен порядок следования элементов;

▫ порядок следования элементов неважен.

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

Первые проявления комбинаторики относят к 16 веку: итальянский математик Тарталья первый занялся подсчётом числа различных комбинаций при игре в кости. В дальнейшем развитии этой науки принимали участие Яков Бернулли, Лейбниц, Эйлер. Но и их разработки в основном относились к азартным играм.

Сегодня комбинаторика бурно развивается и в теории, и в приложениях. При изучении разделов высшей алгебры часто приходится обращаться к комбинаторике: использовать такие понятия, как размещения, перестановки, сочетания!

Весёлая задача.

Любители-велосипедисты организовали клуб. Каждому члену клуба выдали членский билет. Председателю достался билет с номером 008. Через некоторое время председатель обратил внимание на то, что на колёсах его велосипеда часто появляются восьмёрки! Так как колесо с восьмёркой очень похоже на цифру 8, то председателю это показалось подозрительным! Подозрение распространилось и на 0, так на велосипеде с колесом, похожим на 0, тоже далеко не уедешь! Чтобы защититься от нечистой, председатель решил заменить билеты так, чтобы эти плохие цифры не портили колёса!

Оказалось, что билетов с трёхзначными номерами без 0 и 8 ровно столько, как и членов клуба! Сколько было велосипедистов в этом клубе?

Решение задачи.

В рассмотренной задаче: имеем множество цифр M ={1, 2, 3, 4, 5, 6, 7, 9}. Из этого множества выбираем три подмножества , , со свойствами: формировать соответствующие разряды трёхместного кода.

Так как свойства элементов множества M для нас безразличны, то достаточно знать только их количество – восемь. Каждое место трёхзначного номера билета цифры множества M могут заполнять восьмью вариантами. В таком случае всего вариантов заполнения номера билета N= 8³=512. Столько было членов этого клуба!

Ответ: N= 8³=512.

Рассмотренная задача относится к определённому типу задач комбинаторики. Построим её формальную модель, принимая, что индивидуальные свойства объектов множества M для нас несущественны. Это значит, что в качестве объектов множества M можно принять: {1, 2,..., n}. Из элементов этого множества составляют всевозможных подмножеств, в каждом из которых используется по элементов.

Для наглядности будем считать, что для элементов подмножества выделено место заполнения. Рассмотрим случай, когда в место под номером [ 1 ] можно поместить любой из элементов множества {1, 2,..., n}. В этом случае число вариантов заполнения места [ 1 ] равно . Если и все остальные места заполнения используют по одному элементу из множества {1, 2,..., n}, то число вариантов заполнения совокупности мест: [ 1 ], [ 2 ], ..., [ k ] равно N= = . Такие расстановки называют k-расстановками с повторениями из элементов n видов.

☺ ☺

Пример 1 – 04: Догадаться, почему азбука Морзе, составленная из точек: и тире , имеет коды с одним знаком, двумя, тремя, четырьмя и пятью. А нельзя ли обойтись меньшим числом знаков, например, четырьмя?

Решение:

1). Так как индивидуальные свойства знаков и не имеют значения, то примем исходное множество в виде {1, 2}.

2). Тогда при помощи четырёх знаков можно передать только 2⁴ =16 букв! Но в русском алфавите 32 буквы, а ещё есть цифры и знаки препинания!.. Это значит, что не хватит и совокупности кодов с одним знаком, двумя, тремя, четырьмя знаками, так как суммарное количество символов, передаваемых с их помощью N ≤ 2¹+2²+2³+2⁴= 30.

3). А вот с добавлением пяти знаков можно передавать 30 +2⁵= 62 символа.

Ответ: доказано, см. текст!

Пример 1 – 05: На флоте применяют морской семафор флажками. Большинство букв сигнальщик передаёт, располагая оба флажка по разные стороны от тела. А вот при передаче букв: {Б, Д, К, Х, Ю, Я} оба флажка располагаются по одну сторону. Почему сделано такое исключение?

Решение:

1). Для каждой руки сигнальщика хорошо различимы 5 положений: -90⁰, -45⁰, 0⁰, 45⁰, 90⁰. Это значит множество, что множество объектов можно отобразить как {1, 2, 3, 4, 5}.

2). Это значит, двумя руками сигнальщик может передать 5²=25 символов. Ещё следует учесть, что для разделения слов используют положение оба флажка вниз! Остаётся 24 комбинации.

3). Принятые для букв {Б, Д, К, Х, Ю, Я} положения флажков позволяют передать 30 символов. А где ещё два? Оказывается, буквы Е, Ё, Э передают одинаково (их легко воспринимают по смыслу передаваемых слов и предложений)!

Ответ: ответ обоснован, см. текст!

☻

Пусть теперь из множества M ={1, 2,..., n} составляют всевозможные расстановки подмножеств так, что использованное для заполнения места с номером [ 1 ] число удаляется из множества M, то есть их остаётся в множестве на 1 меньше. После заполнения места с номером [ 2 ] в множестве чисел M содержится уже на 2 элемента меньше, и так далее...

В этом случае число вариантов заполнения места [ 1 ] равно ; места [ 2 ] → (n–1); места [ 3 ] → (n–2); и так далее: места [ k ] → (n–k+1). Такие расстановки называют размещениями без повторений из n - по k. Их количество равно: N= = , что легко видеть из представленной схемы.

Если мест заполнения k=n, то размещения без повторений из n по n называют n-перестановками и обозначают = = = n! ( эн-факториал ).

Если из размещений выделить только те, что отличаются друг от друга составом, но не порядком элементов, то получают k-сочетания и обозначают = = : делением на мы удаляем из общего числа размещений те, что различаются только порядком следования элементов.

Часто бывает полезно знать свойства сочетаний :

1*: = , что следует из выражения: = = = .

2*: = + , что следует из: + = + после применения достаточно простого преобразования:

= = .

☺ ☺

Пример 1 – 06: В группе 25 студентов. Надо избрать: старосту, профорга, физорга, культорга и ответственного по успеваемости. Сколькими способами можно выбрать названных лидеров, если каждый может исполнять только одну обязанность?

Решение:

1). В этом случае мы имеем задачу размещений без повторений из n =25 по k =5, то есть необходимо вычислить число: .

2). В результате имеем: =25·24·23·22·21 =6375600 способов.

Ответ: =6375600 способов.

Пример 1 – 07: Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?

Решение:

1). Если бы девушки становились не в круг, а в шеренгу, то различных способов было бы столько, сколько перестановок из 7 по 7, то есть = =7! = 5040.

2). Так как девушки становятся в круг для хоровода, то шеренга девушек имеет возможность вращаться. Это значит, что каждая перестановка девушек, не меняясь, может занимать 7 положений на круге. В таком случае для ответа на поставленный вопрос требуется разделить на 7. Получим: N=720.

Ответ: N=720.

Пример 1 – 08: В урне находятся 25 белых шаров с номерами {1, 2,..., 25}. Сколькими различными способами можно вынуть из урны 5 шаров?

Решение:

1). Очевидно, для нас неважен порядок номеров на вынутых шарах: номера должны быть разными. Тогда мы имеем случай применения k-сочетания: = = .

2). В нашем случае: = = =53130.

Ответ: N=720.

☻

Бином Ньютона.

Этот параграф интересен не только том, что мы сможем увидеть ещё одно симпатичное применение результатов комбинаторики. Мы исправим несправедливость забвения бинома Ньютона в школах России!

Бином Ньютона – это формула: , которую достаточно просто получить, если воспользоваться свойствами сочетаний и методом математической индукции! Интересно получить подтверждение формулы Ньютона путём нестрогих размышлений, а уже потом доказать её формально, алгебраически!

Нестрогое доказательство:

1) Запишем . Раскрывая скобки, получим слагаемые вида: . Так как из каждой скобки берём либо a, либо b, а число скобок n, то должно быть: m+k=n. Значит, все слагаемые имеют вид: .

2) При фиксированном значении k слагаемых вида: столько, сколько сочетаний из n по k, то есть , причём, k =0, 1,..., n.

Формальное (алгебраическое) доказательство:

1) Воспользуемся методом математической индукции. Учтём известные всем формулы:

здесь n =2 = ;

здесь n =3;

2) Видим, при n утверждение (формула) верно. Проверим утверждение при значении (n +1):

или, раскрывая скобки и приводя подобные:

или, учитывая свойства сочетаний:

→ верно.

3). Формула верна для любого n.

☺ ☺

Пример 1 – 09: Получить общую формулу для разложения: .

Решение:

1). Воспользуемся общей формулой: , заменяя значение b на –b.

2). В результате имеем: .

Ответ: .

Пример 1 – 10: Найти коэффициент при x³ в разложении .

Решение:

1). Воспользуемся разложением: и выделим слагаемое, содержащее x³: .

2). Вычислим нужный коэффициент (учитывая свойство сочетаний):

= = =7680.

Ответ: 7680.

Пример 1 – 11: Найти коэффициент при x¹¹ в разложении .

Решение:

1). Запишем общий член разложения: .

2). Используя исходные данные примера, запишем равенство: , откуда: при k=6.

3). Воспользуемся общим членом разложения для k=6 и вычислим: .

Ответ: 2268.

•• ☻ ☻ ••

Вопросы для самопроверки:

1. Что такое метод математической индукции?

2. Как применяют метод математической индукции?

3. Что такое комбинаторика?

4. Определение числа размещений из элементов по (различные случаи).

5. Формула для вычисления числа сочетаний из элементов по ?

6. Бином Ньютона. Общая формула разложения. Треугольник Паскаля.

Задачи для самоподготовки:

Пример C1 – 1: Методом математической индукции доказать, что при любом натуральном верно равенство: = = .

Пример C1 – 2: Методом математической индукции доказать, что при любом натуральном верно равенство: = = .

Пример C1 –3: Методом математической индукции доказать, что при любом натуральном верно равенство: = = .

Пример C1 – 4: Методом математической индукции доказать, что при любом натуральном верно неравенство : , .

Пример C1 – 5: Методом математической индукции доказать, что при любом натуральном верно неравенство : > , .

Пример C1 – 6: Методом математической индукции доказать, что при любом натуральном число, записанное в виде: , делится на 9.

•• ☻ ☻ ••

⇐ Предыдущая 123 4 Следующая ⇒