Исследовательская работа «Использование метода математической индукции для решения олимпиадных задач»

Автор: Качановская София Николаевна

Место работы/учебы (аффилиация): ГУО «Гимназия №1 г.Солигорска», Республика Беларусь, 7 класс

Научный руководитель: Гоглева Ксения Георгиевна

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

Метод математической индукции – один из основных способов доказательства утверждений, справедливых на всем множестве натуральных чисел. Иногда утверждения могут быть сформулированы для всех натуральных чисел n ≥ p₀, иногда – на множестве натуральных четных чисел и т. п.

Основой для доказательства таких утверждений является принцип математической индукции – аксиома, выражающая свойства натурального ряда чисел:

Если утверждение A(п) верно для п = 1 и предполагая справедливость A(п) при п = k > 1, удается доказать справедливость A(п) при п = k + 1, то утверждение А(п) верно для любого натурального числа п.

В соответствии с приведенным выше принципом математической индукции доказательство методом математической индукции состоит из нескольких этапов (шагов).

• Первый этап (базис индукции) – это доказательство следующей теоремы: утверждение А(1)истинно. Обычно эта теорема доказывается проверкой.
• Второй этап (индукционное предположение) – это следующее предположение: пусть утверждение А(k)истинно для некоторого произвольного натурального k≥1.
• Третий этап (индукционный переход) – это доказательство следующей теоремы: утверждение А(k + 1) верно.

При доказательстве индукционного перехода используются базис индукции и индукционное предположение, т.е. при доказательстве справедливости утверждения А(k + 1) мы считаем, что утверждения А(1) и А(k) справедливы для некоторого произвольного k≥1.

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

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

Метод математической индукции (ММИ) | Математика, которая мне нравится

Рассмотрим на примере, как работает метод.

Задача. Доказать, что для всех натуральных справедливо равенство

Решение. Обозначим через левую часть равенства, а через — его правую часть.

1) Докажем сначала, что .

Доказательство.

2) Дано: . Нужно доказать: .

Доказательство.

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

Предположим, что нам нужно доказать последовательность утверждений

Для того чтобы доказать все эти утверждения, достаточно доказать две теоремы:

1. — верное утверждение.

2. Если для какого-либо натурального верно утверждение , то верно и утверждение .

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

Теорема. Если последовательности и таковы, что , и для любого натурального

то для всех натуральных выполняется равенство .

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

Теорема. Если последовательности и таковы, что , и для любого натурального

то для всех натуральных выполняется неравенство .

Пример. Доказать, что для всех натуральных

Доказательство.
1.

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

2.

Теорема. Если последовательности и с положительными членами таковы, что , и для любого натурального

то для всех натуральных выполняется неравенство .

Задачи. Доказать

1. .

2. .

3. при .

4. при .

5. Доказать, что сумма всевозможных произведений квадратов натуральных чисел, взятых по два (от 1 до ), равна

6. Доказать, что для всех натуральных

(четверок — ).

7. Доказать, что для всех натуральных

8. Доказать, что для всех натуральных

9. Доказать, что для всех натуральных

10. Доказать, что сторона правильного вписанного в окружность -угольника выражается формулой

где — радиус этой окружности (двоек — ).

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

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

13. Доказать, что если — суммы членов геометрических прогрессий, у которых первые члены , а знаменатели соответственно равны , то

14. Доказать, что сумма всех членов каждой горизонтальной строки таблицы

равна квадрату нечетного числа.

15. Доказать, что произведение

состоящее из сомножителей, равно

16. Доказать, что сумма всевозможных парных произведений натуральных чисел равна

17. Доказать, что для любого натурального

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

Описание метода

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

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

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

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

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

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

Примеры решения задач

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

                                        ,                         (1)

где  .

    Доказательство. Обозначим  .

    Пусть  , тогда    и из формулы (1) следует  .

    Предположим, что

                                                .                        (2)

    Теперь требуется убедиться в том, что формула (1) выполняется и при , т.е. надо показать, что

                                             .                         (3)

    Из формул (1) и (2) получаем  

,     или    .

    Отсюда следует формула (3). Следовательно, утверждение (1) доказано.

Пример 2. Доказать, что  

                             ,                         (4)

где  .

    Доказательство. Обозначим  .

    Пусть  , тогда    и .

    Пусть и справедлива формула

                                               .                         (5)  

    Пусть  . Докажем, что      или  

                                           .                         (6)

    Так как  , то с учетом индукционного предположения (5) получаем

 .

    Следовательно, формула (6) является доказанной, а рассматриваемое равенство (4) справедливо для произвольных значений .   

Пример 3. Доказать, что  

                                    ,                         (7)

где  .

    Доказательство. Обозначим  .

    Если  , то     и  .

    Предположим, что  

                                                   .                         (8)  

    Докажем,  что   .   

    Из формул (7) и (8) следует, что

.  

    Отсюда вытекает справедливость формулы (7) для произвольных значений .   

    Пример 4.  Если числовая последовательность     является геометрической прогрессией, знаменатель которой равен  , то                                                       

                                                              (9)

    Доказательство. Обозначим  .

    Если  , то    и  

    Пусть    Необходимо показать, что  

    Так как     и  , то с учетом индукционного предположения имеем

,  

или      

    Отсюда следует справедливость формулы (9).

Пример 5.  Доказать, что  

       ,                         (10)

где  .

    Доказательство.  Обозначим левую часть равенства (10) как  .

    Если  , то    и  .

    Пусть  . Покажем, что  .

    Из определения и  равенства    следует, что

                                         .                         (11)

    Если воспользоваться известной формулой  ,

то из равенства (11) получим  ,   

  или  .

    Отсюда, согласно принципу математической индукции, следует справедливость формулы (10).

    Пример 6.  Доказать, что

         ,                         (12)

где  .

    Доказательство.  Обозначим  .

    Пусть  .  Тогда     и   .

    Предположим, что  ,  и покажем,  что  .

    Поскольку    ,  то   ,  

   или   .

    Формула (12) доказана.

    Пример 7.  Доказать неравенство

                                    ,                         (13)

где  .

    Доказательство.  Обозначим  .

    Если  , то  , т.е. неравенство (13) выполняется.

    Предположим, что  . Покажем, что  .

    Так как   и  ,  то  .

    Очевидно, что для решения задачи требуется доказать неравенство

                                        ,                         (14)

которое выполняется для произвольных натуральных  .

    Доказательство неравенства (14) будем вести методом от противного. Допустим, что существуют такие значения  , при которых выполняется противоположное неравенство, т.е. имеет место неравенство

                                          .                         (15)

    Преобразуем неравенство (15) следующим образом:

,      или  .

    Поскольку получили числовое противоречие , то неравенство (14) верно. Тем самым доказано, что   и неравенство (13)  выполняется для любых значений , где .

    Примечание. Проведя аналогичные рассуждения, можно доказать: если ,  то  .

    Пример 8.  Доказать, что выражение  кратно   (делится на число без остатка), где  .   

    Доказательство.  Если  , то  . Очевидно, что в данном случае требуемое утверждение выполняется.

    Пусть    кратно . Покажем, что выражение    также будет делиться на число без остатка.

    Так как  ,  то  

,     или  .                       (16)

    Согласно индукционному предположению, выражение кратно , поэтому из формулы (16) следует, что таковым будет и выражение .  

    В этой связи утверждение задачи доказано.

    Пример 9.  Доказать, что для любого натурального выражение  кратно .   

    Доказательство.  Если  , то    и    кратно .  Предположим, что кратно . Убедимся в том, что   также будет кратно .

    Так как  , то   ,   или  .                         (17)

    Поскольку натуральное число, то выражение всегда принимает только четные значения. В этой связи выражение   кратно . Согласно индукционному предположению кратно и поэтому из формулы (17) следует, что  делится на число  без остатка.

    Утверждение задачи доказано.

    Пример 10.  Доказать, что число диагоналей выпуклого угольника равно

                                ,                         (18)

где  .

    Доказательство.  Из формулы (18) следует, что    и  .  Действительно, треугольники диагоналей не имеют, а выпуклый четырехугольник имеет только две диагонали. Следовательно, формула (18) выполняется для начальных значений индукционного параметра  .

    Предположим, что  . Требуется доказать, что

                                      .                         (19)

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

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

    Таким образом, доказана справедливость утверждения (18).

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

Рекомендуемая литература

1. Виленкин Н.Я. Индукция. Комбинаторика. – М.: Просвещение, 1976. – 48 с.

2. Соминский И.С. Метод математической индукции. – М.: Наука, 1974. – 64 с.

3. Супрун В.П. Математика для старшеклассников: задачи повышенной сложности. – М.: КД «Либроком» / URSS, 2017. – 200 с.

Остались вопросы? 

Чтобы получить помощь репетитора – зарегистрируйтесь.

Урок в 10 классе по теме «Метод математической индукции»

Урок по теме: «метод математической индукции»

Тип: усвоения новых знаний.

Организация: дети сидят как обычно.

Цель: Организовать деятельность учащихся по обеспечению максимального усвоения темы. учащихся.

Задачи урока:

Образовательная: сформировать умение решать задачи, используя метод математической индукции.

Развивающая: развитие мышления учащихся.

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

Этапы урока:

1. Организационный этап

2. Этап подготовки к активному сознательному усвоению знаний

3. Организация деятельности по получению знаний.

4. Этап закрепления знаний

5. Контроль и коррекция знаний

6. Рефлексия.

Ход урока

1этап.Организационный этап – 2 мин.

Задачи:

• определение целей и задач урока (предварительная организация внимания учащихся, которая способствует созданию необходимого делового и психологического контакта между учителем и учащимися)

• подготовка учащихся к продуктивной работе на уроке

• развитие внимания к действиям учителя

• подготовка учащихся к общению на уроке.

• воспитание дисциплинированности, собранности требовательности к себе при организации рабочего труда учащегося.

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

2.Этап подготовки к активному сознательному усвоению знаний (этап актуализации знаний) — 5 мин.

Задачи:

• мотивирование учащихся на самостоятельную продуктивную деятельность

• актуализация опорных знаний и умений сравнивать и на основе этого делать самостоятельные выводы.

• воспитание отношения к другим людям через такие качества, как терпимость, деликатность и доброжелательность при анализе ответов товарищей по классу.

Учитель. Рассмотрим пример

ПРИМЕР. Найти формулу для вычисления суммы k первых нечетных чисел.

1+3+5+7+….Предложите свои способы нахождения этой суммы

Рассмотрим рисунок

Сделайте вывод…..

Итак, эта сумма равна 16 , если k=4

3этап. Организация деятельности по получению знаний-10 мин

Задачи:

• Организация деятельности учащимся по применению знаний при решении задач,

• развитие мышления учащихся при закреплении умений сравнивать и обобщать знания,

