Применение метода математической индукции к решению задач на делимость натуральных чисел. Примеры - математическая индукция

Математическая индукция лежит в основе одного из самых распространенных методов математических доказательств. С его помощью можно доказать большую часть формул с натуральными числами n , например, формулу нахождения суммы первых членов прогрессии S n = 2 a 1 + n - 1 d 2 · n , формулу бинома Ньютона a + b n = C n 0 · a n · C n 1 · a n - 1 · b + . . . + C n n - 1 · a · b n - 1 + C n n · b n .

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

Yandex.RTB R-A-339285-1

Понятия индукции и дедукции

Для начала рассмотрим, что такое вообще индукция и дедукция.

Определение 1

Индукция – это переход от частного к общему, а дедукция наоборот – от общего к частному.

Например, у нас есть утверждение: 254 можно разделить на два нацело. Из него мы можем сделать множество выводов, среди которых будут как истинные, так и ложные. Например, утверждение, что все целые числа, которые имеют в конце цифру 4 , могут делиться на два без остатка – истинное, а то, что любое число из трех знаков делится на 2 – ложное.

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

Допустим, у нас есть последовательность чисел вида 1 1 · 2 , 1 2 · 3 , 1 3 · 4 , 1 4 · 5 , . . . , 1 n (n + 1) , где n обозначает некоторое натуральное число. В таком случае при сложении первых элементов последовательности мы получим следующее:

S 1 = 1 1 · 2 = 1 2 , S 2 = 1 1 · 2 + 1 2 · 3 = 2 3 , S 3 = 1 1 · 2 + 1 2 · 3 + 1 3 · 4 = 3 4 , S 4 = 1 1 · 2 + 1 2 · 3 + 1 3 · 4 + 1 4 · 5 = 4 5 , . . .

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

В чем заключается метод математической индукции

В основе этого метода лежит одноименный принцип. Он формулируется так:

Определение 2

Некое утверждение будет справедливым для натурального значения n тогда, когда 1) оно будет верно при n = 1 и 2) из того, что это выражение справедливо для произвольного натурального n = k , следует, что оно будет верно и при n = k + 1 .

Применение метода математической индукции осуществляется в 3 этапа:

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

Как применять метод математической индукции при решении неравенств и уравнений

Возьмем пример, о котором мы говорили ранее.

Пример 1

Докажите формулу S n = 1 1 · 2 + 1 2 · 3 + . . . + 1 n (n + 1) = n n + 1 .

Решение

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

Для начала проверяем, будет ли данное равенство справедливым при n , равном единице. Получаем S 1 = 1 1 · 2 = 1 1 + 1 = 1 2 . Здесь все верно.
Далее делаем предположение, что формула S k = k k + 1 верна.
В третьем шаге нам надо доказать, что S k + 1 = k + 1 k + 1 + 1 = k + 1 k + 2 , основываясь на справедливости предыдущего равенства.

Мы можем представить k + 1 в качестве суммы первых членов исходной последовательности и k + 1:

S k + 1 = S k + 1 k + 1 (k + 2)

Поскольку во втором действии мы получили, что S k = k k + 1 , то можно записать следующее:

S k + 1 = S k + 1 k + 1 (k + 2) .

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

S k + 1 = S k + 1 k + 1 (k + 2) = k k + 1 + 1 k + 1 (k + 2) = = k (k + 2) + 1 k + 1 (k + 2) = k 2 + 2 k + 1 k + 1 (k + 2) = (k + 1) 2 k + 1 (k + 2) = k + 1 k + 2

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

Ответ: предположение о формуле S n = n n + 1 является верным.

Возьмем более сложную задачу с тригонометрическими функциями.

Пример 2

Приведите доказательство тождества cos 2 α · cos 4 α · . . . · cos 2 n α = sin 2 n + 1 α 2 n sin 2 α .

Решение

Как мы помним, первым шагом должна быть проверка верности равенства при n , равном единице. Чтобы это выяснить, нам надо вспомнить основные тригонометрические формулы.

cos 2 1 = cos 2 α sin 2 1 + 1 α 2 1 sin 2 α = sin 4 α 2 sin 2 α = 2 sin 2 α · cos 2 α 2 sin 2 α = cos 2 α

Следовательно, при n , равном единице, тождество будет верным.

Теперь предположим, что его справедливость сохранится при n = k , т.е. будет верно, что cos 2 α · cos 4 α · . . . · cos 2 k α = sin 2 k + 1 α 2 k sin 2 α .

Доказываем равенство cos 2 α · cos 4 α · . . . · cos 2 k + 1 α = sin 2 k + 2 α 2 k + 1 sin 2 α для случая, когда n = k + 1 , взяв за основу предыдущее предположение.

Согласно тригонометрической формуле,

sin 2 k + 1 α · cos 2 k + 1 α = = 1 2 (sin (2 k + 1 α + 2 k + 1 α) + sin (2 k + 1 α - 2 k + 1 α)) = = 1 2 sin (2 · 2 k + 1 α) + sin 0 = 1 2 sin 2 k + 2 α

Следовательно,

cos 2 α · cos 4 α · . . . · cos 2 k + 1 α = = cos 2 α · cos 4 α · . . . · cos 2 k α · cos 2 k + 1 α = = sin 2 k + 1 α 2 k sin 2 α · cos 2 k + 1 α = 1 2 · sin 2 k + 1 α 2 k sin 2 α = sin 2 k + 2 α 2 k + 1 sin 2 α

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

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter

Брянский Городской Лицей №1

Исследовательская работа на тему:

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

Выполнил

М елешко К онстантин

ученик 10 физико-математического

Брянского Городского Лицея №1

Проверил

Т юкачева О льга И вановна

Введение_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 3

Основная часть

Полная и неполная индукция_ _ _ _ _ _ _ _ _3-4

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

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

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

К задачам на суммирование_ _ _ _ _ _ _ _ _ 7

К задачам на доказательство неравенств_ _8

К задачам на делимость _ _ _ _ _ _ _ _ _ _ _11

К задачам на доказательство тождеств _ _ _12

К другим задачам _ _ _ _ _ _ _ _ _ _ _ _ _ _ 13

Заключение_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 16

Список использованной литературы _ _ _ _17

Введение

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

Роль индуктивных выводов в экспериментальных науках очень велика. Они дают те положения, из которых потом путем дедукции делаются дальнейшие умозаключения. И хотя теоретическая механика основывается на трех законах движения Ньютона, сами эти законы явились результатом глубокого продумывания опытных данных, в частности законов Кеплера движения планет, выведенных им при обработке многолетних наблюдений датского астронома Тихо Браге. Наблюдение, индукция оказываются полезными и в дальнейшем для уточнения сделанных предположений. После опытов Майкельсона по измерению скорости света в движущейся среде оказалось необходимым уточнить законы физики, создать теорию относительности.

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

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

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

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

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

