Депман И. Я. Метод математической индукции : пособие для учителя. — М. : Учпедгиз, 1957. — 72 с.

И. Я. ДЕПМАН

МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

УЧПЕДГИЗ 1957

И. Я ДЕПМАН

МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

ПОСОБИЕ ДЛЯ УЧИТЕЛЯ

ГОСУДАРСТВЕННОЕ УЧЕБНО-ПЕДАГОГИЧЕСКОЕ ИЗДАТЕЛЬСТВО МИНИСТЕРСТВА ПРОСВЕЩЕНИЯ РСФСР

ЛЕНИНГРАДСКОЕ ОТДЕЛЕНИЕ

ЛЕНИНГРАД . 1957

Иван Яковлевич Депман

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

Пособие для учителя

Редактор И. В. Барковский Технический редактор Л, А Леонтьева Корректор А Я. Варковецкая

Сдано в набор 7/1 1957 г. Подписано к печати 27/III 1957 г. Печ. л. 4,5 (3,69). Уч.-изд. л. 3,00. Формат 84хю81/з2» Тираж 200Э0 экз. М-14088. Заказ № 1935. Цена 80 к.

Министерство культуры СССР. Главное управление полиграфической промышленности. 2-я типография „Печатный Двор" имени А. М. Горького. Ленинград, Гатчинская, 26.

ВВЕДЕНИЕ

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

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

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

1 И. С. Соминский, Метод математической индукции, гос. изд. техн.-теор. литературы, 1955. Кроме того, можно указать статьи: Серпинского В. С. („Математика и физика в школе", 1936, № 3), Безиковича Я. С. („Математика в школе", 1946, № 1), Нагибина Ф. Ф. (там же, 1949, № 4), Гайдука Ю. М„ (там же, 1950, № 2), Молодшего В. Н. (там же, 1954. № 3).

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

Исторические и иные сведения, сообщаемые нами в первой главе брошюры, имеют непосредственное отношение к теме „Метод математической индукции", однако могут быть использованы в кружковой работе и вне связи с этой темой и притом до IX класса, в котором, в лучшем случае, учитель знакомит учеников с методом математической индукции. Полагая, что поднятие у учащихся интереса к предмету является одним из самых действенных средств повысить уровень преподавания математики в школе, и считая, что интересная тематика внеклассных занятий по математике является хорошим рычагом для повышения указанного интереса, мы в I главе книги даем довольно большое число фактов, которые могут быть использованы учениками для сообщений в кружке. Материал этот состоит из мелких вопросов, в большинстве своем чисто арифметических, сообщение о которых в кружке посильно ученикам VI—VIII классов. Привлечение учеников этих классов к самостоятельной работе по математике является особенно желательным. Развертыванию кружковой работы по математике в школе препятствует главным образом недостаточность подходящего материала. Помочь учителю в этом отношении является целью нашей брошюры в той же мере, как принести ему посильную пользу при изложении темы о методе математической индукции.

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

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

смотрите конверт и освежите в памяти забытые факты и мысли. Поступайте по примеру знаменитого Куммера, утверждавшего, что он при преподавании „упорно шел на 12 часов впереди своего класса".

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

1) из I главы разбор нескольких более легких примеров ошибочных выводов при применении неполной индукции;

2) главу II и из главы III несколько примеров;

3) из V главы — десяток примеров по выбору учителя.

Кроме того, было бы желательно из главы IV проработать 1, 2, 3-й вопросы пункта а) и 1 и 2-й примеры пункта г). Ученикам, проявляющим интерес к математике, можно после этого предложить самостоятельно проработать остальные страницы книги.

ГЛАВА I

ИНДУКТИВНЫЙ МЕТОД В МАТЕМАТИКЕ

1. Индукция и индуктивный метод

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

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

Можно ли было на основании этих наблюдений сделать вывод, который некоторые из вас в те годы, вероятно, делали: все тела от нагревания расширяются?

Такой вывод неверен. Это было показано на очередном опыте: брали воду, имеющую температуру, близкую к 0°С, нагревали до температуры, приближающейся к 4° С. Объем воды при этом не увеличивался, а уменьшался. Утверждение, что все тела от нагревания расширяются, было неправильно. Можно было лишь сказать, что некоторые тела от нагревания расширяются, или, точнее, что те тела, над которыми мы производили опыт, от нагревания расширялись. Наблюдая некоторую закономерность в опытах над ограниченным количеством тел, нельзя с уверенностью утверждать, что наблюдаемая закономерность имеет место и для других тел. Заключения, на основании наблюдений над некоторыми явлениями о свойствах более широкого множества явлений, или, как говорят, заключения от частного к общему, могут оказаться ошибочными.

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

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

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

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

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

а) Ученику было предложено обратить дробь 6^5QQ в десятичную.

Вспомнив, что при обращении обыкновенной дроби в десятичную надо делить числитель ее на знаменатель, ученик при делении 30303 на 62500 получил в частном 0,4848 и остаток 30000.

Получив в частном повторение цифр 4 и 8, ученик заключил, что в искомой десятичной дроби эти цифры будут далее повторяться, и написал: |^|^ = 0,(48).

Правильно ли было заключение ученика?

Нет, не правильно, так как продолжение деления дает не 0,(48), а конечную десятичную дробь 0,484848. Заключение ученика о периодичности получаемой десятичной дроби было ошибочным; оно является примером необоснованного заключения по неполной индукции.

б) Ученику VII класса было предложено найти l/36493681. Он вычислял согласно правилам и получил

/36'49'36'81 = 6041.

Ученик, извлекая корень, разбил подкоренное число на пары и заметил, что все грани (пары) представляют точные квадраты (81, 36, 49, 36). Он сделал заключение: если подкоренное число разбивается на грани, представляющие точные квадраты, то и все подкоренное число есть точный квадрат и, следовательно, корень квадратный из него извлекается точно. Верно ли такое заключение по индукции?

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

в) Ученик, вычисляя корень /60,4938275, получил 7,7777777... и решил, что /60 4938275 = 7,(7). Верно ли его заключение?

Оно неверно: /б~0Д938275 = 7,77777779...

г) Ученику V класса нужно было разделить число 1,11111... на 9. Он нашел 8 цифр частного 0,1234567 и решил, что дальше последуют цифры 8 и 9. Имел ли он право сделать такое заключение?

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

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

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

а) Ошибка Пьера Ферма.

Французский математик Пьер Ферма (1601—1665) среди многих высказанных им теорем имел и следующую.

„Число вида 2*п -\- 1 при любом целом неотрицательном п есть число простое".1

Числа эти называются „числами Ферма" и обозначаются символом Fn:

F0 = 2*° + l=3 F1 = 2oJ+l=5

F2 = 222 + l=24+l = 17

F3 = 223 + l = 28+l = 257

F, = 22* + 1 — 216 + 1 = 65 537

F, = 2*5 + 1 = 232 + 1 = 4 294 967 297

Первые пять чисел Ферма FQ1 Fu F4j F3, F4 суть числа простые, в чем можно убедиться непосредственно для первых четырех, а для Fn по таблице простых чисел (в настоящее время имеется печатная таблица всех простых чисел до 12 000000). Проверить, будет ли простым числом

F3 = 4 294 967 297,

нельзя и по ныне существующим таблицам.

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

1 Число 2~п-\-\ надо понимать как 2(2,l) -j- 1,

чаям, может быть очень полезно, но не как основание науки; в этом случае можно удовлетвориться только доказанным". За необоснованное доверие наблюдениям без доказательства Ферма и был наказан: его теорема уже для F5 неверна. Число

F5 = 22"° + 1 = 232 + 1 = 4 294 967 297

есть число составное. Ошибку Ферма обнаружил член Петербургской Академии наук Леонард Эйлер (1707—1783) в 1732 г., показав, что число Fb делится на 641. Это мы можем доказать без вычисления значения Fb.