• развитие эмоциональной сферы во время работы, воспитание дисциплинированности, собранности требовательности к себе.

• воспитание отношения к другим людям через такие качества, как терпимость, деликатность и доброжелательность при анализе ответов товарищей по классу.

Учитель. Попробуем подсчитать такую сумму для некоторых значений kработает на доске)

k=1; 1=1=1²;

k=2; 1+3=4=2²;

k=3; 1+3+5=9=3²;

k=4; 1+3+5+7=16=4²;

Таким образом, 1+3…+(2n-1)+(2n+1)=(n+1)².

Получим:

1+3+…+(2n-1)+(2n+1)=n²+(2n+1)=(n+1)², ч.т.д.

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

Знаменитый математик 17 века Пьер Ферма высказал предположение, что простыми являются все числа вида 2²ⁿ+1. Он показал, что первые пять числе 2²⁰+1=3, 2²¹+1=5,2²²+1=17, 2²³+1=257, 2²⁴+1=65537 – простые, и рассуждая по индукциирешил, что для всех n числа вида 2²ⁿ+1- простые. Однако это предположение оказалось не верным, т.к. в 18 веке Л.Эйлер нашёл, что 2²⁵+1=4294967297=641∙4700417 – составное число.

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

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

Запишем в тетрадях

В основе этого метода лежит принцип математической индукции, заключающийся в следующем: (запись на доске)

Утверждения P(n) справедливо для всякого натурального n, если:

1)Оно справедливо для n=1;

2)Из справедливости утверждения для какого-либо произвольного натурального n=k следует его справедливость для n=k+1.

4 этап. Закрепление знаний -15 мин

Задачи:

• Организация групповой деятельности учащимся по закреплению знаний,

• развитие мышления учащихся при закреплении умений сравнивать и обобщать знания,

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

3. Закрепление материала: №6.6(а). Учитель предлагает попробовать решить в тетрадях, затем показывает решение примера на интерактивной доске.

ПРИМЕР. Методом математической индукции докажите справедливость равенства:

1²+3²+5²+…+(2n-1)²=

Доказательство:

1. При n=1, 1²=

2.Пусть при n=k верно неравенство:

1²+3²+…+(2k-1)²=

3.Докажем верность равенству при n=k+1

1²+3²+…+ (2k-1)²+ (2k+1)²=²=

= (2k+1)

= , ч.т.д.

Учитель: Метод математической индукции используется для доказательства тождеств, доказательства неравенств и решения задач на делимость.

Решите, работая парами №6.9,6.10(а),6.11(а). дается время для решения, затем ученики по желанию приглашаются к доске.

6 этап. Контроля, коррекции и оценки знаний. – 3 мин

Задачи:

• контроль ЗУН и анализ обнаруженных пробелов и ошибок и определение путей их устранения, формирование у учащихся навыков правильного воспроизведения своих ЗУН.

• развитие активность мышления и его самостоятельность, глубину, широту, систематичность и т.д.,

• воспитание отношения к другим людям через такие качества, как терпимость, деликатность и доброжелательность при анализе ответов товарищей по классу.

Решите самостоятельно №6.12(а)

7 этап. Рефлексия.

Задачи:

• закрепление, уточнение и систематизация знаний учащихся:

-слабые учащиеся лучше осознают материал,

-успевающие учащиеся убеждаются в правильности усвоения материала.

Учитель предлагает ученикам, которые справились с решением, рассказать своё решение, предварительно решение сканируется и выводится на интерактивную доску.

Учитель: объясните, как доказать тождество методом математической индукции?

Учитель сообщает, что домашнее задание будет дано на следующем уроке.

Метод математической индукции – МАТЕМАТИКА И МЫ

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

В основе этого метода лежит принцип математической индукции.

Если первый человек в очереди – женщина, и за каждой женщиной стоит женщина, то все в очереди – женщины.

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

Имеется последовательность утверждений. Если первое утверждение верно, и за каждым верным утверждением следует верное, то все утверждения в последовательности верны.

Пример 1. Пусть нужно доказать формулу .

Эта формула содержит целую последовательность утверждений:

1) ;

2)  ;

3)  ;

4)  ;

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

Пусть утверждение  k) верно, то есть равенство   справедливо.

Теперь прибавим к обеим частям равенства число . Получим

.

Но это как раз и есть утверждение , которое следует за утверждением .

Мы доказали, таким образом, что за каждым верным утверждением следует верное. В силу принципа математической индукции, наша формула верна при любом .

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

(в нижней строке написана та же сумма, что и в первой, но записанная в обратном порядке). Если  сложим почленно строки, то получим

,

и наше равенство доказано.

Приведем еще одну формулировку принципа математической индукции, немного отличную от первой.

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

Допустим, что удалось доказать такие два утверждения:

 

а) Наша гипотеза справедлива при .

 

б) Из того, что эта гипотеза верна при , где – произвольное натуральное число, следует, что  она верна и при .

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

Утверждение б) носит условный характер. В нем не утверждается, что гипотеза верна для . Оно состоит лишь в том, что если наша гипотеза верна, для , то она верна и для .

Мы будем называть б) индуктивным предположением.

Пример. Докажем, что для любого натурального число делится на .

Проведем доказательство методом математической индукции.

а)  При выражение  равно нулю и, значит, делится на .

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

Используя равенство

,

представим число в виде

.

Мы представили число  в виде суммы двух слагаемых. Первое их них, , делится на 5 по нашему предположению. Второе слагаемое , также делится на 5. Сумма двух чисел делится на 5, так как каждое слагаемое делится на 5, т.е.  делится на 5.

Итак, утверждения а) и б) доказаны. Значит, по принципу математической индукции число  делится на 5 при всех натуральных .

Существуют другие формулировки принципа математической индукции, эквивалентные данным нами. Вот одна из них:

Если:

 

а)  некоторое утверждение верно при ;

 

б)  из того, что оно верно для всех , следует, что оно верно и для , то это утверждение верно для всех .

Отличие этой формулировки от предыдущей состоит в следующем.

В пункте б) мы требуем, чтобы наше утверждение было справедливо для всех , а не только для .

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

Заметим также, что доказательство утверждения а) нужно, так сказать, лишь для “затравки”. Если вместо него доказать утверждение

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

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

Репозиторий Витебского государственного университета имени П. М. Машерова: Введение в математику: метод математической индукции, комбинаторика

Please use this identifier to cite or link to this item:
https://lib.vsu.by/jspui/handle/123456789/14124

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Theme by

Занятие 9. Математическая индукция

Известный литературный герой Шерлок Холмс, раскрывая преступления, в качестве метода своей работы использовал дедукцию. Дедуктивные рассуждения – это то, что в математике называют логическими рассуждениями, или переход от общего к частному. И в математической науке дедукция является самым распространенным  методом исследования. Правила логических рассуждений были сформулированы два с половиной тысячелетия назад древнегреческим учёным Аристотелем (силлогизмы).

Но есть и еще один способ рассуждений – от частного к общему. Такой метод носит название индукция. Индукция (induction– по-латыни наведение). То есть один или несколько частных случаев «наводят» на общее утверждение, общий вывод делается на основании частных наблюдений. Однако, индуктивный метод  имеет весьма существенный недостаток: на основании частных примеров может быть сделан неверный вывод. Гипотезы, возникающие при частных наблюдениях, не всегда являются правильными. Рассмотрим пример, принадлежащий Эйлеру.

Будем вычислять значение трехчлена n² +n+41 при некоторых первых значениях n:

Заметим, что получаемые в результате вычислений числа являются простыми. И непосредственно можно убедиться, что для каждого n от 1 до 39 значение многочлена является простым числом. Однако при n=40 получаем число 1681=41², которое не является простым. Таким образом, гипотеза, которая здесь могла возникнуть, то есть гипотеза о том, что при каждом n число  n²+n+41 является простым, оказывается неверной.

Таким образом, утверждение может быть справедливым в целом ряде частных случаев и в то же время несправедливым вообще. Поэтому в математике такой метод не используют, но применяют особый метод рассуждений, который называется методом математической индукции (полной индукции, совершенной индукции). Этот метод подразумевает полный перебор всех частных случаев. Однако прямой перебор не всегда возможен (учитывая, что множество чисел, для которых надо проверить то или иное утверждение, бесконечно). Поэтому для доказательства используют следующую схему:

1 шаг. Проверяем истинность утверждения P(п) для п = 1.

2 шаг. Предполагаем, что P(п) истинно для п = к (к — произвольное натуральное число).

3 шаг. Доказываем, что Р(п)  истинно, для п = к + 1.

Заменим в левой части равенства первые к слагаемых их суммой из 2-го шага:

В числителе левой части раскроем скобки:

Способом группировки разложим числитель левой части на множители:

Равенство верно.

Задание 2.

(Задача из книги А. Шеня «Математическая индукция», Москва, издательство МЦНМО, 2007)

Игрушка «Ханойские башни» имеет три стержня. На  одном находится пирамидка из нескольких колец (уменьшающихся снизу вверх). Эту пирамидку  нужно переложить на другой стержень, соблюдая правила игры: нельзя переносить сразу несколько колец и нельзя класть большее кольцо поверх меньшего. Например, пирамидку из двух колец можно переложить так: положить меньшее кольцо на второй стержень, затем большее на третий, а затем меньшее поверх большего. Доказать, что возможно переместить на другой стержень пирамидку из любого числа колец, соблюдая правила игры.

Задание 3.

Задание 4.

Доказать, что для любого натурального n значение выражения 4ⁿ +15n-1 кратно 9.

Задание  5.

Доказать, что при любом натуральном n число 

делится на 3.

Задание 6.

Доказать, что сумма первых n натуральных нечётных чисел равна квадрату их числа, то есть 

Задание 7.

Доказать, что

Задание 8.

Доказать, что сумма квадратов n первых чисел натурального ряда равна

Задание 9.

Доказать, что

Задание 10.

Доказать, что

Задание 11.

Доказать, что

Задание 12.

Доказать, что

Математическая индукция — Темы в предварительном исчислении

27

Принцип математической индукции

НАТУРАЛЬНЫЕ ЧИСЛА — это подсчет
числа: 1, 2, 3, 4 и т. д. Математическая индукция — это метод доказательства утверждения — теоремы или формулы — которое утверждается примерно на каждые натуральных чисел.

Под «каждым» или «всеми» натуральными числами мы подразумеваем любое имя, которое мы называем.

Например,

1 + 2 + 3 +. . . + n = ½ n ( n + 1).

Утверждается, что сумма последовательных чисел от 1 до n дается формулой справа. Мы хотим доказать, что это будет верно для n = 1, n = 2, n = 3 и так далее. Теперь мы можем проверить формулу для любого с заданным числом , скажем, n = 3:

.

1 + 2 + 3 = ½ · 3 · 4 = 6