Пусть требуется установить, что каждое натуральное чётное число nв пределах 4 < n< 20 представимо в виде суммы двух простых чисел. Для этого возьмём все такие числа и выпишем соответствующие разложения:

4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;

14=7+7; 16=11+5; 18=13+5; 20=13+7.

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

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

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

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

Пусть, например, требуется найти сумму первых n последовательных нечётных чисел. Рассмотрим частные случаи:

1+3+5+7+9=25=5 2

После рассмотрения этих нескольких частных случаев напрашивается следующий общий вывод:

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

т.е. сумма n первых последовательных нечётных чисел равна n 2

Разумеется, сделанное наблюдение ещё не может служить доказательством справедливости при-

ведённой формулы.

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

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

Пусть нужно доказать справедливость некоторого утверждения для любого натурального числаn(например нужно доказать, что сумма первых n нечётных чисел равна n 2). Непосредственная проверка этого утверждения для каждого значения nневозможна, поскольку множество натуральных чисел бесконечно. Чтобы доказать это утверждение, проверяют сначала его справедливость для n=1. Затем доказывают, что при любом натуральном значении k из справедливости рассматриваемого утверждения при n=k вытекает его справедливость и при n=k+1.

Тогда утверждение считается доказанным для всех n. В самом деле, утверждение справедливо при n=1. Но тогда оно справедливо и для следующего числа n=1+1=2. Из справедливости утверждения для n=2 вытекает его справедливость для n=2+

1=3. Отсюда следует справедливость утверждения для n=4 и т.д. Ясно, что, в конце концов, мы дойдём до любого натурального числа n. Значит, утверждение верно для любого n.

Обобщая сказанное, сформулируем следующий общий принцип.

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

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

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

Если предложение А( n ) истинно при n = p и если А( k ) Þ А( k +1) для любого k > p , то предложение А( n ) истинно для любого n > p .

Доказательство по методу математической индукции проводиться следующим образом. Сначала доказываемое утверждение проверяется для n=1, т.е. устанавливается истинность высказывания А(1). Эту часть доказательства называют базисом индукции. Затем следует часть доказательства, называемая индукционным шагом. В этой части доказывают справедливость утверждения для n=k+1 в предположении справедливости утверждения для n=k (предположение индукции), т.е. доказывают, что А(k)ÞA(k+1).

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

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

Савельева Екатерина

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

Скачать:

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

Министерство науки и образования РФ

Государственное образовательное учреждение

средняя общеобразовательная школа № 618

По курсу: алгебра и начала анализа

Теме проектной работы

«Метод математической индукции и его применение к решению задач»

Работу выполнила : Савельева Е, 11В класс

Руководитель : Макарова Т.П., учитель математики ГОУ СОШ №618

1. Введение.

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

3.Применение метода математической индукции к суммированию рядов.

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

5.Применение метода математической индукции к решению геометрических задач.

6.Список использованной литературы.

Введение

В основе всякого математического исследования лежат дедуктивный и индуктивный методы. Дедуктивный метод рассуждений - это рассуждение от общего к частному, т.е. рассуждение, исходным моментом которого является общий результат, а заключительным моментом - частный результат. Индукция применяется при переходе от частных результатов к общим, т.е. является методом, противоположным дедуктивному. Метод математической индукции можно сравнить с прогресс-сом. Мы начинаем с низшего, в результате логического мышления приходим к высшему. Человек всегда стремился к прогрессу, к умению развивать свою мысль логически, а значит, сама природа предначертала ему размышлять индуктивно. Хотя и выросла область применения метода математической индукции, в школьной программе ему отводится мало времени.А ведь это так важно - уметь размышлять индуктивно. Применение этого принципа при решении задач и доказательстве теорем находится в одном ряду с рассмотрением в школьной практике и других математических принципов: исключенного третьего, включения-исключения, Дирихле и др. В этом реферате содержатся задачи из разных разделов математики, в которых основным инструментом является использование метода математической индукции. Говоря о важ-ности этого метода, А.Н. Колмогоров отмечал, что «понимание и умение применять принцип математической индукции является хорошим критерием зрелости, которая совершенно необходима математику». Метод индукции в широком его понимании состоит в переходе от частных наблюдений к универсальной, общей закономерности или обшей формулировке. В таком толковании метод — это, конечно, основной прием проведения исследований в любой экспериментальной естественнонаучной

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

Задача 1. В свой статье «Как я стал математиком» А.Н. Колмогоров пишет: «Радость математического «открытия» я познал рано, подметив в возрасте пяти-шести лет закономерность

1 =1 2 ,

1 + 3 = 2 2 ,

1 + 3 + 5 = З 2 ,

1 + 3 + 5 + 7 = 4 2 и так далее.

В школе издавался журнал "Весенние ласточки". В нем мое открытие было опубликовано...»

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

1 + 3 + 5 + ... + (2n - 1) = п 2

верна при любом заданном числе п = 1, 2, 3, ...

Для доказательства этой гипотезы достаточно установить два факта. Во-первых, для п = 1 (и даже для п = 2, 3, 4) нужное утверждение верно. Во-вторых, предположим, что утверждение верно при п = к, и убедимся, что тогда оно верно и для п = к + 1:

1 + 3 + 5+…+ (2к - 1) + (2к + 1) = (1 + 3 + 5 + ... + (2к - 1)) + (2к + 1) = к 2 + (2к + 1) = (к + I) 2 .

Значит, доказываемое утверждение верно для всех значений п: для п = 1 оно верно (это проверено), а в силу второго факта — для п = 2, откуда для п = 3 (в силу того же, второго факта) и т.д.