2** = 232 = 24 • 228 = 16 - 228 = (641—625). 228 = = 641 . 228 — 625-228.

Рассмотрим отдельно вычитаемое:

625 - 228 = 54. 228 = (5 - 27)4 = 6404 = (641 — I)4 = = 6414 — 4.6413 + 6.6412 — 4-641 +1.

Подставив это выражение вместо 625 • 228, имеем:

22* = 641 - 228 — 6414 + 4.6413 — 6.6412 + 4.641 — 1; 22* = кратному 641 — 1, или /73 = 225 + 1 кратно 641.

Вычисление подтверждает наше заключение:

F, = 232 + 1 = 4 294 967 297 = 641 • 6 700 417.

Отметим, что среди чисел Ферма Fn при /г^>4 ни одного простого числа не найдено. Для чисел Fn при

п = 7, 8, 9, 11, 12, 15, 18, 23, 36, 38, 73

доказано, что все они являются числами составными.

Число F12 = 22l2+1= 24096 + 1 делится на 114689; число ,Р2з = 2223 + 1 = 28388608 + 1 делится на 167 772 162. Последнее число состоит из 2 525 223 цифр и при печатании шрифтом настоящей книги имело бы длину в 5 км.

Что числа Fn и F23 являются составными числами и имеют указанные делители, было доказано русским любителем математики Иоанном Михеевичем Первушиным (1827—1900) в 1877 г. и в следующие годы.

Вопрос о том, является ли число Fn = 22" + 1 простым или составным числом, важен для геометрии при решении вопроса о возможности или невозможности построить правильный многоугольник циркулем и линейкой.

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

Обозначим символом р{п) число способов, сколькими можно составить натуральное число п из натуральных же чисел. Имеем:

Представления числа п в виде сумм

Для значений /г от 2 до 6 значения р {ri) доставляют ряд простых чисел натурального ряда 2, 3, б, 7, И. Может возникнуть предположение, что р {ri) равняется (п—1)-му простому числу в натуральном ряду и что р{7) равняется 13. Однако подсчет показывает, что число 7 можно представить в виде суммы не 13-ю, а 15-ю способами:

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

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

Если бы индуктивная догадка о том, что p{ri) равно (п—1)-му простому числу в натуральном ряду, была правильной, то /7(200) равнялось бы 199-му простому

числу, которое равно 1217.1 Однако в действительности

/7(200) = 3 972 999 029 388.

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

Действительно, 2я -f- 1 = 2 (/г — 1 ) + 3; если четное число (2п—1) есть сумма двух простых чисел, то нечетное число 2/г —f— 1 есть сумма трех простых чисел.

Теорема Гольдбаха о нечетных числах, которая проверялась в сотнях тысяч отдельных случаев, оставалась недоказанной до наших дней. Академику, Герою Социалистического Труда, Ивану Матвеевичу Виноградову (рожд. 1891 г.) удалось доказать ее для достаточно больших чисел. Предположение о том, что всякое четное число есть сумма двух простых чисел, также проверено в колоссальном числе случаев, однако до сих пор нет доказательства его справедливости для всех чисел.

3. О влиянии числа наблюдений на достоверность индуктивного вывода

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

Отрицательный ответ на все эти вопросы дают математические примеры.

а) Вычислить последовательность чисел

хп = /г2 + (п — 1 ) {п — 2) (п — 3)... (я — 100).

Получаем: хх = 1, х2 = А, л;3 = 9, лг4= 16, яв = 25,... *99 = 992 = 9801, *10o = 10 000.

1 В первой тысяче 168 простых чисел.

Заключая по индукции, что хп = п*, мы сделаем ошибку, так как правило это верно лишь до числа хт, которое равно 10000, но хт равно не 1012, а громадному числу 1012 + 100 - 99 - 98 ... 2-1.

Если хп определять по формуле

хп = п* + (п — 1 ) (п — 2)... (п — 999) {п — 1000),

то первая тысяча членов последовательности хп получается по формуле xn = ncl, но

х1001 = 10012+ 1 -2.3... 1000.

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

Можно привести поразительный пример.

б) В высшей математике изучается уравнение Пелля

x* — kf~=\t

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

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

Положим, что мы не знаем, существует ли целое решение уравнения Пелля, например, уравнения:

л:2—4 729 494_у2=1.1

Попробуем решить этот вопрос индуктивным методом.

Мы имеем х* = 4 729 494у2 + 1.

Будем подставлять вместо у числа 1, 2, 3, 4... и проверим каждый раз, является ли 4 729 494у2 -f-1 полным квадратом, который дает возможность найти целое значение для X.

1 К этому уравнению приводится так называемая задача о быках, приписываемая Архимеду.

Составим таблицу значений:

Будет ли сумма полным квадратом

Продолжая эту таблицу для всех натуральных чисел

до

у = 50 549 486 234 033 074 477 819 735 540 408 986 339, мы все время убеждаемся, что для х целого значения не получается. Мы проделали количество проверок (опытов), выражающееся написанным выше труднопроизносимым 38-значным числом, и для х целого значения не получили. Казалось бы, что это число проверок достаточно большое, чтобы сказать, что х и у для рассматриваемого уравнения

.v2 —4 729 494/= 1

одновременно целых значений иметь не могут. Однако при

у = 50 549 485 234 033 074 477 819 735 540 408 986 340 X получает целое значение в виде 45-значного числа Х=109 931986 732 829 734 979 866 232 821433 543 901 088 0491.

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

Приведенные примеры убеждают нас в том, что не существует такого достаточно большого числа опытов,

1 См. А. З, Вальфиш, Уравнение Пелля, Тбилиси, 1952,

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

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

ГЛАВА II

МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

1. Индукция и дедукция в математике

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

„Самая простая истина, самым простым индуктивным путем полученная, всегда неполна, ибо опыт всегда незакончен", отмечает В. И. Ленин (Философские тетради, Госполитиздат, 1947, стр. 154).

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

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

1. Во всяком параллелограме диагонали в точке пересечения делятся пополам.

2. Прямоугольник есть параллелограм.

3. В прямоугольнике диагонали в точке пересечения делятся пополам.

Если предложение 1-е доказано, то предложение 3-е обязательно.

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

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

Это обстоятельство не должно, однако, привести к мнению об исключительном господстве дедукции в математике. Хотя преобладание дедукции над индукцией признается характерной чертой математики, но и в математике, как и в других науках, „индукция и дедукция связаны между собой столь же необходимым образом, как синтез и анализ" (Ф. Энгельс, Диалектика природы, 1949, стр. 180). Индуктивным методом намечается теорема, которая затем подвергается дедуктивному доказательству.

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

Ф. Клейн (1849—1925) (Элементарная математика с высшей точки зрения, т. I, 1935, стр. 835—836) пишет:

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

Точку зрения современной науки выражает А. Я. Хинчин, говоря: „основу математического творчества составляет синтез дедуцирующего и индуцирующего процессов", „индукция, не синтезированная с дедукцией, обращает математику в эмпиризм, не имеющий ничего общего с математикой, а дедукция, не оплодотворенная индукцией, лишает математика способности творить"; он приходит к заключению: „все здание математического анализа проникнуто индукцией, составляющей и творящей его богатство, его красоту, его ценность, подобно тому, как дедуктивная форма обеспечивает ему вечную прочность".

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

Кроме пользования неполной индукцией, в математике широко применяется так называемый „метод математи-

ческой индукции". Он представляет способ индуктивно-дедуктивного умозаключения, опирающегося на аксиому: „Если некоторое предложение Т верно для натурального числа m (нередко принимается m = 1 или m = 0) и если из предположения о том, что предложение Т верно для натурального числа к, где k^>m, вытекает, что предложение Т верно и для n = k-^-l, то предложение Г верно для любого натурального числа".

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

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

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

Из этого свойства натуральных чисел вытекает: Если какое-либо множество их

1) заключает натуральное число а,

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

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