— это правда.Это также верно для n = 4:

1 + 2 + 3 + 4 = ½ · 4 · 5 = 10.

Но как мы можем доказать это правило для через каждые значения n ?

Метод доказательства следующий. Мы показываем, что , если утверждение — правило — верно для любого конкретного числа k (например, 104), то оно также будет верно для его преемника, k + 1 (например, 105). Затем мы покажем, что утверждение верно для 1.Из этого следует, что утверждение будет истинным для 2. Следовательно, оно будет истинным для 3. Оно будет истинным для любого натурального числа, которое мы назовем.

Это называется принципом математической индукции.

Чтобы доказать утверждение по индукции, мы должны доказать пункты 1) и 2) выше.

Гипотеза шага 1) — « Утверждение верно для n = k » — называется предположением индукции или гипотезой индукции. Это то, что мы предполагаем , когда доказываем теорему по индукции.

Пример 1.
Докажите, что сумма первых n натуральных чисел дается следующей формулой:

Доказательство . Мы выполним шаги 1) и 2) выше. Во-первых, мы предположим , что формула верна для n = k ; то есть примем:

Это предположение индукции. Предполагая это, мы должны доказать, что формула верна для ее преемника, n = k + 1. То есть, мы должны показать:

Для этого мы просто добавим следующий член ( k + 1) к обеим сторонам предположения индукции, линия (1):

Это строка (2), это первое, что мы хотели показать.

Далее мы должны показать, что формула верна для n = 1. У нас есть:

1 = ½ · 1 · 2

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

(В Приложении к арифметике мы устанавливаем эту формулу напрямую.)

Пример 2. Докажите, что это правило экспонент верно для любого натурального числа n :

( ab ) ⁿ = a ⁿ b ⁿ .

Доказательство . Опять же, мы начинаем с , предполагая, что истинно для n = k ; то есть мы предполагаем:

( ab ) ^k = a ^k b ^k . . . . . . . . (3)

С этим предположением мы должны показать, что правило верно для его преемника, n = ( k + 1).Мы должны показать:

( ab ) ^{k + 1} = a ^{k + 1} b ^{k + 1} . . . . . . . (4)

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

Теперь, учитывая предположение, строку (3), как мы можем из нее построить строку (4)?

Просто умножив обе стороны прямой (3) на ab :

Это строка (4), которую мы хотели показать.

Итак, мы показали, что если теорема верна для любого конкретного натурального числа k , то она верна и для его преемника, k + 1.

Затем мы должны показать, что правило верно для n = 1; то есть

( ab ) ¹ = a ¹ b ¹ .

Но ( ab ) ¹ = ab ; и a ¹ b ¹ = ab .

Следовательно, это правило верно для любого натурального числа n .

Пример 3. Сумма последовательных кубиков. Докажите этот замечательный арифметический факт:

1 ³ + 2 ³ + 3 ³ +. . . + n ³ = (1 + 2 + 3 +.. . + n ) ² .

«Сумма n последовательных кубиков равна квадрату
суммы первых n чисел».

Другими словами, согласно Примеру 1:

Доказательство .Для удобства обозначим сумму до n через S ( n ). Таким образом, мы предполагаем, что формула верна для n = k ; то есть

Это строка (2), которую мы хотели показать.

Наконец, мы должны показать, что формула верна для n = 1.

— это правда. Таким образом, формула верна для любого натурального числа.

В Приложении к арифметике мы прямо показываем, что это правда.

Задача 1. Согласно принципу математической индукции, чтобы доказать утверждение, которое утверждается в отношении каждого натурального числа n , нужно доказать две вещи.

а) Что первое?

Чтобы увидеть ответ, наведите указатель мыши на цветную область.
Чтобы закрыть ответ еще раз, нажмите «Обновить» («Reload»).

Если утверждение верно для n = k , то оно будет верно для его преемника, k + 1.

б) Что второе?

Утверждение верно для n = 1.

c) Часть a) содержит предположение индукции. Что это?

Утверждение верно для n = k .

Проблема 2.Пусть S ( n ) = 2 n — 1. Вычислить

а) S ( к )
= 2 к — 1

б) Ю ( к + 1)
= 2 ( k + 1) — 1 = 2 k + 2 — 1 = 2 k + 1

Задача 3. Сумма первых n нечетных чисел равна n-му квадрату .

1 + 3 + 5 + 7 +. . . + (2 n — 1) = n ² .

a) Чтобы доказать, что с помощью математической индукции, какова будет индукция

а) предположение?

Утверждение верно для n = k :

1 + 3 + 5 + 7 +. . . + (2 k — 1) = k ² .

б) Что мы должны показать на основании этого предположения?

Утверждение верно для его преемника, k + 1:

.

1 + 3 + 5 + 7 +.. . + (2 k — 1) + 2 k + 1 = ( k + 1) ².

c) Покажи это.

При добавлении 2 k + 1 к обеим сторонам индукционного предположения:

г) Что мы должны показать, чтобы завершить доказательство математической индукцией?

Утверждение верно для n = 1.

д) Покажи это.

1 = 1 ²

Задача 4. Докажите математической индукцией:

Если мы обозначим эту сумму как S ( n ), то предположим, что формула верна для n = k ; то есть предположим, что

Теперь покажите, что формула верна для n = k + 1; то есть показать:

Начало:

Далее,

Формула верна для n = 1:

Следовательно, это верно для всех натуральных чисел.

Содержание | Дом

Сделайте пожертвование, чтобы TheMathPage оставалась в сети.
Даже 1 доллар поможет.

Авторские права © 2021 Лоуренс Спектор

Вопросы или комментарии?

Эл. Почта: [email protected]

Создание математики: математические инструменты: математический вводный курс

Математические индукции | Безграничная алгебра

Последовательности математических утверждений

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

Цели обучения

Обсудите, что подразумевается под последовательностью математических утверждений

Основные выводы

Ключевые точки

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

Ключевые термины

• натуральные числа : набор чисел, иногда описываемый как все неотрицательные целые числа [латекс] (0, 1, 2,…) [/ latex], а иногда описываемый как все положительные целые числа [латекс] (1, 2, 3,…) [/ латекс].
• set : набор из нуля или более объектов, возможно бесконечного размера, без учета любого порядка или повторения объектов, которые могут содержаться в нем.

В математике последовательность — это упорядоченный список объектов или элементов. Длина последовательности — это количество упорядоченных элементов, и она может быть бесконечной. В отличие от набора, порядок имеет значение в последовательностях, и одни и те же элементы могут появляться несколько раз в разных местах последовательности.Последовательность — это дискретная функция. Например, [латекс] \ left (M, A, R, Y \ right) [/ latex] — это последовательность букв, которая отличается от [latex] \ left (A, R, M, Y \ right) [/ latex ]. Хотя состав такой же, порядок отличается. Последовательности могут быть конечными, как в этом примере, или бесконечными, например, последовательность всех четных положительных целых чисел [latex] (2,4,6, \ cdots) [/ latex].

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

Например, в контексте математической индукции последовательность операторов обычно включает алгебраический оператор, в который вы можете подставить любое натуральное число [латекс] (0, 1, 2, 3,…) [/ latex], и это выражение должно верно.Таким образом, последовательность формируется заменой целых чисел [latex] k [/ latex], [latex] k + 1 [/ latex], [latex] k + 2 [/ latex] и так далее в математическое выражение. Эта концепция будет расширена в следующей концепции, которая вводит доказательство с помощью математической индукции.

Доказательство математической индукцией

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

Цели обучения

Используйте математическую индукцию, чтобы доказать бесконечную последовательность утверждений

Основные выводы

Ключевые точки

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

Ключевые термины

• индуктивное рассуждение : процесс умозаключений, основанных на наблюдаемых закономерностях или простом повторении.Часто используется в отношении прогнозов о том, что произойдет или действительно произойдет, на основе того, что произошло.

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

Самая простая и наиболее распространенная форма математической индукции доказывает, что утверждение, содержащее натуральное число [latex] n [/ latex], выполняется для всех значений [latex] n [/ latex]. Доказательство состоит из двух шагов:

1. Основа (базовый случай): показывает, что утверждение выполняется, когда [latex] n [/ latex] равно наименьшему значению, которое [latex] n [/ latex] задано в вопросе. Обычно [латекс] n = 0 [/ латекс] или [латекс] n = 1 [/ латекс].
2. Индуктивный шаг: показывает, что если утверждение верно для некоторого [латекса] n [/ latex], то утверждение также верно, когда [latex] n + 1 [/ latex] заменяется на [latex] n [/ latex].

Предположение на этапе индукции, что утверждение верно для некоторого [латекса] n [/ латекса], называется гипотезой индукции (или индуктивной гипотезой). Чтобы выполнить индуктивный шаг, нужно принять гипотезу индукции, а затем использовать это предположение, чтобы доказать утверждение для [latex] n + 1 [/ latex].

Выбор между [latex] n = 0 [/ latex] и [latex] n = 1 [/ latex] в базовом случае зависит от контекста доказательства: если [latex] 0 [/ latex] считается натуральное число, как это принято в области комбинаторики и математической логики, тогда [латекс] n = 0 [/ latex].Если, с другой стороны, [латекс] 1 [/ латекс] берется в качестве первого натурального числа, то базовый случай определяется как [латекс] n = 1 [/ латекс].

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

Визуализация

Может быть полезно подумать об эффекте домино. Если вам преподносят длинный ряд костяшек домино, можно быть уверенным, что:

1. Первое домино упадет
2. Каждый раз, когда выпадает домино, его следующий сосед также падает

Итак, делается вывод, что все костяшки домино упадут, и этот факт неизбежен.

Домино: Математическую индукцию можно неформально проиллюстрировать ссылкой на последовательный эффект падения домино.

Пример

Докажите следующее утверждение: Для каждого положительного целого числа [латекс] n [/ latex],

[латекс] \ displaystyle {0 + 1 + 2 + \ cdots + n = \ frac {n (n + 1)} {2}} [/ latex]

Базовый случай: Сначала мы должны проверить, что утверждение выполняется для [latex] n = 0 [/ latex]. В левой части уравнения у нас есть только [латекс] 0 [/ латекс].В правой части уравнения подставляем [латекс] n = 0 [/ латекс]. Таким образом, у нас есть [latex] \ displaystyle {0 = \ frac {0 (0 + 1)} {2}} [/ latex], которое можно упростить до [latex] 0 = 0 [/ latex]. Мы доказали, что утверждение верно для базового случая [latex] n = 0 [/ latex].

Индуктивный шаг: Предположим, что утверждение верно для [latex] n = k [/ latex], и проверьте, верно ли оно и для [latex] n = k + 1 [/ latex]. Другими словами, мы хотим показать, что утверждение верно, когда мы заменяем [латекс] k + 1 [/ latex] на [latex] n [/ latex]:

[латекс] \ displaystyle {0 + 1 + 2 + \ cdots + k + (k + 1) = \ frac {\ left (k + 1 \ right) \ left [\ left (k + 1 \ right) +1 \ right]} {2}} [/ латекс]

Обратите внимание, что мы можем использовать гипотезу индукции, что утверждение выполняется для [latex] n = k [/ latex], чтобы переписать левую часть уравнения:

[латекс] \ displaystyle {0 + 1 + 2 + \ cdots + k + (k + 1) = \ frac {k (k + 1)} {2}} + (k + 1) [/ latex]

Теперь мы можем переписать это утверждение и показать, что оно равно правой части предыдущего утверждения.Другими словами, если мы сможем показать, что верно следующее, мы покажем, что [latex] \ displaystyle {0 + 1 + 2 + \ cdots + n = \ frac {n (n + 1)} {2}} [ / latex] верно для [latex] k + 1 [/ latex]:

[латекс] \ displaystyle {\ frac {k (k + 1)} {2} + (k + 1) = \ frac {\ left (k + 1 \ right) \ left [\ left (k + 1 \ right ) +1 \ right]} {2}} [/ латекс]

Мы можем алгебраически переписать [латекс] \ displaystyle {\ frac {k (k + 1)} {2} + (k + 1)} [/ latex] следующим образом:

[латекс] \ displaystyle {\ begin {align} \ frac {k (k + 1)} {2} + (k + 1) & = \ frac {k (k + 1) + 2 (k + 1)} {2} \\ & = \ frac {(k + 1) (k + 2)} {2} \\ & = \ frac {\ left (k + 1 \ right) \ left [\ left (k + 1 \ вправо) +1 \ вправо]} {2} \ end {align}} [/ latex]

Это именно то, что мы хотели доказать.Мы показали, что [латекс] \ displaystyle {0 + 1 + 2 + \ cdots + n = \ frac {n (n + 1)} {2}} [/ latex] верен для любого [латекса] n = k + 1 [/ latex], если это верно для [latex] n = k [/ latex]. На этом шаг индукции завершен. Мы заключаем, что утверждение верно для любого неотрицательного целого числа [latex] n [/ latex].

Блестящая вики по математике и науке

В стране nnn городов. Любые два города соединены дорогой с односторонним движением. Покажите, что есть маршрут, который проходит через каждый город.

Утверждение очевидно верно для n = 1n = 1n = 1 или n = 2n = 2n = 2.Итак, мы прояснили «базовый вариант».

Но как показать индуктивный шаг, то есть, если мы знаем, что существует маршрут для страны с kkk городов, как показать, что маршрут существует для страны с (k + 1) (k + 1) (k + 1) городов?

Давайте запишем то, что мы уже знаем. Допустим, городами kkk являются C1, C2, C3, ⋯, CkC_1, C_2, C_3, \ cdots, C_ {k} C1, C2, C3, ⋯, Ck и есть маршрут

.

C1 → C2 → C3 → ⋯ → CkC_ {1} \ rightarrow C_ {2} \ rightarrow C_ {3} \ rightarrow \ cdots \ rightarrow C_kC1 → C2 → C3 → ⋯ → Ck

, который проходит через все они.Это наша гипотеза индукции. Теперь нам нужно показать индуктивный шаг. Другими словами, если у нас есть другой город Ck + 1C_ {k + 1} Ck + 1, мы должны показать, что его можно вставить где-нибудь в указанном выше маршруте.

Мы знаем, что каждые два города соединены дорогой с односторонним движением. Это означает, что есть дорога между CkC_kCk и Ck + 1C_ {k + 1} Ck + 1. Можно ли таким образом добавить Ck + 1C_ {k + 1} Ck + 1 в конец маршрута?

Нет, потому что дороги односторонние, и поэтому очень вероятно, что дорога между CkC_kCk и Ck + 1C_ {k + 1} Ck + 1 может пойти в неправильном направлении.Нельзя просто сказать, что наш маршрут

.

C1 → C2 → C3 → ⋯ → Ck → Ck + 1C_1 \ rightarrow C_2 \ rightarrow C_3 \ rightarrow \ cdots \ rightarrow C_k \ rightarrow C_ {k + 1} C1 → C2 → C3 → ⋯ → Ck → Ck +1

, и на этом мы закончили. Это немного сложнее.

Однако надежда еще не окончена. Помните, что любые два города соединены дорогой. Есть вероятность, что Ck + 1 → C1C_ {k + 1} \ rightarrow C_1Ck + 1 → C1. Если это так, мы закончили, потому что у нас есть маршрут

.

Ck + 1 → C1 → C2 → C3 → ⋯ → Ck.C_ {k + 1} \ rightarrow C_1 \ rightarrow C_2 \ rightarrow C_3 \ rightarrow \ cdots \ rightarrow C_k.Ck + 1 → C1 → C2 → C3 → ⋯ → Ck.

Если это не так, существует iii, с 1≤i≤k, 1 \ leq i \ leq k, 1≤i≤k, такой, что Ci → Ck + 1C_i \ rightarrow C_ {k + 1} Ci → Ск + 1.

Возьмите самый большой такой iii. По определению имеем Ci → Ck + 1 → Ci + 1C_i \ rightarrow C_ {k + 1} \ rightarrow C_ {i + 1} Ci → Ck + 1 → Ci + 1. Теперь мы можем вставить Ck + 1C_ {k + 1} Ck + 1 между этими двумя городами, и у нас есть маршрут

.

C1 → C2 → ⋯ Ci → Ck + 1 → Ci + 1 → ⋯ → Ck, C_1 \ rightarrow C_2 \ rightarrow \ cdots C_i \ rightarrow C_ {k + 1} \ rightarrow C_ {i + 1} \ rightarrow \ cdots \ стрелка вправо C_k, C1 → C2 → ⋯ Ci → Ck + 1 → Ci + 1 → ⋯ → Ck,

, что завершает наше доказательство.□ _ \ квадрат □

Примечание : Есть вероятность, что Ci + 1 = Ck + 1C_ {i + 1} = C_ {k + 1} Ci + 1 = Ck + 1. Это просто означает, что вам нужно пройти Ck + 1C_ {k + 1} Ck + 1 до конца маршрута.

Знания учителей Preservice о доказательстве математической индукции

Индукционная

Раздел 2.5 Введение

¶

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

Подраздел Марки

¶

Расследуй! 22

Вам нужно отправить посылку по почте, но вы еще не знаете, сколько почтовых расходов вам потребуется. У вас есть большой запас марок по 8 центов и марок по 5 центов. Какие именно почтовые расходы вы можете получить, используя эти марки? Какие суммы сделать невозможно?

Возможно, при исследовании проблемы, описанной выше, вы выбрали определенную сумму почтовых расходов, а затем выяснили, можно ли получить эту сумму, используя только 8-центовые и 5-центовые марки.Возможно, вы сделали это по порядку: вы можете заработать 1 цент с почтовых расходов? Вы можете заработать 2 цента? 3 цента? И так далее. Если это то, что вы сделали, вы на самом деле отвечали на последовательность вопросов. У нас есть методы работы с последовательностями. Посмотрим, поможет ли это.

На самом деле, мы будем составлять не последовательность вопросов, а последовательность утверждений. Пусть \ (P (n) \) будет утверждением «вы можете заработать \ (n \) центов почтовых расходов, используя только 8-центовые и 5-центовые марки». Поскольку каждое значение \ (n \ text {,} \) \ (P (n) \) является утверждением, оно либо истинно, либо ложно.Итак, если мы сформируем последовательность операторов

\ begin {уравнение *}
P (1), P (2), P (3), P (4), \ ldots
\ end {уравнение *}

последовательность будет состоять из \ (T \) (для истины) и \ (F \) (для ложного). В нашем конкретном случае последовательность начинается с

\ begin {уравнение *}
F, F, F, F, T, F, F, T, F, F, T, F, F, T, \ ldots
\ end {уравнение *}

, потому что \ (P (1), P (2), P (3), P (4) \) все ложны (вы не можете сделать 1, 2, 3 или 4 цента почтовых расходов), но \ (P (5 ) \) верно (используйте одну марку 5 центов) и так далее.

Давайте немного подумаем, как мы могли бы найти значение \ (P (n) \) для некоторого конкретного \ (n \) («значение» будет либо \ (T \), либо \ (F \)).Как мы нашли значение \ (n \) -го члена последовательности чисел? Как мы нашли \ (a_n \ text {?} \). Это можно было сделать двумя способами: либо существовала закрытая формула для \ (a_n \ text {,} \), чтобы мы могли вставить \ (n \) в формулу и получаем наше выходное значение, или у нас было рекурсивное определение последовательности, поэтому мы могли использовать предыдущие члены последовательности для вычисления \ (n \) -го члена. Имея дело с последовательностями операторов, мы также можем использовать любой из этих методов. Может быть, есть способ использовать сам \ (n \), чтобы определить, можем ли мы заработать \ (n \) центов за пересылку по почте.Это было бы что-то вроде закрытой формулы. Или вместо этого мы могли бы использовать предыдущие термины в последовательности (утверждений), чтобы определить, можем ли мы сделать \ (n \) центов почтовых расходов. То есть, если мы знаем значение \ (P (n-1) \ text {,} \), можем ли мы получить от него значение \ (P (n) \ text {?} \) Это будет что-то как рекурсивное определение последовательности. Помните, что поиск рекурсивных определений для последовательностей часто был проще, чем поиск закрытых формул. То же самое и здесь.

Предположим, я сказал вам, что \ (P (43) \) было правдой (это так).Можете ли вы определить из этого факта значение \ (P (44) \) (истинно оно или ложно)? Да, ты можешь. Даже если мы не знаем, как именно мы заработали 43 цента на 5-центовых и 8-центовых марках, мы знаем, что каким-то образом это можно было сделать. Что, если бы таким образом использовались как минимум три марки по 5 центов (что составляет 15 центов)? Мы могли бы заменить эти три марки по 5 центов двумя марками по 8 центов (что составляет 16 центов). Общая стоимость пересылки увеличилась на 1, так что у нас есть способ заработать 44 цента, так что \ (P (44) \) верно. Конечно, мы предполагали, что у нас есть не менее трех 5-центовых марок.Что, если мы этого не сделаем? Тогда у нас должно быть не менее трех марок по 8 центов (что составляет 24 цента). Если мы заменим эти три марки по 8 центов на пять марок по 5 центов (что составляет 25 центов), мы снова увеличим нашу общую сумму на 1 цент, так что мы можем заработать 44 цента, так что \ (P (44) \) истинно.