Задача 2. Рассмотрим все возможные обыкновенные дроби с числителем 1 и любым (целым положи-

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

Решение, Проверим сначала данное утверждение при п = 3; имеем:

Следовательно, базовое утверждение выполнено

Предположим теперь, что интересующее нас утверждение верно для какого-то числа к, и докажем, что оно верно и для следующего за ним числа к + 1. Другими словами, предположим, что существует представление

в котором k слагаемых и все знаменатели разные. Докажем, что тогда можно получить представление единицы в виде суммы из к + 1 дробей нужного вида. Будем считать, что дроби убывают, то есть знаменатели (в представлении единицы суммой к слагаемых) возрастают слева направо так, что т — наибольший из знаменателей. Мы получим нужное нам представление в виде суммы (к + 1)-й дроби, если разобьем одну дробь, например последнюю, на две. Это можно сделать, так как

И поэтому

Кроме того, все дроби остались различными, так как т было наибольшим знаменателем, а т + 1 > т , и

т(т + 1) > т.

Таким образом, нами установлено:

при п = 3 данное утверждение верно;

если интересующее нас утверждение верно для к,
то оно верно и для к + 1.

На этом основании мы можем утверждать, что рассматриваемое утверждение верно для всех натуральных чисел, начиная с трех. Более того, из приведенного доказательства следует и алгоритм отыскания нужного разбиения единицы. (Какой это алгоритм? Представьте число 1 в виде суммы 4, 5, 7 слагаемых самостоятельно.)

При решении предыдущих двух задач были сделаны два шага. Первый шаг называют базисом индукции, второй — индуктивным переходом или шагом индукции. Второй шаг наиболее важен, и он включает в себя предположение (утверждение верно при п = к) и заключение (утверждение верно при п = к + 1). Сам параметр п называется параметром индукции. Эта логическая схема (прием), позволяющая заключить, что рассматриваемое утверждение верно для всех натуральных чисел (или для всех, начиная с некоторого), так как справедливы и базис, и переход, называется принципом математической индукции, на котором и основан метод математической индукции. Сам термин «индукция» происходит от латинского слова induktio (наведение), которое означает переход от единичного знания об отдельных предметах данного класса к общему выводу о всех предметах данного класса, что является одним из основных методов познания.

Принцип математической индукции, именно в привычной форме двух шагов, впервые появился в 1654 году в работе Блеза Паскаля «Трактат об арифметическом треугольнике», в которой индукцией доказывался простой способ вычисления числа сочетаний (биномиальных коэффициентов). Д. Пойа в книге цитирует Б. Паскаля с небольшими изменениями, данными в квадратных скобках:

«Несмотря на то, что рассматриваемое предложение [явная формула для биномиальных коэффициентов] содержит бесчисленное множество частных случаев, я дам для нее совсем короткое доказательство, основанное на двух леммах.

Первая лемма утверждает, что предположение верно для основания — это очевидно. [При п = 1 явная формула справедлива...]

Вторая лемма утверждает следующее: если наше предположение верно для произвольного основания [для произвольного тг], то оно будет верным и для следующего за ним основания [для п + 1].

Из этих двух лемм необходимо вытекает справедливость предложения для всех значений п. Действительно, в силу первой леммы оно справедливо для п = 1; следовательно, в силу второй леммы оно справедливо для п = 2; следовательно, опять-таки в силу второй леммы, оно справедливо для п = 3 и так до бесконечности».

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

Рис 1

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

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

База индукции. При п = 1 все ясно, так как пирамидку из одного кольца очевидно можно переместить на любой стержень.
Шаг индукции. Предположим, что мы умеем перемещать любые пирамидки с числом колец п = к.
Докажем, что тогда мы сможем переместить и пира мидку с п = к + 1.

Пирамидку из к колец, лежащих на самом большом (к + 1)-м кольце, мы можем, согласно предположению, переместить на любой другой стержень. Сделаем это. Неподвижное (к + 1)-е кольцо не будет нам мешать провести алгоритм перемещения, так как оно самое большое. После перемещения к колец, переместим это самое большое (к + 1)-е кольцо на оставшийся стержень. И затем опять применим известный нам по индуктивному предположению алгоритм перемещения к колец, и переместим их на стержень с лежащим внизу (к + 1)-м кольцом. Таким образом, если мы умеем перемещать пирамидки с к кольцами, то умеем перемещать пирамидки и с к + 1 кольцами. Следовательно, согласно принципу математической индукции, всегда можно переместить нужным образом пирамидку, состоящую из п колец, где п > 1.

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

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

Задача 4 . Если n - натуральное число, то число четное.

При n=1 наше утверждение истинно: - четное число. Предположим, что - четное число. Так как, a 2k - четное число, то и четное. Итак, четность доказана при n=1, из четности выведена четность.Значит, четно при всех натуральных значениях n.

Задача 3. Доказать, что число З 3 + 3 - 26n — 27 при произвольном натуральном п делится на 26 2 без остатка.

Решение. Предварительно докажем по индукции вспомогательное утверждение, что 3 3n+3 — 1 делится на 26 без остатка при п > 0.

База индукции. При п = 0 имеем: З 3 - 1 = 26 —делится на 26.

Шаг индукции. Предположим, что 3 3n + 3 - 1 делится на 26 при п = к, и докажем, что в этом случае утверждение будет верно при п = к + 1. Так как 3

то из индуктивного предположения заключаем, что число 3 3k + 6 - 1 делится на 26.

Теперь докажем утверждение, сформулированное в условии задачи. И снова по индукции.

База индукции. Очевидно, что при п = 1 утверждение верно: так как 3 3+3 - 26 - 27 = 676 = 26 2 .
Шаг индукции. Предположим, что при п = к
выражение 3 3k + 3 - 26k - 27 делится на 26 2 без остатка, и докажем, что утверждение верно при п = к + 1,
то есть что число

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

Применение метода математической индукции к суммированию рядов.

Задача 5. Доказать формулу

N - натуральное число.

Решение.

При n=1 обе части равенства обращаются в единицу и, следовательно, первое условие принципа математической индукции выполнено.

Предположим, что формула верна при n=k, т.е.

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

Таким образом, из того, что формула верна при n=k, следует, что она верна и при n=k+1. Это утверждение справедливо при любом натуральном значении k. Итак, второе условие принципа математической индукции тоже выполнено. Формула доказана.

Задача 6. На доске написаны два числа: 1,1. Вписав между числами их сумму, мы получим числа 1, 2, 1. Повторив эту операцию еще раз, получим числа 1, 3, 2, 3, 1. После трех операций будут числа 1, 4, 3, 5, 2, 5, 3, 4, 1. Какова будет сумма всех чисел на доске после 100 операций?

Решение. Выполнять все 100 операций было бы очень трудоемким и долгим занятием. Значит, нужно попытаться найти какую-то общую формулу для суммы S чисел после п операций. Посмотрим на таблицу:

Заметили ли вы здесь какую-нибудь закономерность? Если нет, можно сделать еще один шаг: после четырех операций будут числа

1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1,

сумма которых S 4 равна 82.

В действительности можно не выписывать числа, а сразу сказать, как изменится сумма после добавления новых чисел. Пусть сумма была равна 5. Какой она станет, когда добавятся новые числа? Разобьем каждое новое число в сумму двух старых. Например, от 1, 3, 2, 3, 1 мы переходим к 1,

1 + 3, 3, 3 + 2, 2, 2 + 3, 3, 3 + 1, 1.

То есть каждое старое число (кроме двух крайних единиц) входит теперь в сумму три раза, поэтому новая сумма равна 3S - 2 (вычитаем 2, чтобы учесть недостающие единицы). Поэтому S 5 = 3S 4 - 2 = 244, и вообще

Какова же общая формула? Если бы не вычитание двух единиц, то каждый раз сумма увеличивалась бы в три раза, как в степенях тройки (1, 3, 9, 27, 81, 243, ...). А наши числа, как теперь видно, на единицу больше. Таким образом, можно предположить, что

Попробуем теперь доказать это по индукции.

База индукции. Смотри таблицу (для п = 0, 1, 2, 3).

Шаг индукции. Предположим, что

Докажем тогда, что S к + 1 = З к + 1 + 1.

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

Итак, наша формула доказана. Из нее видно, что после ста операций сумма всех чисел на доске будет равна З 100 + 1.

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

Задача 7. Доказать, что если = 2, х 2 = 3 и для всякого натурального п > 3 имеет место соотношение

х п = Зх п - 1 - 2х п - 2 ,

то

2 п - 1 + 1, п = 1, 2, 3, ...

Решение. Заметим, что в этой задаче исходная последовательность чисел {х п } определяется по индукции, поскольку члены нашей последовательности, кроме двух первых, задаются индуктивно, то есть через предыдущие. Так заданные последовательности называют рекуррентными, и в нашем случае эта последовательность определяется (заданием первых двух ее членов) единственным образом.

База индукции. Она состоит из проверки двух утверждений: при п = 1 и п = 2.В обоих случаях утверждение справедливо по условию.

Шаг индукции. Предположим, что для п = к - 1 и п = к утверждение выполнено, то есть

Докажем тогда справедливость утверждения для п = к + 1. Имеем:

х 1 = 3(2 + 1)- 2(2 + 1) = 2+1, что и требовалось доказать.

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

при к > 2.

Решение. Пусть п — натуральное число. Будем проводить индукцию по п.

База индукции. При п = 1 утверждение справедливо, поскольку единица сама является числом Фибоначчи.

Шаг индукции. Предположим, что все натуральные числа, меньшие некоторого числа п, можно представить в виде суммы нескольких различных членов последовательности Фибоначчи. Найдем наибольшее число Фибоначчи F т , не превосходящее п; таким образом, F т п и F т +1 > п.

Поскольку

По предположению индукции число п- F т может быть представлено в виде суммы 5 нескольких различных членов последовательности Фибоначчи, причем из последнего неравенства следует, что все члены последовательности Фибоначчи, участвующие в сумме 8, меньше F т . Поэтому разложение числа п = 8 + F т удовлетворяет условию задачи.

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

Задача 9. (Неравенство Бернулли.) Докажите, что при х > -1, х 0, и при целом п > 2 справедливо неравенство

(1 + х) п > 1 + хп.

Решение. Доказательство снова будем проводить по индукции.

1. База индукции. Убедимся в справедливости неравенства при п = 2. Действительно,

(1 + х) 2 = 1 + 2х + х 2 > 1 + 2х.

2. Шаг индукции. Предположим, что для номера п = к утверждение справедливо, то есть

(1 + х) к > 1 + хк,

Где к > 2. Докажем его при п = к + 1. Имеем: (1 + х) к + 1 = (1 + х) к (1 + х)>(1 + кх){1 + х) =

1 + (к + 1)х + кх 2 > 1 + (к + 1)х.

Итак, на основании принципа математической индукции можно утверждать, что неравенство Бернулли справедливо для любого п > 2.

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

Задача 10. Доказать, что

при любом натуральном п > 1.

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

Базис индукции проверяется без труда:1+

По предположению индукции

и нам остается доказать, что

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

Хотя это равенство на самом деле верно, оно не дает нам решения задачи.

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

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

Однако при п = 1 имеем: утверждение верно. Для обоснования индуктивного шага предположим, что

и докажем тогда, что

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

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

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

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

Задача 11. Докажите, что 2 т + п - 2 тп при любых натуральных тип.

Решение. Здесь мы имеем два параметра. Поэтому можно попробовать провести так называемую двойную индукцию (индукция внутри индукции).

Будем проводить индуктивное рассуждение по п.

1. База индукции по п. При п = 1 нужно проверить, что 2 т ~ 1 > т. Для доказательства этого неравенства воспользуемся индукцией по т.

а) База индукции по т. При т = 1 выполняется
равенство, что допустимо.