Рассмотрим вопрос, интересовавший уже древних: чему равна сумма п первых нечетных чисел натурального ряда

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

Напрашивается мысль: сумма п первых нечетных чисел натурального ряда для любого п равна /г2.

Этот вывод, сделанный на основании наблюдений нескольких частных случаев, нельзя считать доказанным

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

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

Действительно, он проверен для п=1, 2, 3, 4. Если он верен для п =4, то в силу доказанного перехода от k к закон верен и для п = 5. Так же выводим справедливость его для следующих значений п = 6, 7, 8... до бесконечности.

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

На основании наблюдений мы сделали догадку о том, что сумма п первых нечетных чисел натурального ряда равна квадрату числа слагаемых нечетных чисел, то есть:

1+3 + б + ... + (2/г— 1) = п\ *

Надо доказать, что равенство (*) имеет место для всех натуральных чисел п.

I. При п=\ имеет место равенство:

1 = 12 = 1.

П. Делаем предположение, что равенство имеет место

для П = к\

1+3 + 5 + ... + (2£— \) = k\

III. Если удастся доказать, что из предположения (II) вытекает существование соответственного равенства для k-\-1 слагаемых, то этим доказано равенство (*) для всех натуральных значений /г, т. е. этим доказано наше предположение.

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

1+3 + 5+... + (2£— 1) = £2 вытекает равенство

1+3 + 5 + ... + (2£-1) + (2£ +!) = (£+1)*.

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

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

Так как равенство (*) имеет место при /1=1, то в силу доказанного оно имеет место для п = 2, 3, 4 и т. д. до бесконечности.

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

1) Доказать, что для всякого натурального п

(*)

I. Для п=\ равенство имеет место:

И. Предполагаем, что равенство (*) имеет место для n = k\

III. Докажем, что из предположения (II) вытекает существование равенства (*) при n = k-\-l, то есть, что

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

Для всякого натурального п

2) Доказать, что для всякого натурального п

1) 2k—1 есть /г-ое, 2/г —|— 1 есть k -\- 1-ое нечетные числа натурального ряда.

I. Для n=\ равенство (*) имеет место:

II. Предполагаем, что равенство (*) имеет место при n = k:

III. Докажем, что из этого предположения вытекает существование равенства (*) для n = k-\-l, то есть, что

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

Итак, для всех натуральных п

Предлагаем в качестве примеров для упражнения в применении метода математической индукции и для справок несколько из найденных математиком XVII в. Фаулхабером (1580—1635) равенств:

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

I. К проверке того, что доказываемый факт имеет место при п—\\

II. К предположению, что доказываемый факт имеет место для n = k\

III. К доказательству теоремы: если предположить существование доказываемого факта при n = kf то он имеет место и при n = k-\-l. Убеждение нас в истинности доказываемого факта целиком зависит от третьего момента, который представляет дедуктивное доказательство определенной теоремы и не является применением индукции.2

Доказательство перехода свойства рассматриваемого соотношения от k и k -f-1 представляет как бы переход от k-ой ступени лестницы на А-)-1-ую.

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

Первый пример. Выскажем заведомо неверную „теорему":

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

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

Прибавляя к обеим частям предположенного неравенства по 1, мы получим неравенство k-\- \^>k-\~2.

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

1 Фаулхабер довел эту таблицу до сумм семнадцатых степеней.

2 А. Н. Колмогоров. Метод математической индукции, БСЭ.

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

Второй пример. Положим, что при некотором целом k произведение

1 -2-3 ... (k — \)-k (*)

есть число иррациональное.

В таком случае и произведение

1 -2-3... (А—

есть число иррациональное, так как мы иррациональное число (*) умножили на целое число k-\-\. Мы выполнили II и III моменты применения метода математической индукции, показали, что из предположения о существовании некоторого свойства произведения (*) при n = k (иррациональности произведения) вытекает наличие этого свойства у произведения при n = k-\- 1,

Однако мы не доказали этим, что произведение 1 .2-3 ... (А — 1). п является иррациональным числом, так как мы не установили, что при каком-нибудь натуральном значении п это произведение является иррациональным, и не можем этого установить, так как это заведомо неверно.

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

Рассмотрим последовательность

Допустим, что мы высказали гипотезу

(*)

При п=1 равенство (*) имеет место:

Попытаемся из предположения равенства (*) для п = = k, т. е. из предположения ofe = 3^_j_ 1 , вывести существование его при n = k-\-\, т. е. доказать, что Sk+1 =

Из допущения существования равенства (*) для п = = k не вытекает существование его при n = k-\-\\ формула (*) неверна; верным является равенство Sn = 1 .

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

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

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

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

Указания разных авторов на то, что доказательство методом математической индукции имеется у Евклида, являются лишенными основания. Нет этого метода в современном смысле слова и у мессинского математика Мавролико (1494—1575), часто называемого творцом

метода математической индукции, так как Мавролико ограничивается установлением правильности рассматриваемого равенства для п = 2, 3, 4 и указанием „и так далее до бесконечности", что является заключением по аналогии, как и у Евклида.

В современном понимании метод математической индукции впервые появляется у Паскаля (1623—1662).

ГЛАВА III

ПРИМЕНЕНИЕ МЕТОДА МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ В ШКОЛЬНОМ ПРЕПОДАВАНИИ

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

Надо доказать, что

(*)

I. Равенство имеет место для п=1 и п = 2;

II. Предполагаем справедливость формулы для n = k:

Вводим для сокращения письма обозначение Sk для суммы всевозможных попарных произведений из а,, а2, .. „ ak. Тогда

III. Надо доказать, что

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

Последние два слагаемых представляют сумму всевозможных удвоенных попарных произведений чисел 01, #2>---> ak> ak+\> так как $k содержит сумму всех таких произведений чисел аи аъ ak, а последнее слагаемое дает сумму всех удвоенных произведений слагаемых аи а2, ak на ak+i.

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

2. л-ый член арифметической прогрессии ап вычисляется по формуле:

an=ax + d(n— 1). (*)

(at —первый член, d— разность прогрессии).

I. Равенство (*) имеет место при п=\\ ах = а\-\-+ d(l_l) = fll.

П. Предполагаем, что при n = k равенство (*) имеет место:

ak = at + d(k — 1).

III. Доказываем, что это равенство имеет место и при я = А-|-1, т. е., что ak+1 = a1-\-dk.

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

ak+l = ak-\- d = ax -\-d(k — l)-j-d = a1 -\-dk.

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

3. я-ый член геометрической прогрессии ап вычисляется по формуле

an = a1qn-i (*)

(ах — первый член, q — знаменатель прогрессии).

I. Равенство (*) имеет место при п=1:

а, =а1<7° = а1.

II. Предполагаем, что око имеет место при n = k\

III. Доказываем, что равенство (*) имеет место и при n = k-\-], т. е., что ам = а^1г.

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

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

I. Формула верна для п=1:

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

III. Докажем, что она верна для n = k-\-l, т. е. что

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

Итак, формула (*) верна для всех натуральных /г. 5. Сумма п первых членов геометрической прогрессии выражается формулой

I. Формула (*) верна для п=1:

II. Предполагаем справедливость формулы (*) для n = k, т. е., что

III. Докажем, что она зерна и для n = k\ 1, т. е., что

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

Формула (*) верна для всех натуральных /г. 6. Число перестановок из п элементов может быть вычислено по формуле

.2-3 .../г = /г! (*)

(п — натуральное число).

I. Формула (*) верна при n=l: Р1 = 1\ = 1.

II. Предполагаем, что она верна при n = k: Pk = k\

III. Докажем, что она верна и при n = k-\-1, т. е. что

PM = (k+l)l

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

Положим, что мы составили всевозможные перестановки из k элементов. Число их Pk = k\ В каждой из перестановок по k элементов ставим (А-{-1)-й элемент перед первым элементом и за каждым из k элементов. Из каждой из k\ перестановок по k элементов образуется (k-\-l) перестановок по (A-f- 1) элементов, и мы получим k\ \k-\-1) = (А-|- 1)! перестановок по (А+1) элементов,