Обратите внимание, что мы не сказали, как заработать 44 цента, просто мы можем, исходя из того, что мы можем заработать 43 цента. Как мы узнаем, что можем заработать 43 цента? Возможно, потому, что мы знаем, что можем заработать \ (42 \) цента, а мы знаем, что можем сделать, потому что знаем, что можем заработать 41 цент, и так далее.Это рекурсия! Как и в случае с рекурсивным определением числовой последовательности, мы должны указать наше начальное значение. В этом случае начальное значение — «\ (P (1) \) ложно». Это нехорошо, поскольку наше рекуррентное соотношение просто говорит, что \ (P (k + 1) \) истинно , если \ (P (k) \) также истинно. Нам нужно начать процесс с истинным \ (P (k) \ text {.} \). Поэтому вместо этого мы можем использовать «\ (P (31) \) is true» в качестве начального условия.

Собирая все это вместе, мы приходим к следующему факту: можно (точно) произвести любую сумму, превышающую 27 центов, используя только 5-центовые и 8-центовые марки.Другими словами, \ (P (k) \) истинно для любого \ (k \ ge 28 \ text {.} \). Чтобы доказать это, мы могли бы сделать следующее:

1. Продемонстрируйте, что \ (P (28) \) верно.

2. Докажите, что если \ (P (k) \) истинно, то \ (P (k + 1) \) истинно (для любого \ (k \ ge 28 \)).

Предположим, мы это сделали. Тогда мы знаем, что 28-й член в приведенной выше последовательности — это \ (T \) (с использованием шага 1, начального условия или базового случая ), и что каждый член после 28-го также является \ (T \) (с использованием шага 2, рекурсивная часть или индуктивный корпус ).Вот как могло бы выглядеть доказательство.

Проба

Пусть \ (P (n) \) будет утверждением «можно сделать ровно \ (n \) центов почтовых расходов, используя 5-центовые и 8-центовые марки». Мы покажем, что \ (P (n) \) верно для всех \ (n \ ge 28 \ text {.} \)

.

Сначала мы покажем, что \ (P (28) \) истинно: \ (28 = 4 \ cdot 5+ 1 \ cdot 8 \ text {,} \), поэтому мы можем получить \ (28 \) центов, используя четыре 5 марки и одну марку 8 центов.

Теперь предположим, что \ (P (k) \) истинно для некоторого произвольного \ (k \ ge 28 \ text {.} \) Тогда можно сделать \ (k \) центов, используя 5-центовые и 8-центовые марки. Обратите внимание, что, поскольку \ (k \ ge 28 \ text {,} \) не может быть, чтобы мы использовали менее трех 5-центовых марок и менее трех 8-центовых марок: использование двух марок каждой из них даст только 26 центов. Теперь, если мы сделали \ (k \) центов, используя по крайней мере три марки по 5 центов, замените три марки по 5 центов двумя марками по 8 центов. Это заменяет 15 центов почтовых расходов на 16 центов, с переходом с \ (k \) центов на \ (k + 1 \) центов. Таким образом, \ (P (k + 1) \) верно.С другой стороны, если мы сделали \ (k \) центов, используя по крайней мере три марки по 8 центов, то мы можем заменить три марки по 8 центов на пять марок по 5 центов, переместившись с 24 центов на 25 центов, давая всего \ (k + 1 \) центов почтовых расходов. Так что и в этом случае \ (P (k + 1) \) верно.

Следовательно, по принципу математической индукции \ (P (n) \) верно для всех \ (n \ ge 28 \ text {.} \)

Подраздел Формирование доказательств

¶

То, что мы сделали в приведенном выше примере штампа, работает для многих типов проблем.Доказательство по индукции полезно при попытке доказать утверждения обо всех натуральных числах или всех натуральных числах, превышающих некоторый фиксированный первый случай (например, 28 в приведенном выше примере), а также в некоторых других ситуациях. В частности, индукцию следует использовать, когда есть способ перейти от одного случая к другому — когда вы видите, как всегда «делать еще один».

Это большая идея. Индуктивное размышление о проблеме может дать новое понимание проблемы. Например, чтобы по-настоящему понять проблему с маркой, вы должны подумать о том, как может быть произведена любая сумма почтовых расходов (более 28 центов) (это неиндуктивное рассуждение), а также о том, как можно произвести почтовые расходы изменения по мере увеличения суммы (индуктивное рассуждение).Когда вас просят предоставить доказательство по индукции, вас просят подумать о проблеме динамически ; как увеличение \ (n \) меняет проблему?

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

Вот общая структура доказательства математической индукцией:

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

Для начала скажите, какое утверждение вы хотите доказать: «Пусть \ (P (n) \) будет утверждением…» Чтобы доказать, что \ (P (n) \) истинно для всех \ (n \ ge 0 \ text {,} \) вы должны доказать два факта:

1. Базовый случай: Докажите, что \ (P (0) \) истинно. Вы делаете это напрямую. Часто это легко.

2. Индуктивный случай: докажите, что \ (P (k) \ imp P (k + 1) \) для всех \ (k \ ge 0 \ text {.} \). То есть докажите, что для любого \ (k \ ge 0 \) если \ (P (k) \) истинно, то \ (P (k + 1) \) также истинно. Это доказательство утверждения if… then…, поэтому вы можете предположить, что \ (P (k) \) истинно (\ (P (k) \) называется индуктивной гипотезой ). Затем вы должны объяснить, почему \ (P (k + 1) \) также верно с учетом этого предположения.

Предполагая, что вы успешно справились с обеими вышеизложенными частями, вы можете заключить: «Следовательно, по принципу математической индукции утверждение \ (P (n) \) верно для всех \ (n \ ge 0 \ text {.} \) ”

Иногда утверждение \ (P (n) \) будет истинным только для значений, например, \ (n \ ge 4 \ text {,} \) или некоторого другого значения. В таких случаях замените все 0 выше на 4 (или другое значение).

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

Индукция — это мощно! Подумайте, насколько легче опрокидывать костяшки домино, если не нужно самому толкать каждое домино.Вы просто запускаете цепную реакцию, и полагаетесь на относительную близость домино, чтобы позаботиться обо всем остальном.

Подумайте о нашем исследовании последовательностей. Для последовательностей легче найти рекурсивные определения, чем закрытые формулы. Переходить от одного дела к другому проще, чем сразу к конкретному делу. Вот что такого замечательного в индукции. Вместо того, чтобы переходить непосредственно к (произвольному) случаю для \ (n \ text {,} \), нам просто нужно сказать, как перейти от одного случая к другому.

Когда вас просят доказать утверждение с помощью математической индукции, вы должны сначала подумать о , почему это утверждение истинно, используя индуктивные рассуждения.Объясните, почему индукция — это то, что нужно делать, и примерно почему индуктивный случай будет работать. Затем сядьте и напишите аккуратное формальное доказательство, используя приведенную выше структуру.

Подраздел Примеры

¶

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

Пример2.5.1

Докажите для каждого натурального числа \ (n \ ge 1 \), что \ (1 + 2 + 3 + \ cdots + n = \ frac {n (n + 1)} {2} \ text {.} \)

Решение

Во-первых, давайте индуктивно подумаем об этом уравнении.На самом деле, мы знаем, что это верно по другим причинам (на ум приходит обратное и сложение). Но почему может быть применима индукция? Левая часть складывает числа от 1 до \ (n \ text {.} \). Если бы мы знали, как это сделать, добавить еще один член (\ (n + 1 \)) было бы не так сложно. Например, если \ (n = 100 \ text {,} \) предположим, что мы знаем, что сумма первых 100 чисел равна \ (5050 \) (поэтому \ (1 + 2 + 3 + \ cdots + 100 = 5050 \ text {,} \), что верно). Теперь, чтобы найти сумму первых 101 числа, имеет смысл просто прибавить 101 к 5050, вместо того, чтобы заново вычислять всю сумму.У нас было бы \ (1 + 2 + 3 + \ cdots + 100 + 101 = 5050 + 101 = 5151 \ text {.} \) На самом деле всегда было бы легко добавить еще один член. Вот почему мы должны использовать индукцию.

Теперь формальное доказательство:

Проба

Пусть \ (P (n) \) будет утверждением \ (1 + 2 + 3 + \ cdots + n = \ frac {n (n + 2)} {2} \ text {.} \) Мы покажем, что \ (P (n) \) верно для всех натуральных чисел \ (n \ ge 1 \ text {.} \)

Базовый случай: \ (P (1) \) — это утверждение \ (1 = \ frac {1 (1 + 1)} {2} \), которое явно верно.

Индуктивный случай: пусть \ (k \ ge 1 \) — натуральное число. Предположим (для индукции), что \ (P (k) \) истинно. Это означает \ (1 + 2 + 3 + \ cdots + k = \ frac {k (k + 1)} {2} \ text {.} \). Мы докажем, что \ (P (k + 1) \) является правда тоже. То есть мы должны доказать, что \ (1 + 2 + 3 + \ cdots + k + (k + 1) = \ frac {(k + 1) (k + 2)} {2} \ text {.} \) Чтобы доказать это уравнение, начните с добавления \ (k + 1 \) к обеим сторонам индуктивной гипотезы:

\ begin {уравнение *}
1 + 2 + 3 + \ cdots + k + (k + 1) = \ frac {k (k + 1)} {2} + (k + 1).
\ end {уравнение *}

Теперь, упрощая правую часть, получаем:

\ begin {align *}
\ frac {k (k + 1)} {2} + k + 1 \ amp = \ frac {k (k + 1)} {2} + \ frac {2 (k + 1)} {2} \\
\ amp = \ frac {k (k + 1) + 2 (k + 1)} {2} \\
\ amp = \ frac {(k + 2) (k + 1)} {2}.\ end {выровнять *}

Таким образом, \ (P (k + 1) \) истинно, поэтому по принципу математической индукции \ (P (n) \) верно для всех натуральных чисел \ (n \ ge 1 \ text {.} \)

Обратите внимание, что в той части доказательства, в которой мы доказали \ (P (k + 1) \) из \ (P (k) \ text {,} \), мы использовали уравнение \ (P (k) \ text { .} \) Это была индуктивная гипотеза. Увидеть, как использовать индуктивные гипотезы, обычно просто при доказательстве факта о такой сумме. В других доказательствах это может быть менее очевидно, где оно подходит.

Пример 2.2 \) на единицу больше, чем 5). Как выглядят числа, которые на единицу больше, чем кратные 5? У них должна быть последняя цифра 1 или 6. Что произойдет, если вы умножите такое число на 6? Зависит от числа, но в любом случае последняя цифра нового числа должна быть 6. А затем, если вы вычесть 1, вы получите последнюю цифру 5, то есть кратную 5.

Дело в том, что каждый раз, когда мы умножаем еще на одну шестерку, мы все равно получаем число с последней цифрой 6, поэтому вычитание 1 дает нам число, кратное 5.{k + 1} \ text {,} \) другими словами, \ (P (k + 1) \ text {.} \) Следовательно, по принципу математической индукции \ (P (n) \) верно для все \ (n \ ge 5 \ text {.} \)