б) Шаг индукции по т. Предположим, что при т = к утверждение верно, то есть 2 к ~ 1 > к. Тогда до
кажем, что утверждение будет верным и при т = к + 1.
Имеем:

при натуральных к.

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

2. Шаг индукции по п. Выберем и зафиксируем какое-нибудь натуральное число т. Предположим, что при п = I утверждение справедливо (при фиксированном т), то есть 2 т +1 ~ 2 > т1, и докажем, что тогда утверждение будет справедливым и при п = l + 1.
Имеем:

при любых натуральных т и п.

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

Задача 12. Пусть т, п и к — натуральные числа, причем т > п. Какое из двух чисел больше:

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

Решение. Докажем сначала некоторое вспомогательное утверждение.

Лемма. При любых натуральных т и п (т > п) и неотрицательном (не обязательно целом) х справедливо неравенство

Доказательство. Рассмотрим неравенство

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

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

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

База индукции. При к = 1 имеем неравенство

у[т > у/п , справедливое в силу того, что т > п. При к = 2 требуемое получается из доказанной леммы подстановкой х = 0.

Шаг индукции. Предположим, при некотором к неравенство а >b к справедливо. Докажем, что

Из предположения индукции и монотонности квадратного корня имеем:

С другой стороны, из доказанной леммы следует,

Объединяя два последних неравенства, получаем:

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

Задача 13. (Неравенство Коши.) Докажите, что для любых положительных чисел..., а п справедливо неравенство

Решение. При п = 2 неравенство

о среднем арифметическом и среднем геометрическом (для двух чисел) будем считать известным. Пусть п= 2 , к = 1, 2, 3, ... и сначала проведем индукцию по к. База этой индукции имеет место Предположив теперь, что нужное неравенство уже установлено для п = 2 , докажем его для п = 2 . Имеем (применяя неравенство для двух чисел):

Следовательно, по индукционному предположению

Таким образом, индукцией по k мы доказали неравенство для всех п 9 являющихся степенью двойки.

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

то есть а г + а 2 + ... + а п _ х > (п — 1)А. Разделив обе части на п - 1, получим требуемое неравенство.

Итак, сначала мы установили, что неравенство имеет место для бесконечного числа возможных значений п, а затем показали, что если неравенство выполнено для п чисел, то оно справедливо и для (п - 1) числа. Отсюда теперь мы и заключаем, что неравенство Коти имеет место для набора из п любых неотрицательных чисел при любом п = 2, 3, 4, ...

Задача 14. (Д. Успенский.) Для любого треугольника АВС, у которого углы = САB, = СВА соизмеримы, имеют место неравенства

Решение. Углы и соизмеримы, а это (по определению) означает, что эти углы имеют общую меру, для которой = р, = (р, q— натуральные взаимно простые числа).

Воспользуемся методом математической индукции и проведем ее по сумме п = р + q натуральных взаимно простых чисел..

База индукции. При р + q = 2 имеем: р = 1 и q = 1. Тогда треугольник АВС равнобедренный, и нужные неравенства очевидны: они следуют из неравенства треугольника

Шаг индукции. Предположим теперь, что нужные неравенства установлены для р + q = 2, 3, ..., к — 1, где к > 2. Докажем, что неравенства справедливы и для р + q = к.

Пусть АВС — данный треугольник, у которого > 2. Тогда стороны АС и ВС не могут быть равными: пусть АС > ВС. Построим теперь, как на рисунке 2, равнобедренный треугольник АВС; имеем:

АС = DС и АD=АВ + ВD, следовательно,

2АС > АВ + ВD (1)

Рассмотрим теперь треугольник ВDС, углы которого также соизмеримы:

DСВ = (q - р), ВDС = p.

Рис. 2

Для этого треугольника выполнено индуктивное предположение, и поэтому

(2)

Складывая (1) и (2), имеем:

2AC+BD>

и поэтому

Из того же треугольника ВБС по предположению индукции заключаем, что

Учитывая предыдущее неравенство, заключаем, что

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

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

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

и черный цвета так, чтобы соседние части, имеющие общий отрезок границы, были разного цвета (как на рисунке 3 при п = 4).

рис 3

Решение. Воспользуемся индукцией по числу прямых. Итак, пусть п — число прямых, делящих нашу плоскость на части, п > 1.

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

Шаг индукции. Чтобы доказательство индуктивного перехода было более понятно, рассмотрим процесс добавления одной новой прямой. Если проведем вторую прямую (п = 2), то получим четыре части, которые можно раскрасить нужным образом, покрасив противоположные углы в один цвет. Посмотрим, что произойдет, если мы проведем третью прямую. Она поделит некоторые «старые» части, при этом появятся новые участки границы, по обе стороны которых цвет один и тот же (рис. 4).

Рис. 4

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

Рис.5

Докажем теперь индуктивный переход. Предположим, что для некоторого п = к утверждение задачи справедливо, то есть все части плоскости, на которые она делится этими к прямыми, можно раскрасить в белый и черный цвета так, чтобы соседние части были разного цвета. Докажем, что тогда существует такая раскраска и для п = к + 1 прямых. Поступим аналогично случаю перехода от двух прямых к трем. Проведем на плоскости к прямых. Тогда, по предположению индукции, полученную «карту» можно раскрасить нужным образом. Проведем теперь (к + 1)-ю прямую и с одной стороны от нее поменяем цвета на противоположные. Таким образом, теперь (к + 1)-я прямая всюду разделяет участки разного цвета, при этом «старые» части, как мы уже видели, остаются правильно раскрашенными. Согласно принципу математической индукции, задача решена.

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

Решение. Попытаемся доказать индукцией по п, что машина может отъехать на п километров от края пустыни. При п = 50 это известно. Осталось провести шаг индукции и объяснить, как проехать п = к + 1 километров, если известно, что п = к километров проехать можно.

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

База индукции. Пусть единица бензина — это количество бензина, необходимое для совершения одного километра пути. Тогда рейс на расстояние в 1 километр и обратно требует двух единиц бензина, поэтому мы можем оставить 48 единиц бензина в хранилище на расстоянии километра от края и вернуться за новой порцией. Таким образом, за несколько рейсов в хранилище можно сделать запас произвольного размера, который нам потребуется. При этом, чтобы создать 48 единиц запаса, мы расходуем 50 единиц бензина.

Шаг индукции. Предположим, что на расстоянии п = к от края пустыни можно запасти любое количество бензина. Докажем, что тогда можно создать хранилище на расстоянии п = к + 1 километров с любым заданным наперед запасом бензина и оказаться у этого хранилища в конце перевозок. Поскольку в точке п = к имеется неограниченный запас бензина, то (согласно базе индукции) мы можем за несколько рейсов в точку п = к + 1 сделать в точке п = к 4- 1 запас произвольного размера, который потребуется.

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

Заключение

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

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

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

Литература

1.Вuленкин ИНДУКЦИЯ. Комбинаторика. Пособие ДЛЯ учителей. М., Просвещение,

1976.-48 с.

2.Головина Л.И., Яглом И.М. Индукция в геометрии. - М.: Госуд. издат. литер. - 1956 - С.I00. Пособие по математике для поступающих в вузы/ Под ред. Яковлева Г.Н. Наука. -1981. - С.47-51.

3.Головина Л.И., Яглом ИМ. Индукция в геометрии. —
М.: Наука, 1961. — (Популярные лекции по математике.)

4. И.Т.Демидов,А.Н.Колмогоров, С.И.Шварцбург,О.С.Ивашев-Мусатов, Б.Е.Вейц. Учебное пособие / “Просвещение” 1975.

5.Р. Курант, Г Роббинс «Что такое математика?» Глава 1, § 2

6.Попа Д. Математика и правдоподобные рассуждения. — М,: Наука, 1975.

7.Попа Д. Математическое открытие. — М.: Наука,1976.

8.Рубанов И.С. Как обучать методу математической индукции/ Математика школе. - Nl. - 1996. - С.14-20.

9.Соминский И.С., Головина Л.И., Яглом ИМ. О методе математической индукции. — М.: Наука, 1977. — (Популярные лекции по математике.)

10.Соломинский И.С. Метод математической индукции. - М.: Наука.

63с.

11.Соломинский И.С., Головина Л.И., Яглом И.М. О математической индукции. - М.:Наука. - 1967. - С.7-59.

12.httр://ш.wikiреdiа.оrg/wiki

13.htt12:/ /www.rеfешtсоllесtiоп.ru/40 124.html

Индукция есть метод получения общего утверждения из частных наблюдений. В случае, когда математическое утверждение касается конечного числа объектов, его можно доказать, проверяя для каждого объекта. Например, утверждение: «Каждое двузначное чётное число является суммой двух простых чисел,» – следует из серии равенств, которые вполне реально установить:

10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.

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

Математическая индукция – метод доказательства некоторого утверждения для любого натурального n основанный на принципе математической индукции: «Если утверждение верно для n=1 и из справедливости его для n=k вытекает справедливость этого утверждения для n=k+1, то оно верно для всех n». Способ доказательства методом математической индукции заключается в следующем:

1) база индукции: доказывают или непосредственно проверяют справедливость утверждения для n=1 (иногда n=0 или n=n 0);