Среди полученных перестановок из (А-)-1) элементов не может быть одинаковых, так как при допущении этого по удалении элемента аш остались бы две одинаковые перестановки из k элементов, что противоречит нашему предположению о том, что мы сначала имели все возможные перестановки из k элементов и только эти перестановки, различные между собою.

Полученные {k-\-1)! перестановок из (А+ 0 элементов включают все возможные перестановки из (k-{-\) элементов. Допустим, что отсутствует перестановка из (А+ 1) элементов, в которой элемент ak+l стоит на определенном, скажем, на первом месте. Такая перестановка не может отсутствовать, так как без элемента аш эта перестановка представляет перестановку из k элементов, а мы брали

все перестановки из k элементов и помещали в них ak+1 на всех возможных местах, в том числе и на первом месте. Следовательно, перестановка с элементом аш на первом месте, которую мы предполагали отсутствующей в числе (Ä-j- !)•' составленных нами перестановок из (&-J- 1) элементов, должна была находиться в числе их.

Итак,/\+1 ={k-\-1)! и формула Рп = п\ доказана для всех натуральных чисел п.

7. Число размещений из m элементов по п вычисляется по формуле

А% = т{т—\){т — 2) ... (т — (*)

где п^т, п и m — натуральные числа.

I. Формула (*) верна при п=1: Ат = т.

И. Предполагаем, что формула (*) верна при n = ky т. е., что при k<^m

Akm = m(m— \){т — 2) ... {m — k-\-1).

III. Докажем, что формула (*) остается верной и для n = k-\- 1, т. е., что

А%г = т(т— \){т — 2) ... (m — k-\-X){m — k).

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

Положим, что составлены все размещения из m элементов по k, где k<^m. Чтобы составить все размещения из тех же m элементов по k -f-1 элементов в каждом, присоединим ко всем Am размещениям по k элементов каждый из остальных (т — k) элементов, не входящих в данное размещение из k элементов.

Пример. Пусть имеем четыре элемента, обозначенные цифрами 1, 2, 3, 4, и составлены все размещения из этих четырех элементов по два; их, согласно предположению, будетЛ4 = 4 - (4 — 2+1) = 4.3=12;они суть 12,13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43.

Для каждого размещения остаются неиспользованными из четырех элементов два, которые, каждый в отдельности, присоединяем к имеющимся размещениям по два элемента. Имеем: 123, 124, 132, 134, 142, 143, 213, 214, 231, 234, 241, 243, 312, 314, 321, 324, 341, 342, 412, 413, 421, 423, 431, 432.

Все полученные размещения различны, и их 12 • 2 = 24, т. е. Л!-(4 —2) = 4.3-2.

В общем случае такими же рассуждениями получаем число размещений из m элементов по (к-{-1), равным Ат (m — k), т. е.

Akm+l= Akm(m — k) = m(m— l)(m — 2) ... ... (m — k + 1) {m — k).

Все полученные таким способом размещения, по (k + 1) элементов из т, различны, так как любые два размещения отличаются друг от друга или в первых k элементах, если они образованы от различных размещений по k элементов, либо последними элементами, если они образованы присоединением к одному и тому же размещению из k элементов одного из остальных (т — k) элементов. В числе образованных размещений по элементов содержатся все возможные размещения по (&-J-1) элементов из т. Допустим, что существует размещение из (k-\-l) элементов, не вошедшее в множество размещений, образованных нами. В таком случае мы либо не исходили от множества всех размещений по k элементов, либо не присоединяли к каждому из размещений из k элементов по порядку все остальные (т — к) элементов. То и другое допущение противоречит условию.

8. Число сочетаний из m элементов по п выражается формулой

(*)

где п^т, m и п — натуральные числа. I. Формула (*) верна для п= 1:

II. Предполагаем справедливость формулы (*) для n = k, т. е. предполагаем, что

III. Докажем, что в таком случае формула (*) верна и для n = k-\-\, т. е., что

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

Для получения всех сочетаний из m элементов по (k А- 1) представим выписанными все сочетания из m элементов по k и к каждому такому сочетанию в качестве (k-\- 1)-го элемента присоединим каждый из m — k элементов, которые в данное сочетание по k элементов не входят. Таким путем мы получим всего Ст- {р1 — k) сочетаний из m элементов по но эти сочетания будут не все различными, а каждое возможное сочетание из m элементов по (k-\-l) повторено (A-f-1) раз.

Рассмотрим для примера образование всех сочетаний из 6 элементов по 3.

Пусть составлены все Сб = ут2= ^ сочетаний из 6 элементов по 2: ах а2, ах а3, аг а4, ах ай, ах а6, а2 а3, а2 а4, а2 ав, а2 а6, а3 а4, а3 а5, а3 а6, а4 а5, а4 а6, а5 а6.

Присоединим к первому сочетанию ах а2 элемент а3; получим сочетание а{ а2 а3. То же сочетание ах а2 а3 мы получим, присоединив ко второму сочетанию ах аг элемент а2 и присоединив к шестому сочетанию а2 а3 элемент ах. Из всех остальных сочетаний по 2 элемента присоединением какого угодно остального элемента сочетание ах а2 а3 не образуется. Таким образом, присоединяя ко всем сочетаниям из 6 элементов по 2 элемента по порядку все оставшиеся элементы, мы получим все возможные сочетания из 6 элементов по 3 элемента, но каждое сочетание повторится 3 раза. Следовательно, число сочетаний

В общем случае, присоединяя к каждому сочетанию из m элементов по k каждый из не входящих в данное сочетание (т — k) элементов, мы получим всего Ст-(т — k) сочетаний по (А+ 1) элементов в каждом, но каждое возможное сочетание из m элементов по (А -)— 1 ) элементов повторяется среди образованных Скт (т — Щ сочетаний {k -\-1) раз.

Это очевидно из следующего рассуждения.

Удаляя из сочетания ах а9 а8 ... ak ak+u состоящего из (&+1) элементов, по одному элементу, мы получим всего сочетаний из k элементов а2а3 ... akak+u

ах а3 а4... ак аА+1,..., ах а2... ак.

Обратно, имея все возможные сочетания из каких-нибудь (я-f- 1) элементов по k напр. сочетания а2 а3... ak ak+1, ata3 ... ak ak+1, аха^ ... ak и присоединяя к каждому из них отсутствующий в нем элемент из числа элементов аи аъ а3, ... ak, аш, мы получим (k -f-1) раз одно и то же сочетание аха^ ... ak аш, состоящее из (k -[- 1) элементов.

Итак, для получения числа различных сочетаний из m элементов по (k-\-\) элементов, надо полученное число сочетаний Ckm(m — k) уменьшить в (k-\-\) раз и

Формула (*) доказана для всех натуральных чисел тип при п^т.

9. Для всяких чисел а и b и любого натурального числа п имеет место равенство

(*)

I. Равенство имеет место при п—\\ {a-\-b)x = a-\-b}

П. Предположим справедливость формулы для n = k} т. е. предполагаем, что

III. Докажем, что (a-|-ô)fe+1 выразится той же формулой, в которую вместо k поставлено

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

1 Здесь надо избежать ошибки, которая приводит к известному софизму. Если в формулу (,|:) подставить механически вместо п единицу, то получим (считая С°п = 1)

(а + Ьу = а + с\аЧ + с°аЬ° + b = а + Ь + а + Ь = 2 (а + Ь), откуда, при условии, что а-\~Ь^Ь0, имеем 1=2. Надо помнить, что (а-\-Ь)п по формуле (*) имеет п-\-\ член, поэтому (а-\~Ьу имеет только два члена: первый и последний по формуле (*), и (а + ЬУ = а + Ь.

Так как

Формула (*) верна для всякого натурального числа п. Её, так называемую формулу бинома Ньютона, можно вывести, не вводя символов С», а обозначая коэффициенты через

10. Разность одинаковых степеней двух чисел всегда делится на разность этих чисел, т. е., при натуральном п всегда ап — Ьп делится на а — Ь. (*)

I. Для п=\ наше утверждение верно: а — b делится на а — Ь.

П. Предполагаем, что утверждение имеет место для n=ky т. е. предполагаем, что ак — bk делится на а — Ь.

III. Докажем, что в таком случае и ak+1 — bk+1 делится на а — 6.

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

Первое слагаемое правой части равенства делится на а — 6, второе слагаемое делится на а — b в силу предположения (II). Если каждое слагаемое делится на а — Ьу то и сумма их ak+1 — bk+1 делится на а — Ь. Итак, ап — Ьп делится на а — b при всяком натуральном п.

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

11. Теорема Безу: многочлен я-ой степени

при делении на х— b дает в остатке результат подстановки в этот многочлен числа b вместо х, т. е. / (Ь), равный

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

I. Теорема верна при п—\\ для многочлена первой степени fl(x) = a0xJraî имеем:

Остаток при делении многочлена fi(x) = a0x-\-al на х-b равен f1(b) = aQb-\-al.

II. Предполагаем, что теорема верна для многочлена степени k:

т. е. предполагаем, что остаток от деления fk{x) на х — b есть Д ф) = a0bk + а^*"1 + ... + ак_хЬ + ak.

III. Докажем, что при таком предположении теорема будет верна и при n = k-\-l, т. е., что при делении многочлена на X — b остаток будет равен

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

Так как в силу допущения II fk(x) при делении на х-b дает остаток fk(p), иными словами,

Л (*)=(*-ft) им (*)+/»(*).

(где qk-i(x) — частное от деления fk{x) на х—Ь), то предпоследнее равенство можно переписать так:

Первое слагаемое правой части последнего равенства делится на л: — Ь, поэтому остаток от деления/м (х) на X — b совпадает с остатком от деления на х — b

выражения xfk(b)-\-ak+l. Это выражение есть многочлен первой степени. В пункте I установлено, что остаток от деления такого многочлена на х—b равен результату подстановки в многочлен вместо х числа 6, т. е., что остаток есть bfk(b)-\-aM.

Следовательно, остаток от деления fk+i(x) на х — b равен bfk (b) + ak+1 = aQbk+1 + a,bn +... -f ak_xb + ak+l =

Теорема Безу доказана методом математической индукции.

12. Доказать, что для любого натурального значения п

|aj + a8+ ...+ая|<|а1|-На8| + ... + \ап\. (*)

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

I. Для двух слагаемых неравенство (*) имеет место: ах и а2 могут быть или одного или разных знаков; в первом случае имеем

| ах -f- а21 = | at \ -f-1 а21, во втором |ai-f ав|<|а, | + | а8|.

И. Предполагаем справедливость неравенства (*) для п= k слагаемых, т. е., предполагаем, что

I (h + а8 +... + ак I < I а, | +1 а, | + ... +1 ак \.

III. Докажем, что неравенство (*) имеет место и при n = k-{-1, т. е., что

|ai + a8+ + % +аЛ+11<| а, | + |а8|+ ... +|aft| +

Действительно, И1 + а9+ ... +аА + аЛ+1|==|(а1 + аа + ... +аА) + ай+1|^ ^|а, + а2 + ... +ая | + | а/г+11^| ах | + |а2|+ ... + +1 я* I +1 %+i I

Неравенство (*) имеет место при любом натуральном значении /г.

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

(1+а)*>1+/ш, (*)

где а^>—1 и а^О, я — натуральное число, большее 1.

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

I. При п = 2 неравенство имеет место: (l-f-a)2 = = 1+2а + а2>1+2а.

II. Предполагаем, что равенство имеет место при n = k, т. е., что (1 -\-а)к^> 1 -\-ka.

III. Докажем, что неравенство в силу предположения (II) имеет место и при n = k-\-l, т. е., что

(1 + а)*+1>1 + (£+1)а.

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

Так как &а2>0, то (1 + а)*+1>1 +(*+ 1)а. Неравенство (\-\-а)п^>\-\-па имеет место для всех натуральных значений п при а^>—1 и а^О. 14. Имеем равенства:

Возникает догадка, что

(2/г-1)2 = /г + (/г+1) + (/г + 2)+...+ (3^-2). (*)

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

I. Для ;г = 1 равенство (*) имеет место:

12 = (2 -1 — 1)*=1.

II. Предполагаем, что для n = k имеем

III. Докажем, что для n = k-\-\ равенство (*) имеет место, т. е., что выражение [2(k-\-l)— I)]2 или (2&-|-1)2 равно сумме натуральных чисел от k-\-l до числа 3(k-\-l) — 2 или 3k-\-l. Иными словами, докажем, что

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

Сумма

Равенство (*) имеет место для всех натуральных п.

Примечание. В этом примере, для того чтобы иметь возможность использовать допущение II, нужно было в правую часть доказываемого равенства ввести + £ и — k\ после такого преобразования получается выражение, стоящее в квадратных скобках, которое совпадает с правой частью предположенного равенства П. При применении метода математической индукции в доказываемом равенстве (III) приходится часто делать подобные тождественные преобразования, так как предположение (II) является во всех случаях основою последующего доказательства (III).

15. Имеем равенства:

13 — 1, 23 = 3 + 5, 33 = 7 + 9+11, 43= 13+ 15 + + 17+19 и т. д.

Возникает догадка:

n* = (n*-n+l)+[(n*-n+l) + 2] + [{n*-n-\-l) + + 4] + ... + [(/г2 - п +1) + 2(л - 1)]. (*)

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

Последнее слагаемое правой части равенства (*) после раскрытия скобок принимает вид

я2 — я+ 1+2(я— 1) = я2 + я — 1.

Первое слагаемое рассматриваемой суммы /г2 — п + 1 представляет при всяком натуральном п нечетное число.

Действительно, его можно представить в виде п(п—1)+1. Число п(п—1) при п натуральном является четным числом, как произведение двух последовательных натуральных чисел, одно из которых число четное. Нечетными числами являются и все другие слагаемые правой части равенства (*), так как они получаются прибавлением к нечетному числу я2 — п + 1 четных чисел 2, 4, 6, ... , 2 (п— 1).

Таким образом равенство (*) утверждает, что куб всякого натурального числа (я3) равен сумме всех нечетных чисел натурального ряда от ri* — #+ 1 до я2 + я— 1.

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

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

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

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

ГЛАВА IV

НЕКОТОРЫЕ ДОПОЛНИТЕЛЬНЫЕ ЗАМЕЧАНИЯ О ПРИМЕНЕНИИ МЕТОДА МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

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

Вопрос 1. При каких натуральных значениях п имеет место неравенство

2*>/г? (*)

I. При п—\ неравенство (*) имеет место: 2>1.

II. Предположим, что оно имеет место при n = k, т. е. что 2k^>k.

III. Докажем, что отсюда вытекает неравенство 2* + 1>А+1.

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

2k + 1 = 2 • 2k ]> 2k (по предположению II);

2k = k-\-k^>k-\-\ при всех значениях £, больших 1, поэтому 2k + 1 > k -f-1.

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

Вопрос 2. При каких натуральных значениях п имеет место неравенство

2л>л2? (*)

I. При /г=1 неравенство (*) имеет место: 2>1.

II. Предположим справедливость неравенства (*) при n — ky т. е. предположим, что 2k^>k*.

III. Вытекает ли из этого предположения, что 2* + 1>(£+ 1У2?

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

2fe + 1 = 2.2fe>2-£2 (по предположению II).

Неравенство пункта III будет иметь место, если 2*8>(А+1)8, или, что то же, если £2 + £2>£2 + 2А+ 1, или £2>2£ + 1, или *>2 + -у- , где А — натуральное число, большее 1.

Из последнего неравенства следует, что k натуральное число, не меньшее 3, т. е. А^З.

Итак, неравенство 2k + 1^>(k-\- I)2 может иметь место лишь при необходимом условии &^3.

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

/г = 3; 23 = 8 <^ З2 = 9; неравенство (*) не удовлетворяется; Л = 4; 24= 16 = 42= 16;

п = б; 25 = 32 > 52 = 25; неравенство (*) удовлетворяется.

Итак, неравенство 2л^>/г2 имеет место для всех натуральных значений п ^5. Кроме того, неравенство имеет место еще при /1=1.

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

2я>л3? (*)

I. При п—\ неравенство (*) справедливо: 2]>1.

II. Предположим его справедливость при n — k, т. е. полагаем 2k^>k*.

III. Вытекает ли отсюда, что неравенство (*) имеет место при n = k-\-l, т. е. что 2fe+1^>(é-j-I)3?

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

2fe+1 = 2-2fe>2&3, (по предположению II).

Неравенство пункта III имеет место, если 2/г3>(&-|- I)3, или, что то же, если k* + k3># + 3£* + + 3Ä+1, или £3>3£2 + 3£+1, или £>3 + -~ + ~.

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

Надо проверить, все ли значения я, начиная с п = 4, удовлетворяют неравенству 2л^>я3.

п = 4 9 24 = 16 < 43 = 64; неравенство(*) не удовлетворяется

/г=10,210==1024> 103= 1000; неравенство (*) удовлетворяется.

Итак, неравенство Т^>пъ удовлетворяется всеми натуральными значениями п, начиная с #=10; кроме того оно удовлетворяется и при п=1.

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

б) Во всех рассмотренных случаях применения метода математической индукции мы для получения общего вывода применяли переход от k к k-\- 1.

Иногда для той же цели применяется переход от k к к — 1.

Таким образом Коши (1789—1857) доказывает теорему: Среднее геометрическое п положительных неравных чисел меньше их среднего арифметического:

(*)

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

I. 1) Теорема (*) верна для п = 2:

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

2) Теорема (*) верна для п = А:

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

Для двух положительных чисел (корни арифметические) У их • а2 и У а3 • а4 , по доказанному, имеем

откуда и подавно

или

Повторяя такое же рассуждение, убеждаемся, что теорема (*) верна для п = 8, 16 и так далее, вообще для п = 2к положительных неравных чисел, где k — натуральное число.

II. Докажем, что если теорема (*) верна для 2k чисел, то она верна и для 2k — 1 чисел.

Обозначив 2k через /7 —j— 1, докажем, что если теорема (*) верна для р + 1 чисел, то она верна и для р чисел.

Имеем тождество

(подкоренное выражение в правой части равенства есть

и вся правая часть обращается в

Так как, по предположению, теорема (*) имеет место для р-\-1 чисел, то из (**) имеем

откуда

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

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

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

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

Наблюдения дают для двух точек один отрезок, для трех точек 3, для четырех точек 6 отрезков.

Предполагаем, что для п точек необходимо Un = —Ц>—- отрезков.

I. Для п = 2 догадка верна: 2 = —^- = 1.

II. Делаем предположение, что формула верна для n = k точек, т. е. что uk = —±—^—L.

1 Здесь (р-{-\)-м числом является

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

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

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

Isin/гл:| ^п \ sinx\ (*)

при п натуральном.

I. При п=\ соотношение (*) имеет место.

II. Предположим, что соотношение (*) имеет место при n — k\

I sin kx I I sin X |.

III. Докажем, что соотношение (*) имеет место и при n = k-\- 1, т. е., что

J sio (/г —f- 1)л:| ^(А+ 1)| sin х\.

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

Примечание. Неравенство

I sin kx I • I cos XI +1 cos kx I • I sin x \ \ sin x \ + sin x\

имеет место всегда, так как |cosx|^l и |cosAx|^l и от замены таких множителей единицами выражение не уменьшится.

Итак, соотношение (*) имеет место при всяком натуральном п.

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

несколько примеров параллельно и другими способами. Приведем пару таких примеров.

1. Доказать, что выражение 3 • 52n+1 -{- 23n+1 делится на 17 при всяком натуральном я.

Решение 1. Имеем сумму двух слагаемых, в которые входят различные степени чисел 5 и 2. Из алгебры известны теоремы о делимости сумм и разностей одинаковых степеней двух чисел на суммы и разности этих чисел. Среди этих теорем имеем единственную, утверждающую делимость при всяких натуральных показателях (независимо от четности или нечетности их), именно: разность одинаковых степеней двух чисел всегда делится на разность этих чисел. Отсюда мы получаем указание, что для доказательства надо преобразовать данную сумму в разность одинаковых степеней двух чисел, притом таких, разность которых равна 17. Числа, разность которых равна 17, должны составляться из оснований данных в задаче степеней, т. е., из 5 и 2. Замечаем 52 — 23 = 25— — 8=17. Значит, нам следует стремиться преобразовать данную сумму 3 • 52Л+1 -|- 23/г+1 так, чтобы выделилась разность 25* — 8* = (5*)* - (23)*.

Поступаем следующим образом.

17-25я делится на 17; 25" — 8п также делится на 25 — 8=17, следовательно, и 3 • 52n+1 + 2гп+1 делится на 17.

Решение II. Доказать, что

(*)

делится на 17 при всяком натуральном п.

I. При п=1 имеем 3-53 + 24 = 375 +16 = 391 = = 17-23.

II. Предположим, что утверждение (*) верно при n=k, т. е., что 3 • 52fe+1 _j- 23fe+1 делится на 17.

III. Отсюда вытекает делимость и при n = k-\-l. Действительно:

Первое слагаемое делится на 17; второе — делится на основании предположения И, следовательно, делится на 17 и сумма их. По методу математической индукции утверждаем справедливость свойства (*) при всяком натуральном /г.

Указание. Для доказательства того, что из предположения правильности некоторого утверждения при n = k вытекает правильность для n = k-\-l, из полученного при n = k-\-\ выражения нужно выделить часть, совпадающую с соответственным выражением при п = k, для которой утверждение предполагается верным, и рассмотреть оставшуюся часть. Этим указанием надо руководствоваться при выполнении третьего момента применения метода математической индукции.

2. Доказать, что выражение

_|_ j j Зл+1 ^

делится на 17 при всяком натуральном /г.

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

Решение II. Требуется доказать, что б"*3 -f- 113,1+1 делится на 17 при всяком натуральном п.

I. При п=1 данное выражение делится на 17:

54+ 114 = 625 + 14 641 = 15 266= 17-898.

II. Предполагаем, что при n = k делимость имеет место:

5fe+3+ll3fe+1 делится на 17.

III. Докажем делимость при n = k-\-l:

Мы доказали, что из предположения, что данное выражение делится на 17 при n = k, вытекает делимость и при n = k-\-l.

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

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

Доказательство I. Составим таблицу.

В первом ряду стоят числа натурального ряда от 1 до /г, в дальнейших рядах удвоенные, утроенные и т. д., /7-кратные и наконец /г-кратные чисел натурального ряда.

Обозначим сумму чисел первой строки через N.

Суммами чисел строк будут N,2N,3N9..., nN.

Общая сумма чисел в рассматриваемом квадрате

Наша таблица разрезана на „наугольники". Сумма чисел, стоящих в р-м наугольнике, равна:

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

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

I. При п=\ равенство (*) имеет место:

II. Предполагаем справедливость равенства (*) при n = k;

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

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

По методу математической индукции имеем для любого натурального п

д) Ученик из наблюдений:

сделал заключение, что

при всяком

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

и что

вообще

при любом числе корней и с^>0, ученик пришел к теореме:

Доказать, что для с^>0

(*)

при всяком числе п корней в заданном сложном радикале. I. При п=\ неравенство (*) имеет место:

II. Предположим, что оно имеет место для n = k:

(k корней).

III. Надо доказать, что неравенство (*) имеет место при n = k-\-l, т. е., что

Обозначим

Тогда по предположению (II) выражение принимает вид

то есть,

Итак, неравенство (*) доказано для любого числа п корней.

ГЛАВА V

ПРИМЕРЫ И УПРАЖНЕНИЯ

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

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

1. Найти выражение суммы

1.2 + 2-3+3-4+...+/г(/г+1)

для произвольного натурального значения п. Решение. Делаем наблюдение:

1-2 = 2, 1-2 + 2.3 = 8, Ь2 + 2.3 + 3-4 = 20.

Замечаем, что

Высказываем гипотезу, что

Доказать или опровергнуть эту гипотезу.

I. Равенство (*) имеет место при п=1:

II. Предполагаем, что при n = k равенство (*) удовлетворяется, т. е. предполагаем, что

III. Докажем, что равенство (*) имеет место и при n = k -\-1, т. е., что

На основании предположения II

Предположение (*) оправдано для всех натуральных значений /г.

2. Таким же образом доказывается равенство

3. Найти выражение суммы

для произвольного натурального значения /г.

Решение. Мы наблюдаем, что

Высказав предположение, что

(*)

будем искать доказательства или опровержения нашего предположения (*).

I. При п = 1 равенство (*) имеет место:

II. Предлолагаем, что пру n = k равенство (*) остается в силе, т. е., что

III. Докажем, что в силу этого предположения равенство (*) имеет место и при n = k-\-l, т. е., что

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

Равенство (*) имеет место для всех натуральных значений ft,

4. Таким же образом доказывается равенство

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

(*)

найденное в начале XV в. узбекским математиком Джемшидом эд-Дин ал-Каши.

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

I. Равенство (*) имеет место для п—\\

II. Предполагаем, что оно имеет место для n — k\

III. Докажем, что равенство (*) остается в силе и при n = k-\-\\

Используя сделанное предположение, имеем:

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

или

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

Формула (*) имеет место для любого натурального числа п.

6. Доказать, что для любого натурального п имеем:

(*)

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

I. Для п=1 равенство (*) имеет место:

II. Предполагаем, что равенство (*) имеет место при n = k:

III. Докажем, что равенство (*) имеет место и при п = к-\-1:

Действительно, на основании предположения II имеем:

Равенство (*) доказано для всех натуральных значений п.

7. Для каких натуральных значений п имеется неравенство 2*>/z4? (*) Решение.

I. При /г=1 неравенство (*) имеет место: 21>14.

И. Предполагаем, что неравенство (*) удовлетворяется при n = k, т. е., что 2fe>£4.

III. Установим, при каких значениях k будет удовлетворяться неравенство

2/г + 1>(£+1)4. (**)

2fe + 1 = 2-2fe>2Ä4 (по предположению II).

Для удовлетворения неравенству (**) необходимо, чтобы было 2£4^(£+1)4, т. е. 2£4^£4 + 4£3 + + 6£2 + 4£+1.

Так как k^> 1, то

и для удовлетворения неравенству (**) необходимо, чтобы было

Проверка показывает, что для значений /г = 15 и для п =16 неравенство (*) не имеет места и что оно удовлетворяется для значений /г^17 и, кроме того, для п=1.

8. Является ли при натуральном значении п выражение п^п~2 ^ + — 3/z -f- 2 суммою п первых чисел натурального ряда

1+2 + 3+.. .+»? (*)

I. Для п= 1 и п = 2 ответ на вопрос утвердительный.

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

III. Выясним, следует ли из (*), что предполагаемое равенство имеет место и при n = k-\-l, т. е., что

При допущении сделанного предположения мы имели бы

Полученный результат не совпадает с тем, который должен был бы получиться при предположении, что данное в задаче выражение является суммой чисел 1 -f- 2 -f-+ ... 4" À + (A -f-1). Из предположения о справедливости формулы для n = k не вытекает справедливость ее для /г = А-{-1. Предполагавшаяся формула для суммы 1 —1— 2 —J— 3 —J— ... —J— оказалась неверной.

9. Имеет ли при натуральном значении п место равенство

(*)

I. При п=1, 2, 3 равенство (*) имеет место.

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

III. Выясняем, вытекает ли из этого предположения, что равенство (*) имеет место при n = k-\-\ , т. е., что существует равенство

По предположению II имели бы

Результат не совпадает с ожидавшимся; из предположения II не вытекает применимость формулы (*) при n = k-\-\. Предполагавшееся выражение для суммы неверно.

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

(л+1)(л + 2) ... (п + п) = 2п-\'Ъ-Ь-7 ...(2п—1).(*)

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

1. Равенство (*) имеет место для п=1:

2 = 2-1=2.

2. Предполагаем, что равенство (*) имеет место для n = k: (Ä+l)(A + 2) ... (£-Н) = 2/г-1-3-5 ... (2k— 1).

3. Докажем, что оно имеет место и для n = k-\-l1 т. е., что

По допущению II имеем:

Равенство (*) имеет место для всех натуральных п.

11. Доказать, что для всякого натурального числа п и для значений х, удовлетворяющих условию |л:|^1, имеет место равенство

(*)

I. Равенство (*) имеет место для п=1:

1 Переход сделан умножением и делением предыдущего выражения на одно и то же число (k -f-1).

II. Предполагаем существование равенства (*) при n = k:

III. Докажем, что равенство (*) остается в силе и при n = k-\-l, т. е., что существует равенство

По предположению II имеем:

Равенство (*) имеет место для всех натуральных п. 12. Доказать, что

(*)

для любого натурального п и при условии, что

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

1. При п=1 равенство (*) имеет место

II. Предполагаем существование равенства (*) при n = k:

III. Докажем, что равенство (*) остается в силе и при n = k-\-1, т. е., что

На основании предположения II имеем:

Остается убедиться в том, что правые части последних двух равенств совпадают, т. е., что

или, после замены sin {k-\-1) а через

или что

Это равенство имеет место, так как

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

Итак, равенство (*) доказано для всех натуральных значений п.

13. Доказать, что тождество

имеет место при всех целых

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

I. При п = 0 и п = 1 тождество (*) имеет место:

II. Предполагаем, что тождество (*) имеет место при n = k:

III. Докажем, что тождество остается в силе и при п = A4-1, что

На основании предположения II имеем:

Тождество (*) доказано для всех целых

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

(*)

{п — натуральное число, sin* ф 0).

Доказательство. I. При я=1 равенство (*) имеет место:

II. Предполагаем, что равенство (*) имеет место при n = k:

III. Докажем, что равенство (*) удовлетворяется и при п = к-\-\, то есть докажем, что

Имеем на основании предположения II:

Предпоследний переход был сделан на основании формулы

sin 2 (А + 1)х — sin 2 kx = 2 cos (2А+ 0*-sin х.

Итак, из предположения о применимости формулы (*) при n = k вытекает применимость ее и при n = k-\-1. Формула (*) применима для всех натуральных значений п.

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

(*)

(п — натуральное число).

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

I. При п=\ равенство имеет место: С)=Ь2°; 1 = 1.

II. Предполагаем существование равенства (*) при n = k\

III. Докажем, что равенство остается в силе при n=k-\-l, т. е. докажем, что

На основании известного свойства символа Cl пишем:

Складывая эти равенства по столбцам, имеем:

Формула (*) доказана для всякого натурального значения п.

16. Доказать для неравных нулю чисел а19 аъ а3, ап равенство

(*)

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

I. Равенство имеет место при п=1:

II. Предполагаем существование равенства (*) при n — k.

1 Выражение в первых скобках равно 2к по свойству биномиальных коэффициентов, выражения во вторых и третьих скобках по сделанному предположению равны каждое k • 2k~x.

III. Докажем, что равенство (*) имеет место и при n=k-\-l, т. е. докажем существование равенства

Действительно, на основании предположения II

Равенство (*) доказано для всех натуральных значений п.

17. Доказать, что для всякого натурального числа п при условии X Ф 1 имеет место равенство

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

I. Равенство (*) имеет место при п=1:

II. Предполагаем существование равенства (*) при n=k.

III. Докажем, что равенство (*) имеет место и при n — k-^-l, т. е., что существует равенство

Действительно, на основании предположения II

Равенство (*) имеет место для всех натуральных значений п.

18. Доказать для любого натурального числа п равенство

(*)

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

I. Равенство (*) имеет место для /1=1:

II. Предполагаем существование равенства (*) для 11 = k.

III. Докажем, что равенство (*) имеет место и для n = k-\-l, т. е. докажем существование равенства

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

Существование равенства (*) для любых натуральных значений п доказано.

19. Доказать существование равенства

для произвольного натурального числа п при условии, что ни одно из чисел аъ а2, ап не равно — 1.

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

I. Равенство (*) имеет место при п=1:

II. Предполагаем существование равенства (*) при n = k.

III. Докажем, что равенство (*) имеет место и при n = k-\-\, то есть, что существует равенство

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

Равенство (*) доказано для всех натуральных значений я.

20. Доказать, что при целом п^О выражение

цл+в_|_12вя+1 (*)

делится на 133.

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

I. При п = 0 выражение (*) равно 133 и делится на 133.

II. Предполагаем, что при n = k 1 lfe+2 -f- 122fe+1 делится на 133.

III. Докажем, что выражение (*) делится на 133 и при n = k-\-\.

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

Первое слагаемое делится на 133 по сделанному предположению—второе, как содержащее множитель 133, следовательно, и сумма, т. е. выражение (*) при п = = k-\-l делится на 133. Этим доказано, что выражение 1i22/I+1 делится на 133 при всяком целом п^О,

21. Доказать, что выражение

22П+ \Бп— 1 (*)

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

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

I. При п=\ выражение (*) равно 18 и делится на 9.

И. Предполагаем, что при n=k 22fe+ 15Ä—1 делится на 9.

III. Докажем, что из предположения II вытекает делимость на 9 выражения (*) при n — k-\-l, т. е., что 2«(*+i) -J- 15(ä+ 1) — 1 делится на 9.** Имеем,

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

62л + Зл+2 + 3" делится на 11. (*)

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

I. При п=\ утверждение (*) верно: б2 -f-З3-f-3 = 66.

П. Предполагаем, что при n = k

6**-f3*+*-|-3ft делится на 11. (**)

III. Докажем, что из предположения (**) вытекает правильность утверждения (*) для n = k-\-l, т. е., что 62(fe+i)_|_3(^i}+2_j_3ft+i делится на 11. (***)

Имеем

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

ГЛАВА VI

НЕКОТОРЫЕ ОТРЫВКИ ИЗ СОЧИНЕНИЙ ЭЙЛЕРА

1) Замечания об одной теореме Ферма и о других теоремах, относящихся к простым числам (Comment. Petropolit, VI, 1732, стр. 103— 107).

Известно, что величина ап -\-1 всегда имеет делители, если п число нечетное или делящееся на нечетное число, кроме единицы. Действительно, аш+1 -|-1 делится на a-f-1, а ap(2w+1)-|-1 делится на ар-\-\, какое бы число мы ни подставили вместо а. И наоборот, если п такое число, которое не делится ни на какое нечетное число, кроме единицы, как это бывает, когда п есть степень двойки, нельзя указать ни одного делителя числа ап-\-1. Поэтому, каковы бы ни были простые числа вида ал-|-1, все они заключены в форме af1 -\-\. Всё же отсюда нельзя заключить, что ат-|- 1 всегда представляет простое число, каково бы ни было а. Во-первых, очевидно, что если а число нечетное, то указанное выражение будет иметь делитель 2. Во-вторых, если даже а число четное, существует бесчисленное множество случаев, в которых получается составное число. Так, во всяком случае, а2-|-1 делится на 5, если a = 5ô±3 и 302 —|— 1 делится на 17, а 502 —f— 1 делится на 41. Равным образом 104-)-1 имеет делитель 73; 6s —J— 1 имеет делитель 17, а 6128_)-1 делится на 257. Однако для чисел вида 22/п-|-1, как показывают таблицы простых чисел, не простирающиеся, впрочем, далее 100000, нельзя обнаружить ни одного случая, в котором имелся бы какой-либо делитель. На основании этого соображения и других Ферма не поколебался утверждать, что 22 -f-1 всегда есть простое число, и предложил это для доказательства как

выдающуюся теорему Валлису и другим английским математикам. Он признается, что сам не имеет доказательства этой теоремы, но тем не менее утверждает, что она истинна. Пользу же ее он усматривает главным образом в том, что с ее помощью легко указать простое число, большее любого заданного числа, что без такого рода общей теоремы было бы чрезвычайно трудно. Об этом можно прочитать в „Переписке" Валлиса, содержащейся во втором томе его трудов, в предпоследнем письме. Также и в сочинениях самого Ферма, на стр. 115 говорится следующее: „А так как для меня очевидно, что числа, образованные от двойки последовательными возвышениями в квадрат и увеличенные на единицу, всегда будут простыми и уже давно была указана исследователями истинность этой теоремы, а именно, что простыми являются 3, 5, 17, 257, 65537 и т. д. до бесконечности.

Истинность этой теоремы очевидна, как я уже сказал, если положить вместо m 1, 2, 3 и 4; действительно, получаются числа 5, 17, 257 и 65537, которые все находятся в таблице простых чисел. Но какими-то судьбами оказывается, что ближайшее же следующее число 220 -f-1 уже не будет простым, ибо на днях, занимаясь совсем другим, я заметил, что это число делится на 641, как это станет ясно каждому, кто попытается проверить. В самом деле, 225 -[- 1=4 294 967 297. Отсюда ясно, что теорема может быть неверна и в других случаях, и таким образом задача о нахождении простого числа, большего, чем любое заданное число, остается до сих пор не решенной.

2) Доказательство некоторых теорем, относящихся к простым числам (Comment. Petropolit., VIII, 1736, стр. 141—146).

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

Повидимому, Ферма к большей части своих теорем пришел посредством индукции, которая представляет собой едва ли не единственный путь нахождения этих свойств. Однако я мог бы на многих примерах показать, как мало значения приходится придавать индукции в этих вопросах; достаточно будет привести один из этих примеров, взятый от самого Ферма. Я говорю о теореме, ложность которой я показал уже несколько лет назад, а именно о той, где Ферма утверждает, что все числа, охватываемые формулой 22Ш -|" 1, суть числа простые. Могло бы показаться, что истинность этого предложения вполне подтверждается индукцией. Ибо, помимо того, что все эти числа, меньшие чем 100000, действительно оказываются простыми, можно легко доказать, что ни одно простое число, не превышающее 600, не будет мерой (делителем) этой формулы 2^т —[— 1, сколь бы велико ни было число, подставляемое вместо tu. Но так как установлено, что это предложение не согласуется с истиной, легко понять, как мало силы имеет индукция в рассуждениях этого рода.

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

3) Употребление наблюдений в чистой математике (Собр. соч., серия 1, т. 2, стр. 459).

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

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

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

СОДЕРЖАНИЕ

Стр.

Введение .................................... 3

Глава I.

Индуктивный метод в математике.................... 6

1. Индукция и индуктивный метод.................—

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

3. О влиянии числа наблюдений на достоверность индуктивного вывода...........................12

Глава II.

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

1. Индукция и дедукция в математике.............. —

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

Глава III.

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

Глава IV.

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

Глава V.

Примеры и упражнения..........................51

Глава VI.

Некоторые отрывки из сочинений Эйлера...............68

ОПЕЧАТКИ

Напечатано

Следует читать

Зак. 1935. И. Я. Депман. „Метод математической индукции".