Предыдущий пример может напомнить вам принцип ипподрома из исчисления, который гласит, что если \ (f (a) \ lt g (a) \ text {,} \) и \ (f ‘(x) \ lt g ‘(x) \) для \ (x> a \ text {,} \), затем \ (f (x) \ lt g (x) \) для \ (x> a \ text {.} \) Та же идея: большая функция увеличивается с большей скоростью, чем меньшая функция, поэтому большая функция останется больше.В дискретной математике у нас нет производных, поэтому мы смотрим на различия. Таким образом, индукция — это правильный путь.

Предупреждение:

С большой мощностью приходит большая ответственность. Индукция — это не волшебство. Кажется очень сильным предположить, что \ (P (k) \) истинно. В конце концов, мы пытаемся доказать, что \ (P (n) \) истинно, и единственная разница заключается в переменной: \ (k \) vs. \ (n \ text {.} \). Предполагаем ли мы, что то, что мы хотите доказать верно? Не совсем. Мы предполагаем, что \ (P (k) \) истинно, только ради доказательства того, что \ (P (k + 1) \) истинно.

Тем не менее вы можете начать верить, что с помощью индукции можно доказать все, что угодно. Рассмотрим это неверное «доказательство» того, что у всех канадцев один и тот же цвет глаз: Пусть \ (P (n) \) будет утверждением, что все \ (n \) канадцы имеют одинаковый цвет глаз. \ (P (1) \) верно, поскольку у всех такой же цвет глаз, как и у них самих. Теперь предположим, что \ (P (k) \) истинно. То есть предположим, что в любой группе \ (k \) канадцев у всех одинаковый цвет глаз. Теперь рассмотрим произвольную группу \ (k + 1 \) канадцев. У первых \ (k \) из них должен быть один и тот же цвет глаз, поскольку \ (P (k) \) истинно.Кроме того, последний \ (k \) из них должен иметь тот же цвет глаз, поскольку \ (P (k) \) истинно. Фактически, у всех в группе должен быть один и тот же цвет глаз. Таким образом, \ (P (k + 1) \) верно. Таким образом, по принципу математической индукции \ (P (n) \) верно для всех \ (n \ text {.} \)

Очевидно, что-то пошло не так. Проблема в том, что доказательство того, что \ (P (k) \) влечет \ (P (k + 1) \), предполагает, что \ (k \ ge 2 \ text {.} \). Мы показали только \ (P (1 )\) правда. На самом деле \ (P (2) \) ложно.

Подраздел Сильная индукция

¶

Расследуй! 23

Начните с квадратного листа бумаги.Вы хотите разрезать этот квадрат на более мелкие квадраты, не оставляя мусора (каждый лист бумаги, который у вас получится, должен быть квадратом). Очевидно, можно разрезать квадрат на 4 квадрата. Вы также можете разрезать его на 9 квадратов. Оказывается, квадрат можно разрезать на 7 квадратов (хотя и не все одинакового размера). Какое еще количество квадратов могло бы получиться?

Иногда, чтобы доказать, что \ (P (k + 1) \) истинно, было бы полезно знать, что \ (P (k) \) и \ (P (k-1) \) и \ (P (k-2) \) все верно.Рассмотрим следующую загадку:

У вас есть прямоугольная плитка шоколада, состоящая из \ (n \) одинаковых квадратов шоколада. Вы можете взять такую ​​планку и разбить ее по любому ряду или столбцу. Сколько раз вам придется ломать плитку, чтобы превратить ее в \ (n \) кусочки шоколада?

Поначалу этот вопрос может показаться невозможным. Возможно, я хотел попросить наименьшее количество необходимых перерывов ? Давайте разбираться.

Начнем с небольших случаев.Если \ (n = 2 \ text {,} \), у вас должен быть прямоугольник \ (1 \ times 2 \), который можно уменьшить на отдельные части за один разрыв. С \ (n = 3 \ text {,} \) у нас должен быть столбик \ (1 \ times 3 \), для которого требуется два разрыва: первый разрыв создает один квадрат и столбик \ (1 \ times 2 \). , который, как мы знаем, занимает один (более) перерыв.

А как насчет \ (n = 4 \ text {?} \) Теперь у нас может быть полоса \ (2 \ times 2 \) или полоса \ (1 \ times 4 \). В первом случае разбейте столбик на два \ (2 \ times 2 \) столбца, для каждого из которых требуется еще один разрыв (всего требуется три разрыва).Если мы начали с бара \ (1 \ times 4 \), у нас есть выбор для нашего первого перерыва. Мы могли бы сломать планку пополам, создав две полосы \ (1 \ times 2 \), или мы могли бы сломать один квадрат, оставив полосу \ (1 \ times 3 \). Но в любом случае нам нужно еще два перерыва, всего три.

Это начинает выглядеть так, как будто независимо от того, как мы ломаем планку (и как бы квадраты \ (n \) не выстраивались в прямоугольник), у нас всегда будет одинаковое количество необходимых разрывов. Также похоже, что это число на единицу меньше, чем \ (n \ text {:} \)

Гипотеза 2.5,4

Для \ (n \) квадратной прямоугольной плитки шоколада всегда требуется \ (n-1 \) разрывов, чтобы уменьшить плитку до отдельных квадратов.

Имеет смысл доказать это индукцией, потому что, сломав плитку один раз, вы получите плиток меньшего размера, шоколадок. Сведение к меньшим случаям — вот что такое индукция. Мы можем индуктивно предположить, что уже знаем, как работать с этими меньшими барами. Проблема в том, что если мы пытаемся доказать индуктивный случай с \ ((k + 1) \) — квадратным стержнем, мы не знаем, что после первого разрыва на оставшемся баре будет \ (k \) квадратов.Поэтому нам действительно нужно предположить, что наша гипотеза верна для всех случаев, меньших чем \ (k + 1 \ text {.} \)

.

Верно ли это более сильное предположение? Помните, что по индукции мы пытаемся доказать, что \ (P (n) \) верно для всех \ (n \ text {.} \). Что, если бы это было не так? Тогда был бы некоторый первый \ (n_0 \), для которого \ (P (n_0) \) было ложным. Поскольку \ (n_0 \) является первым контрпримером , мы знаем, что \ (P (n) \) истинно для всех \ (n \ lt n_0 \ text {.} \). Теперь мы переходим к доказательству того, что \ (P (n_0) \) на самом деле верно, исходя из предположения, что \ (P (n) \) верно для всех меньших \ (n \ text {.} \)

Это большое преимущество: теперь у нас есть более сильная индуктивная гипотеза. Можно считать, что \ (P (1) \ text {,} \) \ (P (2) \ text {,} \) \ (P (3) \ text {,} \)… \ (P (k) \) верно, просто чтобы показать, что \ (P (k + 1) \) верно. Ранее для этой цели мы просто предполагали \ (P (k) \).

Будет немного проще, если мы изменим наши переменные на сильную индукцию. Вот как могло бы выглядеть формальное доказательство:

Прочная конструкция для защиты от индукции

Опять же, начните с того, что вы хотите доказать: «Пусть \ (P (n) \) будет утверждением…» Затем установите два факта:

1. Базовый случай: Докажите, что \ (P (0) \) истинно.

2. Индуктивный случай: предположим, что \ (P (k) \) истинно для всех \ (k \ lt n \ text {.} \). Докажите, что \ (P (n) \) истинно.

Сделайте вывод: «Следовательно, по сильной индукции \ (P (n) \) истинно для всех \ (n \ gt 0 \ text {.} \)»

Конечно, можно заменить 0 на при необходимости более крупный базовый вариант.

Докажем нашу догадку о загадке плитки шоколада:

Проба

Пусть \ (P (n) \) будет утверждением, «требуется \ (n-1 \) перерывов, чтобы уменьшить \ (n \) — квадратную плитку шоколада до отдельных квадратов.”

Базовый случай: рассмотрим \ (P (2) \ text {.} \) Квадраты должны быть расположены в прямоугольник \ (1 \ times 2 \), и нам нужны \ (2-1 = 1 \) разрывы, чтобы уменьшить это на отдельные квадраты.

Индуктивный случай: зафиксируйте произвольный \ (n \ ge 2 \) и предположите, что \ (P (k) \) истинно для всех \ (k \ lt n \ text {.} \). Рассмотрим \ (n \) — квадратная прямоугольная плитка шоколада. Разорвите полосу один раз вдоль любой строки или столбца. В результате получается две плитки шоколада, скажем, размеров \ (a \) и \ (b \ text {.} \). То есть у нас есть \ (a \) — квадратная прямоугольная плитка шоколада, a \ (b \) — квадратная прямоугольная плитка шоколада и \ (a + b = n \ text {.} \)

Мы также знаем, что \ (a \ lt n \) и \ (b \ lt n \ text {,} \), поэтому по нашей индуктивной гипотезе \ (P (a) \) и \ (P (b) \) верны. Чтобы уменьшить полосу \ (a \) — sqaure до отдельных квадратов, требуется \ (a-1 \) разрыв; чтобы уменьшить \ (b \) — квадратную полосу до отдельных квадратов, требуется \ (b-1 \) перерыв. В результате наша исходная полоса уменьшится до отдельных квадратов. Все вместе взяло начальный перерыв, плюс перерывы \ (a-1 \) и \ (b-1 \), в общей сложности \ (1 + a-1 + b-1 = a + b-1 = n. -1 \) ломается. Таким образом, \ (P (n) \) верно.

Следовательно, по сильной индукции \ (P (n) \) истинно для всех \ (n \ ge 2 \ text {.} \)

Вот более математически релевантный пример:

Пример2.5.5

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

Решение

Во-первых, идея: если мы возьмем какое-то число \ (n \ text {,} \), возможно, оно будет простым. Если так, то все готово. Если нет, то оно составное, то есть произведение двух меньших чисел. Каждый из этих факторов меньше \ (n \) (но не менее 2), поэтому мы можем повторить рассуждение с этими числами.Мы свели к меньшему случаю.

Теперь формальное доказательство:

Проба

Пусть \ (P (n) \) будет утверждением: «\ (n \) либо простое, либо может быть записано как произведение простых чисел». Мы докажем, что \ (P (n) \) верно для всех \ (n \ ge 2 \ text {.} \)

.

Базовый случай: \ (P (2) \) верно, потому что \ (2 \) действительно простое число.