2) индукционный шаг (переход): предполагают справедливость утверждения для некоторого натурального n=k и, исходя из этого предположения, доказывают справедливость утверждения для n=k+1.

Задачи с решениями

1. Доказать, что при любом натуральном n число 3 2n+1 +2 n+2 делится на 7.

Обозначим А(n)=3 2n+1 +2 n+2 .

База индукции. Если n=1, то А(1)=3 3 +2 3 =35 и, очевидно, делится на 7.

Предположение индукции. Пусть А(k) делится на 7.

Индукционный переход. Докажем, что А(k+1) делится на 7, то есть справедливость утверждения задачи при n=k.

А(k+1)=3 2(k+1)+1 +2 (k+1)+2 =3 2k+1 ·3 2 +2 k+2 ·2 1 =3 2k+1 ·9+2 k+2 ·2=

3 2k+1 ·9+2 k+2 ·(9–7)=(3 2k+1 +2 k+2)·9–7·2 k+2 =9·А(k)–7·2 k+2 .

Последнее число делится на 7, так как представляет собой разность двух целых чисел, делящихся на 7. Следовательно, 3 2n+1 +2 n+2 делится на 7 при любом натуральном n.

2. Доказать, что при любом натуральном n число 2 3 n +1 делится на 3 n+1 и не делится на 3 n+2 .