Индуктивный случай: предположим, что \ (P (k) \) истинно для всех \ (k \ lt n \ text {.} \). Мы хотим показать, что \ (P (n) \) истинно. То есть мы хотим показать, что \ (n \) либо простое число, либо произведение простых чисел.Если \ (n \) простое число, все готово. Если нет, то \ (n \) имеет более двух делителей, поэтому мы можем записать \ (n = m_1 \ cdot m_2 \ text {,} \) с \ (m_1 \) и \ (m_2 \) меньше, чем \ ( п \) (и больше 1). По предположению индукции, \ (m_1 \) и \ (m_2 \) либо простые, либо могут быть записаны как произведение простых чисел. В любом случае \ (n \) записывается как произведение простых чисел.

Таким образом, по сильной индукции \ (P (n) \) верно для всех \ (n \ ge 2 \ text {.} \)

Используете ли вы обычную индукцию или сильную индукцию, зависит от утверждения, которое вы хотите доказать.Если вы хотите быть в безопасности, вы всегда можете использовать сильную индукцию. Это действительно сильнее , поэтому он может сделать все, что «слабая» индукция. Тем не менее, использовать регулярную индукцию часто проще, поскольку есть только одно место, где вы можете использовать гипотезу индукции. Также есть что сказать о elegance в пруфах. Если вы можете доказать утверждение, используя более простые инструменты, это будет хорошо.

В качестве последнего контраста между двумя формами индукции рассмотрим еще раз проблему штампа.Регулярный вводный курс работал, показывая, как увеличить почтовые расходы на один цент (либо заменяя три марки по 5 центов двумя марками по 8 центов, либо три марки по 8 центов на пять марок по 5 центов). Мы могли бы дать несколько иное доказательство, используя сильную индукцию. Во-первых, мы могли бы показать пять базовых случаев : можно получить 28, 29, 30, 31 и 32 цента (мы бы фактически сказали, как создается каждый из них). Теперь предположим, что можно сделать \ (k \) центов почтовых расходов для всех \ (k \ lt n \) до тех пор, пока \ (k \ ge 28 \ text {.2 \ amp \ text {по факторингу}
\ end {выровнять *}

Таким образом, \ (P (k + 1) \) выполняется, поэтому по принципу математической индукции \ (P (n) \) верно для всех \ (n \ ge 1 \ text {.} \)

4

Докажите, что \ (F_0 + F_2 + F_4 + \ cdots + F_ {2n} = F_ {2n + 1} — 1 \), где \ (F_n \) — это \ (n \) -е число Фибоначчи.

Решение

Доказательство

Пусть \ (P (n) \) будет выражением \ (F_0 + F_2 + F_4 + \ cdots + F_ {2n} = F_ {2n + 1} — 1 \ text {.} \) Мы покажем, что \ ( P (n) \) верно для всех \ (n \ ge 0 \ text {.} \). Сначала базовый случай прост, потому что \ (F_0 = 0 \) и \ (F_1 = 1 \), поэтому \ (F_0 = F_1 — 1 \ text {.} \) Теперь рассмотрим индуктивный случай. Предположим, что \ (P (k) \) истинно, то есть предположим \ (F_0 + F_2 + F_4 + \ cdots + F_ {2k} = F_ {2k + 1} — 1 \ text {.} \), Чтобы установить \ (P (k + 1) \) работаем слева направо:

\ begin {align *}
F_0 + F_2 + \ cdots + F_ {2k} + F_ {2k + 2} ~ \ amp = F_ {2k + 1} — 1 + F_ {2k + 2} \ amp \ text {по инд. hyp.} \\
\ amp = F_ {2k + 1} + F_ {2k + 2} — 1 \ amp \\
\ amp = F_ {2k + 3} — 1 \ amp \ text {по рекурсивному определению}
\ end {выровнять *}

Следовательно, \ (F_0 + F_2 + F_4 + \ cdots + F_ {2k + 2} = F_ {2k + 3} — 1 \ text {,} \), то есть \ (P (k + 1) \) выполняется .{k + 1} \ lt (k + 1)! \), поэтому мы установили \ (P (k + 1) \ text {.} \) Таким образом, по принципу математической индукции \ (P (n) \) равно верно для всех \ (n \ ge 4 \ text {.} \)

6

Докажите математической индукцией, что \ (F_0 + F_1 + F_2 + \ cdots + F_ {n} = F_ {n + 2} — 1 \ text {,} \), где \ (F_n \) — это \ (n \) -е число Фибоначчи (\ (F_0 = 0 \ text {,} \) \ (F_1 = 1 \) и \ (F_n = F_ {n-1} + F_ {n-2} \)).

7

Зомби Эйлер и Зомби Коши, два известных математика-зомби, только что зарегистрировались в Твиттере.По прошествии одного дня у Зомби Коши больше последователей, чем у Зомби Эйлера. Каждый день после этого количество новых последователей Зомби Коши точно такое же, как количество новых последователей Зомби Эйлера (и ни один из них не теряет последователей). Объясните, как доказательство с помощью математической индукции может показать, что каждый день после первого дня у Зомби Коши будет больше последователей, чем у Зомби Эйлера. То есть объясните, что такое базовый случай и индуктивный случай, и почему они вместе доказывают, что у Зомби Коши будет больше последователей на 4-й день.2 = \ гидроразрыва {n (n + 1) (2n + 1)} {6}
\ end {уравнение *}

10

Что не так со следующим «доказательством» того «факта», что \ (n + 3 = n + 7 \) для всех значений \ (n \) (кроме, конечно, того, что оно претендует на доказательство, ложно )?

Проба

Пусть \ (P (n) \) будет утверждением, что \ (n + 3 = n + 7 \ text {.} \). Мы докажем, что \ (P (n) \) верно для всех \ (n \ in \ N \ text {.} \) Предположим для индукции, что \ (P (k) \) верно. То есть \ (k + 3 = k + 7 \ text {.} \) Мы должны показать, что \ (P (k + 1) \) истинно.Теперь, поскольку \ (k + 3 = k + 7 \ text {,} \) добавьте 1 к обеим сторонам. Это дает \ (k + 3 + 1 = k + 7 + 1 \ text {.} \) Перегруппировка \ ((k + 1) + 3 = (k + 1) + 7 \ text {.} \) Но это просто \ (P (k + 1) \ text {.} \) Таким образом, по принципу математической индукции \ (P (n) \) верно для всех \ (n \ in \ N \ text {.} \)

Решение

Единственная проблема в том, что мы никогда не устанавливали базовый вариант. Конечно, когда \ (n = 0 \ text {,} \) \ (0 + 3 \ ne 0 + 7 \ text {.} \)

11

Доказательство в предыдущей задаче не работает. Но если мы изменим «факт», мы сможем получить работающее доказательство.Докажите, что \ (n + 3 \ lt n + 7 \) для всех значений \ (n \ in \ N \ text {.} \). Это доказательство можно провести с помощью алгебры (без индукции), но цель этого упражнения состоит в том, чтобы выписать верное индукционное доказательство.

Решение

Доказательство

Пусть \ (P (n) \) будет утверждением, что \ (n + 3 \ lt n + 7 \ text {.} \) Мы докажем, что \ (P (n) \) истинно для всех \ (n \ in \ N \ text {.} \) Во-первых, обратите внимание, что выполняется базовый случай: \ (0 + 3 \ lt 0 + 7 \ text {.} \) Теперь предположим для индукции, что \ (P (k) \) правда. То есть \ (k + 3 \ lt k + 7 \ text {.} \) Мы должны показать, что \ (P (k + 1) \) истинно. Теперь, поскольку \ (k + 3 \ lt k + 7 \ text {,} \) добавьте 1 к обеим сторонам. Это дает \ (k + 3 + 1 \ lt k + 7 + 1 \ text {.} \) Перегруппировка \ ((k + 1) + 3 \ lt (k + 1) + 7 \ text {.} \) Но это просто \ (P (k + 1) \ text {.} \) Таким образом, по принципу математической индукции \ (P (n) \) верно для всех \ (n \ in \ N \ text {.} \ )

12

Найдите изъян в следующем «доказательстве» того «факта», что \ (n \ lt 100 \) для каждого \ (n \ in \ N \ text {.} \)

Проба

Пусть \ (P (n) \) будет выражением \ (n \ lt 100 \ text {.} \) Мы докажем, что \ (P (n) \) истинно для всех \ (n \ in \ N \ text {.} \) Сначала мы установим базовый случай: когда \ (n = 0 \ text {,} \) \ (P (n) \) истинно, потому что \ (0 \ lt 100 \ text {.} \) Теперь для индуктивного шага предположим, что \ (P (k) \) истинно. То есть \ (k \ lt 100 \ text {.} \) Теперь, если \ (k \ lt 100 \ text {,} \), то \ (k \) — какое-то число, например 80. Конечно, \ (80+ 1 = 81 \), что по-прежнему меньше 100. Так что и \ (k +1 \ lt 100 \). Но это то, что утверждает \ (P (k + 1) \), поэтому мы показали, что \ (P (k) \ imp P (k + 1) \ text {.} \) Таким образом, по принципу математической индукции \ (P (n) \) верно для всех \ (n \ in \ N \ text {.} \)

Решение

Проблема здесь в том, что пока \ (P (0) \) истинно, а пока \ (P (k) \ imp P (k + 1) \) для , некоторые значений \ (k \ text {, } \) существует по крайней мере одно значение \ (k \) (а именно \ (k = 99 \)), когда эта импликация не выполняется. Для правильного доказательства по индукции \ (P (k) \ imp P (k + 1) \) должно быть истинным для всех значений \ (k \), больших или равных базовому случаю.

13

Хотя приведенное выше доказательство не работает (лучше, поскольку утверждение, которое оно пытается доказать, ложно!), Мы можем доказать нечто подобное.Докажите, что существует строго возрастающая последовательность \ (a_1, a_2, a_3, \ ldots \) ​​чисел (не обязательно целых) такая, что \ (a_n \ lt 100 \) для всех \ (n \ in \ N \ text {. } \) (Под строго увеличивающимся мы подразумеваем \ (a_n \ lt a_ {n + 1} \) для всех \ (n \ text {.} \), Поэтому каждый член должен быть больше предыдущего.)

Решение

Доказательство

Пусть \ (P (n) \) будет утверждением «существует строго возрастающая последовательность \ (a_1, a_2, \ ldots, a_n \) с \ (a_n \ lt 100 \ text {.} \)». Мы докажем \ (P (n) \) верно для всех \ (n \ ge 1 \ text {.} \) Сначала мы устанавливаем базовый случай: \ (P (1) \) говорит, что существует единственное число \ (a_1 \) с \ (a_1 \ lt 100 \ text {.} \) Это правда — возьмите \ ( a_1 = 0 \ text {.} \) Теперь для индуктивного шага предположим, что \ (P (k) \) истинно. То есть существует строго возрастающая последовательность \ (a_1, a_2, a_3, \ ldots, a_k \) с \ (a_k \ lt 100 \ text {.} \). Теперь рассмотрим эту последовательность плюс еще один член, \ (a_ { k + 1} \), которое больше \ (a_k \), но меньше \ (100 \ text {.} \) Такое число существует, например, среднее между \ (a_k \) и 100.2 + n \) четно ».

16

Докажите, что существует последовательность положительных действительных чисел \ (a_0, a_1, a_2, \ ldots \) ​​такая, что частичная сумма \ (a_0 + a_1 + a_2 + \ cdots + a_n \) строго меньше, чем \ (2 \ ) для всех \ (n \ in \ N \ text {.} \) Подсказка: подумайте, как вы могли бы определить, что такое \ (a_ {k + 1} \), чтобы заставить аргумент индукции работать.

Решение

Идея состоит в том, чтобы определить последовательность так, чтобы \ (a_n \) было меньше расстояния между предыдущей частичной суммой и 2. Таким образом, когда вы добавляете ее в следующую частичную сумму, частичная сумма все равно меньше 2.Вы можете сделать это заранее или использовать умный \ (P (n) \) в доказательстве индукции.

Проба

Пусть \ (P (n) \) будет утверждением: «существует последовательность положительных действительных чисел \ (a_0, a_1, a_2, \ ldots, a_n \) такая, что \ (a_0 + a_1 + a_2 + \ cdots + a_n \ lt 2 \ text {.} \) ”

Базовый случай: выберите любой \ (a_0 \ lt 2 \ text {.} \)

Индуктивный случай: Предположим, что \ (a_1 + a_2 + \ cdots + a_k \ lt 2 \ text {.} \) Теперь пусть \ (a_ {k + 1} = \ frac {2- a_1 + a_2 + \ cdots + a_k } {2} \ text {.} \) Затем \ (a_1 + a_2 + \ cdots + a_k + a_ {k + 1} \ lt 2 \ text {.} \)

Следовательно, по принципу математической индукции \ (P (n) \) верно для всех \ (n \ in \ N \)

17

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

Решение

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

Проба

Пусть \ (P (n) \) будет утверждением «\ (n \) является либо степенью двойки, либо может быть записано как сумма различных степеней двойки». Мы покажем, что \ (P (n) \) истинно для всех \ (n \ ge 1 \ text {.x \) мы записали \ (n \) как сумму различных степеней 2.

Следовательно, по принципу (сильной) математической индукции \ (P (n) \) верно для всех \ (n \ ge 1 \ text {.} \)

18

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

19

Используйте индукцию, чтобы доказать, что если \ (n \) люди пожимают друг другу руки, общее количество рукопожатий равно \ (\ frac {n (n-1)} {2} \ text {.} \)

Решение

Обратите внимание: мы уже доказали это без использования индукции, но индуктивное рассмотрение проливает свет на проблему (и это весело).

Проба

Пусть \ (P (n) \) будет утверждением «когда \ (n \) люди пожимают друг другу руки, в общей сложности происходит \ (\ frac {n (n-1)} {2} \) рукопожатий. . »

Базовый случай: Когда \ (n = 2 \ text {,} \) будет одно рукопожатие, и \ (\ frac {2 (2-1)} {2} = 1 \ text {.} \) Таким образом \ (P (2) \) верно.

Индуктивный случай: Предположим, что \ (P (k) \) верно для произвольного \ (k \ ge 2 \) (что количество рукопожатий среди \ (k \) людей равно \ (\ frac {k (k-1) } {2} \ text {.} \) Что произойдет, если появится \ (k + 1 \) -й человек? Сколько происходит новых рукопожатий? Новый человек должен обменяться рукопожатием со всеми присутствующими, то есть \ (k \) новых рукопожатий. Таким образом, общая сумма теперь равна \ (\ frac {k (k-1)} {2} + k = \ frac {(k + 1) k} {2} \ text {,} \) по мере необходимости.

Следовательно, по принципу математической индукции \ (P (n) \) верно для всех \ (n \ ge 2 \ text {.} \)

20

Предположим, что конкретное действительное число \ (x \) обладает тем свойством, что \ (x + \ frac {1} {x} \) является целым числом.к) + \ журнал (а) = к \ журнал (а) + \ журнал (а)
\ end {уравнение *}

с последним равенством по индуктивной гипотезе. Но это упрощается до \ ((k + 1) \ log (a) \ text {,} \), устанавливающего \ (P (k + 1) \ text {.} \) Следовательно, по принципу математической индукции \ (P (n) \) верно для всех \ (n \ ge 2 \ text {.} \)

24

Пусть \ (f_1, f_2, \ ldots, f_n \) — дифференцируемые функции. Докажите по индукции, что

\ begin {уравнение *}
(f_1 + f_2 + \ cdots + f_n) ‘= f_1’ + f_2 ‘+ \ cdots + f_n’
\ end {уравнение *}

Вы можете принять \ ((f + g) ‘= f’ + g ‘\) для любых дифференцируемых функций \ (f \) и \ (g \ text {.} \)

Подсказка

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

25

Предположим, что \ (f_1, f_2, \ ldots, f_n \) — дифференцируемые функции. Используйте математическую индукцию, чтобы доказать обобщенное правило произведения:

\ begin {уравнение *}
(f_1 f_2 f_3 \ cdots f_n) ‘= f_1’ f_2 f_3 \ cdots f_n + f_1 f_2 ‘f_3 \ cdots f_n + f_1 f_2 f_3’ \ cdots f_n + \ cdots + f_1 f_2 f_3 \ cdots f_n ‘
\ end {уравнение *}

Вы можете предположить, что правило продукта для двух функций верно.

Подсказка

Для индуктивного шага мы знаем по правилу произведения для двух функций, что

\ begin {уравнение *}
(f_1f_2f_3 \ cdots f_k f_ {k + 1}) ‘= (f_1f_2f_3 \ cdots f_k)’ f_ {k + 1} + (f_1f_2f_3 \ cdots f_k) f_ {k + 1} ‘
\ end {уравнение *}

Затем используйте индуктивную гипотезу о первом слагаемом и распределите.

Принцип математической индукции

— GeeksforGeeks

Математическая индукция — это математический метод доказательства, который используется для доказательства данного утверждения о любом хорошо организованном множестве.Как правило, он используется для подтверждения результатов или утверждения утверждений, сформулированных в терминах n, , где n — натуральное число. Методика включает три шага для доказательства утверждения P (n), как указано ниже:

• Проверить, истинно ли утверждение для тривиальных случаев, таких как n = a , то есть P (a) истинно. [Базовый случай]
• Предположим, что утверждение верно для n = k для некоторого k ≥ a, то есть P (k) верно. [Индуктивная гипотеза]
• Если истинность P (k) влечет истинность P (k + 1), то утверждение P (n) верно для всех n ≥ a .

Базовый шаг и индуктивный шаг вместе доказывают, что P (k) => P (k + 1) => P (k + 2)…. правда. Следовательно, P (n) истинно для всех целых чисел n ≥ a. Мы можем сравнить математическую индукцию с падением домино. Когда домино падает, оно сбивает следующее домино подряд. Первое домино сбивает второго, второе сбивает третьего и так далее. В конце концов, все домино перевернутся. Но есть некоторые условия, которые должны быть выполнены:

1. Стартовое домино должно упасть, чтобы запустить процесс стука.Это базовый шаг.
2. Расстояние между домино должно быть одинаковым для любых двух соседних домино. В противном случае одно домино может упасть, не выбив другое. Тогда последовательность реакций остановится. Сохранение равного расстояния между домино гарантирует, что P (k) ⇒ P (k + 1) для каждого целого числа k ≥ a. Это индуктивный шаг.

Примеры

Пример 1: Для всех n ≥ 1 докажите, что,
1 ² + 2 ² + 3 ² ….n ² = {n (n + 1) (2n + 1)} / 6

Решение:

Пусть данный оператор будет P (n),

Теперь возьмем положительное целое число , k, и предположим, что P (k) истинно, т.е.

Теперь мы докажем, что P (k + 1) также истинно, так что теперь мы имеем

P (k + 1) = P (k ) + (k + 1) ²

Таким образом, P (k + 1) истинно, если P (k) истинно для всех натуральных чисел. Следовательно, посредством процесса математической индукции данный результат верен для всех натуральных чисел.

Пример 2: Для всех n ≥ 1 докажите, что
1.2.3 + 2.3.4 + 3.4.5… n (n + 1) (n + 2) = {n (n + 1) (n + 2) (n + 3)} / 4

Решение:

Пусть данный оператор будет S (n),

Теперь возьмем положительное целое число k и предположим, что S (k) быть истинным, т.е.

Теперь мы докажем, что S (k + 1) также истинно, так что теперь мы имеем,

Таким образом, S (k + 1) истинно, всякий раз, когда S (k) истинно для всех натуральных чисел.И изначально мы показали, что S (1) истинно, поэтому S (n) истинно для всех натуральных чисел.

Пример 3: Для всех n ≥ 1 докажите, что,
1 + 3 + 5… 2n — 1 = n ²

Решение:

Пусть данное утверждение будет S (n),

и S (n) = 1 + 3 + 5… 2n — 1 = n ²

Для n = 1, 2 * 1 — 1 = 1 ² Таким образом, S (1) истинно.

Теперь возьмем положительное целое число k и предположим, что S (k) истинно i.е.,

S (k) = 1+ 3 + 5 .. (2k — 1) = k ²

Теперь мы докажем, что S (k + 1) также истинно, так что теперь мы имеем,

1 + 3 + 5 .. (2 (k + 1) — 1) = (k + 1) ²

LHS: 1 + 3 + 5 +…. (2k — 1) + 2k + 2-1

= S (k) + 2k + 1

= k ² + 2k + 1

= (k + 1) ²

= RHS

Таким образом, S (k + 1) истинно, если S (k) истинно для всех натуральных чисел. И изначально мы показали, что S (1) истинно, поэтому S (n) истинно для всех натуральных чисел.

Пример 4: Для всех n ≥ 1 докажите, что
1,2 + 2,3 + 3,4… n (n + 1) = {n (n + 1) (n + 2)} / 3

Решение :

Пусть дано выражение S (n),

Теперь давайте возьмем положительное целое число k и предположим, что S (k) истинно, т.е.

Теперь мы докажем, что S ( k + 1) также истинно, поэтому теперь у нас есть

Таким образом, S (k + 1) истинно, если S (k) истинно для всех натуральных чисел. И изначально мы показали, что S (1) истинно, поэтому S (n) истинно для всех натуральных чисел.

Пример 5: Докажите, что _n = a ₁ + (n — 1) d, является общим членом любой арифметической последовательности.

Решение:

Для n = 1 имеем _n = a ₁ + (1 — 1) d = a ₁ , поэтому формула верна для n = 1,

Предположим, что формула a _k = a ₁ + (k — 1) верна для всех натуральных чисел.