Введём обозначение: а i =2 3 i +1.

При n=1 имеем, а 1 =2 3 +1=9. Итак, а 1 делится на 3 2 и не делится на 3 3 .

Пусть при n=k число а k делится на 3 k+1 и не делится на 3 k+2 , то есть а k =2 3 k +1=3 k+1 ·m, где m не делится на 3. Тогда

а k+1 =2 3 k+1 +1=(2 3 k) 3 +1=(2 3 k +1)(2 3 k ·2 –2 3 k +1)=3 k+1 ·m·((2 3 k +1) 2 –3·2 3 k)=3 k+1 ·m·((3 k+1 ·m) 2 –3·2 3 k)=

3 k+2 ·m·(3 2k+1 ·m 2 –2 3 k).

Очевидно, что а k+1 делится на 3 k+2 и не делится на 3 k+3 .

Следовательно, утверждение доказано для любого натурального n.

3. Известно, что х+1/x – целое число. Доказать, что х n +1/х n – так же целое число при любом целом n.

Введём обозначение: а i =х i +1/х i и сразу отметим, что а i =а –i , поэтому дальше будем вести речь о натуральных индексах.

Заметим: а 1 – целое число по условию; а 2 – целое, так как а 2 =(а 1) 2 –2; а 0 =2.

Предположим, что а k целое при любом натуральном k не превосходящем n. Тогда а 1 ·а n – целое число, но а 1 ·а n =а n+1 +а n–1 и а n+1 =а 1 ·а n –а n–1 . Однако, а n–1 , согласно индукционному предположению, – целое. Значит, целым является и а n+1 . Следовательно, х n +1/х n – целое число при любом целом n, что и требовалось доказать.

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

5. Доказать, что при натуральном n > 1 и |х|

(1–x) n +(1+x) n

При n=2 неравенство верно. Действительно,

(1–x) 2 +(1+x) 2 = 2+2·х 2

Если неравенство верно при n=k, то при n=k+1 имеем

(1–x) k+1 +(1+x) k+1

Неравенство доказано для любого натурального n > 1.

6. На плоскости дано n окружностей. Доказать, что при любом расположении этих окружностей образуемую ими карту можно правильно раскрасить двумя красками.

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

При n=1 утверждение очевидно.

Предположим, что утверждение справедливо для любой карты, образованной n окружностями, и пусть на плоскости задано n+1 окружностей. Удалив одну из этих окружностей, мы получим карту, которую в силу сделанного предположения можно правильно раскрасить двумя красками (смотрите первый рисунок из приведённых ниже).

Восстановим затем отброшенную окружность и по одну сторону от нее, например внутри, изменим цвет каждой области на противоположный (смотрите второй рисунок). Легко видеть, что при этом мы получим карту, правильную раскрашенную двумя красками, но только теперь уже при n+1 окружностях, что и требовалось доказать.

7. Выпуклый многоугольник будем называть «красивым», если выполняются следующие условия:

1) каждая его вершина окрашена в один из трёх цветов;

2) любые две соседние вершины окрашены в разные цвета;

3) в каждый из трёх цветов окрашена, по крайней мере, одна вершина многоугольника.

Доказать, что любой красивый n-угольник можно разрезать не пересекающимися диагоналями на «красивые» треугольники.

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

База индукции. При наименьшем из возможных n=3 утверждение задачи очевидно: вершины «красивого» треугольника окрашены в три разных цвета и никакие разрезы не нужны.

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

Индукционный шаг. Рассмотрим произвольный «красивый» (n+1)-угольник и докажем, используя предположение индукции, что его можно разрезать некоторыми диагоналями на «красивые» треугольники. Обозначим через А 1 , А 2 , А 3 , … А n , А n+1 – последовательные вершины (n+1)-угольника. Если в какой-либо из трёх цветов окрашена лишь одна вершина (n+1)-угольника, то, соединив эту вершину диагоналями со всеми не соседними с ней вершинами, получим необходимое разбиение (n+1)-угольника на «красивые» треугольники.

Если в каждый из трёх цветов окрашены не менее двух вершин (n+1)-угольника, то обозначим цифрой 1 цвет вершины А 1 , а цифрой 2 цвет вершины А 2 . Пусть k – такой наименьший номер, что вершина А k окрашена в третий цвет. Понятно, что k > 2. Отсечём от (n+1)-угольника диагональю А k–2 А k треугольник А k–2 А k–1 А k . В соответствии с выбором числа k все вершины этого треугольника окрашены в три разных цвета, то есть этот треугольник «красивый». Выпуклый n-угольник А 1 А 2 … А k–2 А k А k+1 … А n+1 , который остался, также, в силу индуктивного предположения, будет «красивым», а значит разбивается на «красивые» треугольники, что и требовалось доказать.

8. Доказать, что в выпуклом n-угольнике нельзя выбрать больше n диагоналей так, чтобы любые две из них имели общую точку.

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

Докажем более общее утверждение: в выпуклом n-угольнике нельзя выбрать больше n сторон и диагоналей так, чтобы любые две из них имели общую точку. При n = 3 утверждение очевидно. Допустим, что это утверждение верно для произвольного n-угольника и, используя это, докажем его справедливость для произвольного (n+1)-угольника.

Допустим, что для (n+1)-угольника это утверждение неверно. Если из каждой вершины (n+1)-угольника выходит не больше двух выбранных сторон или диагоналей, то всего их выбрано не больше чем n+1. Поэтому из некоторой вершины А выходит хотя бы три выбранных стороны или диагонали AB, AC, AD. Пусть АС лежит между АВ и AD. Поскольку любая сторона или диагональ, которая выходит из точки С и отличная от СА, не может одновременно пересекать АВ и AD, то из точки С выходит только одна выбранная диагональ СА.

Отбросив точку С вместе с диагональю СА, получим выпуклый n-угольник, в котором выбрано больше n сторон и диагоналей, любые две из которых имеют общую точку. Таким образом, приходим к противоречию с предположением, что утверждение верно для произвольного выпуклого n-угольника.

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

9. В плоскости проведено n прямых, из которых никакие две не параллельны и никакие три не проходят через одну точку. На сколько частей разбивают плоскость эти прямые.

С помощью элементарных рисунков легко убедится в том, что одна прямая разбивает плоскость на 2 части, две прямые – на 4 части, три прямые – на 7 частей, четыре прямые – на 11 частей.

Обозначим через N(n) число частей, на которые n прямых разбивают плоскость. Можно заметить, что

N(2)=N(1)+2=2+2,

N(3)=N(2)+3=2+2+3,

N(4)=N(3)+4=2+2+3+4.

Естественно предположить, что

N(n)=N(n–1)+n=2+2+3+4+5+…+n,

или, как легко установить, воспользовавшись формулой суммы n первых членов арифметической прогрессии,

N(n)=1+n(n+1)/2.

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

Для n=1 формула уже проверена.

Сделав предположение индукции, рассмотрим k+1 прямых, удовлетворяющих условию задачи. Выделим из них произвольным образом k прямых. По предположению индукции они разобьют плоскость на 1+ k(k+1)/2 частей. Оставшаяся (k+1)-я прямая разобьётся выделенными k прямыми на k+1 частей и, следовательно, пройдёт по (k+1)-й части, на которые плоскость уже была разбита, и каждую из этих частей разделит на 2 части, то есть добавится ещё k+1 часть. Итак,

N(k+1)=N(k)+k+1=1+ k(k+1)/2+k+1=1+(k+1)(k+2)/2,

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

10. В выражении х 1:х 2: … :х n для указания порядка действий расставляются скобки и результат записывается в виде дроби:

(при этом каждая из букв х 1 , х 2 , … , х n стоит либо в числителе дроби, либо в знаменателе). Сколько различных выражения можно таким образом получить при всевозможных способах расстановки скобок?

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

Можно предположить, что все остальные буквы х 3 , х 4 , … , х n могут располагаться в числителе или знаменателе совершенно произвольным образом. Отсюда следует, что всего можно получить 2 n–2 дробей: каждая из n–2 букв х 3 , х 4 , … , х n может оказаться независимо от остальных в числителе или знаменателе.

Докажем это утверждение по индукции.

При n=3 можно получить 2 дроби:

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

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

Пусть выражение х 1:х 2: … :х k после некоторой расстановки скобок записывается в виде некоторой дроби Q. Если в это выражение вместо х k подставить х k:х k+1 , то х k окажется там же, где и было в дроби Q, а х k+1 будет стоять не там, где стояло х k (если х k было в знаменателе, то х k+1 окажется в числителе и наоборот).

Теперь докажем, что можно добавить х k+1 туда же, где стоит х k . В дроби Q после расстановки скобок обязательно будет выражение вида q:х k , где q – буква х k–1 или некоторое выражение в скобках. Заменив q:х k выражением (q:х k):х k+1 =q:(х k ·х k+1), мы получим, очевидно, ту же самую дробь Q, где вместо х k стоит х k ·х k+1 .

Таким образом, количество всевозможных дробей в случае n=k+1 в 2 раза больше чем в случае n=k и равно 2 k–2 ·2=2 (k+1)–2 . Тем самым утверждение доказано.

Ответ: 2 n–2 дробей.

Задачи без решений

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

а) число 5 n –3 n +2n делится на 4;

б) число n 3 +11n делится на 6;

в) число 7 n +3n–1 делится на 9;

г) число 6 2n +19 n –2 n+1 делится на 17;

д) число 7 n+1 +8 2n–1 делится на 19;

е) число 2 2n–1 –9n 2 +21n–14 делится на 27.

2. Докажите, что (n+1)·(n+2)· … ·(n+n) = 2 n ·1·3·5·…·(2n–1).

3. Доказать неравенство |sin nx| n|sin x| для любого натурального n.

4. Найдите натуральные числа a, b, c, которые не делятся на 10 и такие, что при любом натуральном n числа a n + b n и c n имеют одинаковые две последние цифры.

5. Доказать, что если n точек не лежат на одной прямой, то среди прямых, которые их соединяют, не менее чем n различных.

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

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

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

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

Аксиома математической индукции формулируется так:

1. Проверяется справедливость некоторого утверждения при n = р0.

2. Предполагается, что это утверждение верно при n = к, к ≥ р0.

3. Доказывается, что утверждение верно при n=k+1.

Первый факт называется базисом индукции, второй - индукционным переходом или шагом индукции. Индукционный переход включает и себя посылку (или предположение) индукции (утверждение верно при n = k) и заключение (утверждение верно при п = k + 1). Другими словами, шаг индукции состоит в переходе от посылки к заключению, т. е. в выводе, что заключение верно, если верна посылка. В целом весь логический приём, позволяющий заключить, что рассматриваемое утверждение верно для всех натуральных чисел, коль скоро справедливы и базис, и переход, называется принципом математической индукции. На нём и основан метод математической индукции. Этот метод может быть успешно применён в том случае, когда имеется некоторое утверждение А, зависящее от параметра, принимающего натуральные значения, и требуется доказать, что А справедливо при всяком значении параметра.

Говоря об индукции вообще (т. е. не только в математике), различают полную и неполную индукцию.

Полная индукция

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

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

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

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

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

Неполная индукция. Популярная индукция

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

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

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

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

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

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

На доказательство теоремы

Пусть имеется выпуклая фигура и внутри ее взяты n точек. Тогда центр масс этих точек тоже принадлежит фигуре.

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

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

База доказана, теперь шаг индукции. Цент масс n+1 точек – это, в силу определения, центр масс двух точек: любой одной и центра масс всех остальных, которых n штук. В силу предположения индукции центр масс этих остальных n точек принадлежит фигуре, а значит, центр масс его и (n+1)-й точки тоже принадлежит фигуре, так как по определению лежит на отрезке, соединяющем эти две точки нашей выпуклой фигуры, что и требовалось доказать.

На нахождение суммы

Найдите сумму +

S(1)= S(2)= S(3)=S(2)+ Можно предположить, что S(n)=

Докажем это. Для n=1 формула верна. Предположим, что она будет верна и для n=k+1:

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

Пусть х1, х2,. , хn - произвольные положительные числа, причем x1x2xn = 1. Доказать, что х1 + х2 +. +хn ≥ n.

1. Если n = 1, то по условию х1 = 1 и, следовательно, можно написать x1 ≥ 1, т. е. для n = 1 утверждение верно.

2. Предположим, что утверждение верно для n = k. Пусть х1,х2,. ,хk,хk + 1 - произвольные положительные числа и х1х2хkхk+1 = 1.

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

Произведение их равно единице, и, следовательно, по индуктивному предположению x1 + x2 + + xk-1+ xkxk+1 ≥ k.

Прибавим к обеим частям последнего неравенства хk+хk+1,перенесем xkxk+1направо и преобразуем правую часть неравенства: x1 + x2 + + xk + xk+1 ≥ k - xkxk+1+хk + хk+1 =

K+1 +хk(1-хk+1) + хk+1- 1=k+1+хk(1- хk+1) - (1 - хk+1) =

K + 1+(1 - хk+1)(xk - l) ≥ k + l.

Таким образом, из истинности утверждения при n = k вытекает его истинность при n = k+ 1. Утверждение доказано. Из приведенного доказательства следует, что знак равенства в доказываемом соотношении имеет место тогда и только тогда, когда x1 = х2 =. = хn = 1.

Доказать неравенство

Где x1, x2,. , x3 – произвольные положительные числа.

Это важное неравенство между средним арифметическим и средним геометрическим n чисел является простым следствием соотношения, доказанного в предыдущем примере. В самом деле, пусть х1, х2,. , хn - произвольные положительные числа. Рассмотрим n чисел

Очевидно, что все эти числа положительны и произведение их равно единице. Следовательно, по доказанному в предыдущем примере их сумма больше или равна n, т. е.

причем знак равенства имеет место тогда и только тогда, когда x1 = х2 =. = хn.

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

На вывод формулы прогрессии

Пусть (an) – арифметическая прогрессия, у которой разность равна d.

a1=a1 a2=a1+d=a1+1d a3=a2+d=a1+d+d= a1+2d a4=a3+d=a1+2d+d= a1+3d a5=a4+d=a1+3d+d= a1+4d

Анализ этих равенств позволяет высказать гипотезу, что an=a1+(n – 1)d. Эта гипотеза верна при любом nN.

На делимость

Доказать истинность предложения

А (n) = {число 5∙23n-2 + З3n-1 кратно 19}, nN.

1. Высказывание А (1) = {число 5∙2 +З2 кратно 19} истинно.

2. Предположим, что для некоторого значения n = k

А(k) = {число 5∙23k-2 + З3k-1 кратно 19} истинно. Тогда, так как 5∙23(k+1)-2 + З3(k+1)-1 =

8 ∙5∙23k-2 + 27∙ З3k-1 = 8 (5∙23k-2 + З3k-1) + 19 ∙З3k-1, очевидно, что и А(k + 1) истинно. Действительно, первое слагаемое делится на 19 в силу предположения, что А (k) истинно; второе слагаемое тоже делится на 19, потому что содержит множитель 19. Оба условия принципа математической индукции выполнены, следовательно, предложение А (k) истинно при всех значениях n.

На доказательство тождеств

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

1*2+2*3+3*4+4*5++n(n+1)=.

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

1) Проверяем утверждение при n=1.

Неравенство выполняется.

2) Предположим, что равенство верно при n=k, т. е.

1*2+2*3+3*4+4*5++k(k+1)=

3) Докажем утверждение при n=k+1:

1*2+2*3+3*4+4*5++ k(k+1)+(k+1)(k+2)=+ (k+1)(k+2)=

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

Задачи реальной действительности

Докажем, что сумма внутренних углов выпуклого n-угольника равна π(n-2).

1. Минимальное число углов - три. Поэтому начнем доказательство с n = 3. Получаем, что для треугольника формула дает π (3~2) = π Утверждение для n = 3 справедливо.

2. Допустим, что формула верна при n=k. Докажем, что она верна для любого выпуклого

(к +1) -угольника. Разобьем

(к +1) -угольник диагональю так, что получим k-угольник и треугольник (см. рисунок).

Так как формула верна для треугольника и k-угольника, получаем π (к - 2) + π = π (к -1).

То же мы получим, если в исходную формулу подставить п = к + 1: π (к +1 - 2) = π (к -1).

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

Все согласны с тем, что должно быть условие. Мы должны уметь забраться на первую ступень. Далее должны уметь с 1-ой ступеньки забраться на вторую. Потом во второй – на третью и т. д. на n-ую ступеньку. Конечно, в совокупности же «n» утверждений гарантирует нм то, что мы сможем добраться до n-ой ступеньки.

Посмотрим теперь на 2, 3,. , n положение и сравним их друг с другом. Легко заметить, что все они имеют одну и ту же структуру: если мы добрались до k ступеньки, то можем забраться на (k+1) ступеньку. Отсюда становится естественной такая аксиома для справедливости утверждений, зависящих от «n»: если предложение А(n), в котором n – натуральное число, выполняется при n=1 и из того, что оно выполняется при n=k (где k – любое натуральное число), следует, что оно выполняется и для n=k+1, то предположение А(n) выполняется для любого натурального числа n.

Заключение.

Итак, индукция (от лат. inductio - наведение, побуждение) - одна из форм умозаключения, приём исследования, применяя который от знания отдельных фактов идут к обобщениям, к общим положениям. Метод математической индукции – метод доказательства, основанный на так называемой аксиоме (принципе) математической индукции. Индукция бывает полная и неполная. Применяя полную индукцию, мы лишь тогда считаем себя вправе объявить об истинности универсальной формулировки, когда убедились в её истинности для каждого без исключения значения n. Метод неполной индукции состоит в переходе к универсальной формулировке после проверки истинности частных формулировок для отдельных, но не всех значений n.

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

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

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

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

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

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