Соминский И. С. Метод математической индукции. — 8-е изд. — М. : Наука, 1974. — 64 с. — (Популярные лекции по математике ; вып. 3).

Популярные лекции

ПО МАТЕМАТИКЕ

И. С. СОМИНСКИЙ

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

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

ВЫПУСК 3

И. С. СОМИНСКИЙ

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

ИЗДАНИЕ ВОСЬМОЕ

ИЗДАТЕЛЬСТВО «НАУКА»

ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

МОСКВА 1974

512 С 61

УДК 512

АННОТАЦИЯ

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

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

„ 20202-034

С -89-74

053(01)-74

СОДЕРЖАНИЕ

От издательства............ 4

Введение .............. б

§ 1. Доказательства тождеств; задачи арифметического характера (примеры 1—13; задачи 1—16) 16

§ 2. Тригонометрические и алгебраические задачи (примеры 14-18; задачи 17—23).........29

§ 3. Задачи на доказательство неравенств (примеры 19—24; задачи 24—27) ........... 34

§ 4. Доказательство некоторых теорем элементарной алгебры методом математической индукции (теоремы 1—7) . 42

Ю. А. Гастев. Послесловие .........47

Указания и решения...........53

ОТ ИЗДАТЕЛЬСТВА

Книжка И. С. Соминского «Метод математической индукции», изданная впервые в 1960 г. и пользовавшаяся большим успехом, переведена на несколько иностранных языков. В серии «Популярные лекции по математике» появилось шесть ее изданий (начиная с третьего — стереотипных).

Настоящее издание, подготовленное к печати уже без участия автора (скончавшегося 25 июля 1962 г.), отличается от предыдущего издания 1961 г. незначительными редакционными изменениями, некоторым расширением вводной части книги (произведенным с использованием текста упомянутой на стр. 49 книги Л. И. Головиной и И. М. Яглома), а также кратким послесловием, написанным Ю. А. Гастевым.

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

Настоящее издание не отличается от предыдущего (1965 г.).

ВВЕДЕНИЕ

Утверждения подразделяются на общие и частные.

Приведем примеры общих утверждений.

Все граждане СССР имеют право на образование.

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

Все числа, оканчивающиеся нулем, делятся на 5.

Соответствующими примерами частных утверждений являются следующие:

Петров имеет право на образование.

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

140 делится на 5.

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

Все граждане СССР имеют право на образование. (1) Петров — гражданин СССР. (2)

Петров имеет право на образование. (3)

Из общего утверждения (1) при помощи утверждения (2) получено частное утверждение (3).

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

140 делится на 5. (1)

Все числа, оканчивающиеся нулем, делятся на 5. (2)

Из частного утверждения (1) получено общее утверждение (2). Утверждение (2) верно.

140 делится на 5. (1)

Все трехзначные числа делятся на 5. (2)

Из частного утверждения (1) получено общее утверждение (2). Утверждение (2) неверно.

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

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

Пример 1. Пусть

Легко проверить, что

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

Пример 2. Рассмотрим трехчлен х2-\-х+А\9 на который обратил внимание еще Л. Эйлер. Поставим в этот трехчлен вместо х нуль, получим простое число 41. Подставим теперь в этот же трехчлен вместо х единицу, получим опять простое число 43. Продолжая подставлять в трехчлен вместо х последовательно 2, 3, 4, 5, 6, 7, 8, 9, 10, получаем всякий раз простое число 47, 53, 61, 71, 83, 97, 113, 131, 151. На основании полученных результатов утверждаем, что при подстановке в трехчлен вместо je любого целого неотрицательного числа в с е г« да в результате получается простое число.

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

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

*) См. Послесловие, стр. 47—52.

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

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

Так, если в примере 1 сделанное нами общее утверждение случайно оказывается верным, как это доказано ниже в примере 4, то в примере 2 наше общее утверждение оказалось неверным.

В самом деле, при более внимательном изучении трехчлена Jt2+# + 41 обнаружили, что он равен простому числу при #=0, 1, 2, 39, но при х=40 этот трехчлен равен 412, т. е. числу составному**).

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

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

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

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

*) См. Послесловие, стр. 47—52.

**) И уж совсем сразу бросается в глаза, что при х=41 *2+jt+41=412+4i + 41 делится на 41.

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

В 1938 г. в журнале «Успехи математических наук» (вып. IV) была опубликована заметка выдающегося советского математика Н. Г. Чеботарева, в которой он предложил нашим математикам выяснить этот вопрос.

Эту задачу решил В. Иванов1). Оказалось, что указанным свойством обладают все двучлены хп—1, степень которых меньше 105. Одним же из множителей х105—I является многочлен

уже не обладающий этим свойством.

Пример 4. Рассмотрим числа вида 22" +1. При л=0, 1, 2, 3, 4^числа 22° +1=3, 22'+1=5, 222 + 1 = 17, 22\+1 = = 257, 22' +1=65 537— простые. Замечательный французский математик XVII в. П. Ферма предполагал, что все числа такого вида — простые. Однако в XVIII в. Л.Эйлер нашел, что

22 5 +1 = 4 294 967 297 = 641 • 6 700 417

— составное число.

Пример 5. Знаменитый немецкий математик XVII в., один из создателей так называемой «высшей математики», Г. В. Лейбниц доказал, что при всяком целом положительном п число я3—п делится на 3, число пъ—п делится на 5, число п7—п делится на 7*). На основании этого он предположил было, что при всяком нечетном k и любом натуральном п число nk—п делится на k, но скоро сам заметил, что 29—2 = 510 не делится на 9.

Пример 6. В ошибку такого же рода впал однажды известный советский математик Д. А. Граве, предположив, что для всех простых чисел р число 2Р~1—1 не

1) «Успехи математических наук», вып. IV, 1941, стр. 313—317.

*) См., например, книгу: Д. О. Шклярский, Н. Н. Ченцов, И. М. Яглом, Избранные задачи и теоремы элементарной математики, ч. 1, Физматгиз, 1959 (задачи 27а), б), в)).

делится на р2. Непосредственная проверка подтвердила это предположение для всех простых чисел р> меньших тысячи. Вскоре, однако, было установлено, что 21092—1 делится на 10932 (1093—простое число), т. е. предположение Граве оказалось ошибочным.

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

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

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

В действительности это не так, а именно: четыре плоскости разбивают пространство на 14 частей, пять плоскостей— на 22 части. Можно доказать, что п плоскостей разбивают пространство на п(п—1)+2 частей*).

Пример 8. Приведем еще один весьма убедительный пример. Подставляя в выражение 991/г2+1 вместо п последовательно целые числа 1, 2, 3, мы никогда не получим числа, являющегося полным квадратом, сколько бы дней или даже лет мы ни посвятили этим вычислениям. Однако если мы сделаем отсюда вывод, что все числа такого вида не являются квадратами, то мы ошибемся. На самом деле оказывается, что среди чисел вида 991 n2-f-1 имеются и квадраты: только наименьшее значение п, при котором число 991п2+1 есть полный квадрат, очень велико. Вот это число:

п = 12 055 735 790 331 359 447 442 538 767.

Рассмотренные примеры позволяют сделать простой и в то же время важный вывод.

Утверждение может быть справедливым в целом ряде частных случаев и в то же время несправедливым вообще.

*) Решение см. ниже, на стр. 27—28, пример 13.

3. Теперь возникает такой вопрос. Имеется утверждение, справедливое в нескольких частных случаях. Все частные случаи рассмотреть невозможно. Как же узнать, справедливо ли это утверждение вообще?

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

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

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

Доказательство*). Предположим противное, т. е. предположим, что утверждение справедливо не для всякого натурального п. Тогда существует такое натуральное m, что 1) утверждение для п=пг несправедливо, 2) для всякого п, меньшего m, утверждение справедливо (иными словами, m есть первое натуральное число, для которого утверждение несправедливо).

Очевидно, что т>1, так как для п=\ утверждение справедливо (условие 1). Следовательно, m—1—натуральное число. Выходит, что для натурального числа m—1 утверждение справедливо, а для следующего натурального числа m оно несправедливо. Это противоречит условию 2.

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

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

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

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

Теорема 1. Утверждение справедливо для п=1.

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

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

Пример 9. Вычислить сумму (см. пример 1)

Мы знаем, что

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

Будем осторожны и скажем, что рассмотрение сумм Si, S2t S3, S4 позволяет высказать гипотезу (предположение), что $п = ПРИ всяком натуральном п. При

этом мы знаем, что гипотеза эта верна при п=1, 2, 3, 4. Для проверки гипотезы воспользуемся методом математической индукции.

Теорема 1. Для л=1 гипотеза верна, так как

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

где k — некоторое натуральное число. Докажем, что тогда гипотеза обязана быть верной и для л=£-Н, т. е. что

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

следовательно, по условию теоремы,

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

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

Замечание 1. Необходимо подчеркнуть, что доказательство методом математической индукции безусловно требует доказательства обеих теорем, 1 и 2.

Мы уже видели, к чему привело пренебрежительное отношение к теореме 2 (пример 2).

Сейчас мы покажем, что нельзя опускать и теорему 1. Рассмотрим пример.

Пример 10. Теорема. Всякое натуральное число равно следующему за ним натуральному числу.

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

k = k+\. (1)

Докажем, что

k + 1 = k + 2. (2)

Действительно, прибавив к каждой части равенства (1) по 1, получим равенство (2). Выходит, что если утверждение справедливо для я = &, то оно справедливо и для n = k + l. Теорема доказана.

Следствие. Все натуральные числа равны.

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

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

Если не доказана теорема 1, а доказана теорема 2 (см. пример 10), то, следовательно, не создана база для проведения индукции, и тогда бессмысленно применять теорему 2, так как и расширять-то, собственно, нечего.

Если не доказана теорема 2, а доказана только теорема 1 (см. примеры 1 и 2), то, хотя база для проведения индукции и создана, право расширения этой базы отсутствует.

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

Иногда вторая часть доказательства опирается на справедливость утверждения не только для n = k, но и для п = А—1. В этом случае утверждение в первой части должно быть проверено для двух последовательных значений п.

Иногда также вторая часть доказательства состоит в установлении справедливости требуемого рассуждения для какого-то значения п в предположении справедливости его для всех натуральных чисел k9 меньших п. Ниже читатель найдет примеры такого рода (см. пример 7 на стр. 21, 22).

Иногда утверждение доказывается не для всякого натурального я, а для всякого целого /г, превосходящего некоторое целое m1). В этом случае в первой части доказательства утверждение проверяется для n = m+l, а если это требуется, то и для нескольких последующих значений п.

1) Так, например, любое утверждение, касающееся свойств произвольных м-угольников, имеет смысл лишь при п>3.

5. Вернемся еще раз к примеру 1 для выяснения одной существенной стороны метода математической индукции.

Изучая сумму

при разных значениях п, мы подсчитали, что

и это навело нас на гипотезу, что и при всяком п

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

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

Пример 11. Рассмотрим суммы

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

(1)

При п = 1 формула (1) верна, так как Sj =—. Предположим, что формула (1) верна при n = k, т. е.

Попытаемся доказать, что формула (1) верна и при n = k+1, т. е. что

Имеем

т. е. результат получился иной.

Выходит, что из справедливости формулы (1) при n = k не следует ее справедливость при n = k+l. Мы обнаружили, что формула (1) неверна.

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

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

Чтобы не повторять без конца слова «Теорема 1» и «Теорема 2», мы условимся в дальнейшем помечать первую и вторую части доказательства по индукции (эти части и составляют содержание двух теорем, доказательство которых равносильно пользованию методом индукции) знаками 1° и 2°. Кроме того, мы будем различать примеры, снабженные подробными решениями, и задачи, предназначенные для самостоятельной работы читателя. В конце книги будут приведены указания, относящиеся к решению всех приведенных в тексте задач. Иногда эти указания представляют собой лишь ссылку на иную, доступную читателям литературу; в других случаях они содержат полное решение задачи.

§ 1. ДОКАЗАТЕЛЬСТВА ТОЖДЕСТВ; ЗАДАЧИ АРИФМЕТИЧЕСКОГО ХАРАКТЕРА

Пример 1. Выпишем в порядке возрастания нечетные положительные числа 1, 3, 5, 7, ... Обозначим первое из них ui, второе и2, третье и3 и т. д., т. е,

ы2 = 3, «з = 5, и4 = 7,

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

Решение. Первое нечетное число щ можно записать так:

^ = 2.1-1; (1)

второе нечетное число щ можно записать так:

ii.-2.2-l; (2)

третье нечетное число и% можно записать так:

м3== 2-3—1. (3)

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

ип = 2п-\. (4)

Докажем, что формула эта справедлива.

1°. Равенство (1) показывает, что для /1=1 формула (4) справедлива.

2°. Предположим, что формула (4) справедлива для n = kfT. е. &-е нечетное число имеет вид

ик = 2k— 1.

Докажем, что тогда формула (4) обязана быть справедливой и для (&+1)-го нечетного числа, т. е. что (&-{-1)-е нечетное число имеет вид

%и = 2(А-Н)-1,

или, что все равно,

uk+l = 2k+ 1.

Для получения (£+1)-го нечетного числа достаточно к k-му нечетному числу прибавить 2, т. е.

uk+i - и* + 2.

Но, по условию, uk=2k—1. Значит,

uk+l = (2k—l) +2 = 2£-И.

что и требовалось доказать. Ответ. ип = 2п—1.

Пример 2. Вычислить сумму первых /г нечетных чисел.

Решение. Обозначим искомую сумму Sn, т. е. 5Я = 1 + 3 + 5 + ... + (2лг — 1).

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

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

Имеем

S1==l, S2 = 4, S3 = 9, S4= 16, S6 = 25, Se = 36.

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

Полагаем, что в данном случае легко заметить, что S1== I2, S2 = 22, S3 = 32, S4 = 42. На основе этого можно предположить, что вообще

Докажем, что гипотеза эта справедлива.

1°. При п=1 сумма представляется одним слагаемым, равным 1. Выражение п2 при л=1 также равно 1. Значит, при л=1 гипотеза верна.

2°. Допустим, что гипотеза верна для п=й, т. е. SÄ= = k2. Докажем, что тогда гипотеза должна быть верна и для n=fe+l, т. е.

S*+1=(*+l)2.

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

S*+i-S* + (2ft+l). Но S Ä=ft2 и потому

S,+i = ^2 + (2ä + 1) = (ä+1)2,

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

Задача 1. Найти иЛ, если известно, что и что

при всяком натуральном k>l

Ч - uk-i + з. Указание. «i = 3*I—2, 3-2—2.

Задача 2. Найти сумму

Sn =г 1 + 2 + 2а + 23 + ... + 2"-Ч

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

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

Обозначим искомую сумму S„» т. е.

Sn =1 + 2 + 3 + ... + п.

1°. При п=1 гипотеза верна. 2°. Пусть

Покажем, что

В самом деле,

Задача решена.

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

Решение. Пусть

1.

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

Тогда

и окончательно

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

Решение. Iе. При п=1 гипотеза, очевидно, верна

((-i)°=i).

Докажем, что

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

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

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

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

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

Решение. 1°.

2°. Если

то

Пример 6 можно также вывести из результатов примеров 3 и 4, если заметить, что

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

Задача 7, Доказать, что

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

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

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

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

Пример 7. Доказать, что если t/0=2, v{ = 3 и для всякого натурального k имеет место соотношение

то

Решение. 1°. Для п=0 и п=1 утверждение справедливо по условию.

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

Тогда

Задача 12. Доказать, что если

и для всякого натурального k>2 имеет место соотношение

то

Пример 8. Произведение Ь2«3 ... п обозначается знаком п\ и читается так: «п факториал». Полезно запомнить, что 11 = 1, 21 = 2, 31 = 6, 4!=24, 51=120.

Вычислить

S„= 1. II+ 2-2!+ 3-3I + ... + n.nl Решение.

S1 = bl!= 1, Sa= Ы1 + 2.21 = 5,

53 = l.ll + 2.2! + 3.3! = 23,

54 =1.1! + 2.2! + 3-3! + 4.4! = 119.

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

S1==2!—1, S2 = 3!—1, S3 = 4!—1, S4 = 5!—1.

Это дает возможность высказать гипотезу, что S„ = (n+1)!-1.

Проверим эту гипотезу.

1°. Для п=1 гипотеза верна, так как

S1 = 1.Ц= 21—1.

2°, Пусть

Sk = Ы! +2.2!+ + = 1)1—1.

Покажем, что

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

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

Пример 9. Дано:

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

(1)

Решение. 1°. Докажем сначала, что формула (1) верна для п«=2. По условию,

По формуле (1)

Сократив последнюю дробь на а—ß, имеем

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

2°. Пусть формула (1) справедлива для n = fe, т. е.

(2)

Докажем, что тогда она должна быть справедлива и для n=k+l9 т. е.

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

Пользуясь равенством (2), имеем

Теорема доказана.

Задача 14. Упростить многочлен

Ответ.

Пример 10. Доказать, что любое целое число рублей, большее 7, можно уплатить без сдачи денежными билетами, достоинством в 3 и 5 рублей.

Решение. 1°. Для 8 рублей утверждение справедливо (ибо 8 руб.*=3 руб.+5 руб.).

2°. Пусть утверждение верно для k рублей, где k — целое число, большее или равное 8.

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

В первом случае трехрублевых билетов должно быть не менее трех, так как в этом случае k>8. Для того чтобы уплатить £+1 рубль, заменим три трехрублевых билета двумя пятирублевыми.

Во втором случае для уплаты k+l рубля заменим один пятирублевый билет двумя трехрублевыми.

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

Решение. 1 . Сумма 13+23+33 делится на 9. Значит, утверждение справедливо, когда первым из трех последовательных натуральных чисел является 1.

2°. Пусть сумма £3+(£+1)3+(£+2)3, где k — некоторое натуральное число, делится на 9. Сумма

(£+1)3 + (£ + 2)3 + (£+3)3~(£ + 1)3 + (£ + 2)3 + £3 + +9£2+27£+27 = [£3+(Ä + 1)3+ (k + 2)3] + 9 (&а + 3& + 3)

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

Ля= 11"+*+ 122л+1

делится на 133.

Пример 12. Из 2п чисел 1, 2, 2п произвольно выбрали п+1 число. Доказать, что среди выбранных чисел найдутся хотя бы два числа, из которых одно делится на другое.

Решение1). Г. Для двух чисел 1, 2 утверждение справедливо.

2°. Допустим, что из 2п чисел 1, 2, 2пу где п> 2, удалось выбрать п+1 число так, что ни одно из них не делится на другое. Совокупность всех этих чисел обозначим для краткости Мп+Х. Докажем, что тогда из 2п—2 чисел 1, 2, 2п—2 можно выбрать п чисел таких, что опять ни одно из них не будет делиться на другое.

1) Это решение принадлежит М. Фридману.

Возможны четыре случая:

1) Мп+\ не содержит ни 2м—1, ни 2п.

2) Мп+\ содержит 2п—1 и не содержит 2п.

3) Mn+i содержит 2п и не содержит 2м— 1.

4) Мп+\ содержит и 2п— 1, и 2м.

Случай 1. Исключим из Мп+\ какое-нибудь число. Останется м чисел, каждое из которых не больше, чем 2п—2. Ни одно из этих чисел не делится на другое.

Случай 2. Исключим из Мп+\ число 2п—1. Останется м чисел, каждое из которых не больше, чем 2п—2. Ни одно из этих м чисел не делится на другое.

Случай 3. Исключим из Мп+\ число 2п и опять получим тот же результат.

Случай 4. Прежде всего заметим, что в Мп+\ не содержится число м, так как иначе в Мп+\ нашлось бы два числа (2п и м), из которых одно делится на другое.

Исключим из Мл-fi числа 2п—1 и 2п. Совокупность оставшихся м—1 чисел обозначим Мп-\ . Присоединим к Мп-\ число п. Получим м чисел, каждое из которых не превосходит 2п—2. Остается показать, что среди этих м чисел ни одно не делится на другое.

В Mn+i не было двух чисел, из которых одно делится на другое. Значит, таких чисел не было и в Мп-\- Остается только убедиться в том, что таких чисел не появилось и тогда, когда мы к Afn-i присоединили число м.

Для этого достаточно убедиться в том, что: 1) ни одно число, входящее в Mл—i, не делится на м и 2) число м не делится ни на одно из чисел, входящих в /Wrt-i.

Первое вытекает из того, что все числа входящие в Мп-А> не превосходят 2п—2.

Второе вытекает из того, что число 2п не делится ни на одно из чисел, входящих в Мп-\.

Итак, если допустить, что утверждение неверно для 2п чисел 1, 2, 2м, то оно неверно и для 2(м—1) чисел 1, 2, 2м—2. Значит, если утверждение верно для 2(м—1) чисел 1, 2, 2м—2, то оно верно и для 2м чисел 1, 2, 2м.

Отсюда и из пункта 1° следует, что наше утверждение справедливо для 2м чисел 1, 2, 2м, где м — любое натуральное число.

Заметим, что эта задача имеет следующее простое решение. Выберем из 2м чисел 1, 2, 2м произвольное м+1 число. Совокупность этих чисел обозначим Afn-f-i.

Каждое четное число, входящее в Мп+и разделим на такую степень двойки, чтобы частное было нечетным. Совокупность этих частных и всех нечетных чисел, входящих в Мп+и обозначим через Мо+ь В Мп+\ содержится п+1 нечетное число, каждое из которых меньше 2/г.

Так как всех положительных нечетных чисел, меньших 2/г, имеется всего п, то в Мп+\ имеются хотя бы два равных числа. Каждое из этих чисел пусть равно k.

Полученный результат означает, что в Мл+1 было два числа 2sk и 2*k (где одно из чисел s и / может равняться нулю). Но одно из чисел 2sk и 2fk делится на второе.

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

Пример 13. Доказать, что п плоскостей, проходящих через одну точку так, что никакие три из них не проходят через одну прямую, делят пространство на Ап =п(п—1)+2 частей.

Решение. Г. Одна плоскость делит пространство на две части, и Лi = 2. Для /1=1 утверждение справедливо.

2°. Предположим, что утверждение справедливо для n = k, т. е. k плоскостей делят пространство на k(k—1)+2 частей. Докажем, что тогда £+1 плоскостей делят пространство на k(k+l)+2 частей.

Действительно, пусть Р есть (&+1)-я плоскость. С каждой из первых k плоскостей плоскость Р пересекается по некоторой прямой и, таким образом, плоскость Р разбита на части посредством k различных прямых, проходящих через одну точку. На основании задачи 16 утверждаем, что плоскость Р разбита на 2k частей, каждая из которых представляет собой плоский угол с вершиной в данной точке.

Первые k плоскостей делят пространство на некоторые многогранные углы. Некоторые из этих многогранных углов делятся посредством плоскости Р на две части.

*) Задача 16 и пример 13 отнесены к этому параграфу, поскольку они имеют, по существу, чисто арифметический характер, хотя и связаны с геометрической проблематикой.

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

Это означает, что число многогранных углов, разбиваемых на две части плоскостью Р$ не может быть больше, чем 2k.

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

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

Итак, плоскость Р разбивает на две части точно 2k частей пространства, образованных первыми k плоскостями. Поэтому если k плоскостей разбивают пространство на k(k—1)+2 частей, k+l плоскость разбивает пространство на

[k (k— l)+2]+2k = k (k+1)+2

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

§ 2. ТРИГОНОМЕТРИЧЕСКИЕ И АЛГЕБРАИЧЕСКИЕ ЗАДАЧИ

Пример 14, Доказать тождество

Решение. 1°. При л=0 тождество справедливо, так как

2°. Пусть тождество справедливо при n=k, т. е.

Тогда оно справедливо и при л=£+1. Действительно,

Пример 15. Доказать, что A =cos по, если известно, что j4i=cos б; ^42=cos2ö и для всякого натурального А>2 имеет место соотношение

Решение. 1°, Утверждение справедливо при л=1 и п=2. 2°# Пусть

Тогда

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

Решение. Iе. При п=1 утверждение справедливо. 2°. Пусть

Тогда

ибо

Задача 17, Доказать, что

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

Задача 20, Доказать, что

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

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

Решение. Iе. При п=1 утверждение справедливо, так как

2°. Пусть

Тогда

Пример 18. Доказать теорему:

Если в результате конечного числа рациональных действий (т. е. сложения, вычитания, умножения и деления) над комплексными числами Х\9 х% хп получается число w, то в результате jex же действий над сопряженными числами хи *2, хп получится число ы, сопряженное с и.

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

Тогда

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

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

Например, пусть

Для вычисления и достаточно произвести действия:

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

Действительно, последнее (&+1)-е «действие» мы выполняем над числами ut и Uj, которые сами вычислялись посредством не более чем k «действий».

Ь результате замены чисел хи *2, хп сопряженными, числа ut и иj заменяются сопряженными и{ и u/t а тогда и результат (&+1)-го «действия» над ними, т. е. число и, также заменится сопряженным числом и.

Задача 23. Доказать, что при любом натуральном п

(cos x+i sin jc)n=»cos nx+i sin nx.

§ 3. ЗАДАЧИ НА ДОКАЗАТЕЛЬСТВО НЕРАВЕНСТВ

Пример 19. Доказать, что при любом натуральном л>1

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

1°. 52=—• = —, следовательно, при п=2 неравенство справедливо.

2°. Пусть Sk> -^-при некотором k. Докажем, что тогда и SÄ+1 > —. Имеем

Сравнивая Sk и SÄ+1, имеем

т. е.

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

Но S*> • значит» и

Задача 24. Найти ошибку.

Утверждение. При любом натуральном п справедливо неравенство

2п>2п + 1.

Доказательство. Пусть неравенство справедливо при n = k, где k— некоторое натуральное число, т. е.

2* > 2k + 1. (1)

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

2*+I>2(ft+l) + l. (2)

Действительно, 2* не меньше 2 при любом натуральном k. Прибавим к левой части неравенства (1) 2*, а к правой 2. Получим справедливое неравенство

2* + 2* > 2k + 1 + 2,

или

2*+»>2(ife+l) + l.

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

Задача 25. При каких натуральных п справедливо неравенство

2п>2п+ 1?

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

2п > л2?

Решение.

При /г = 1 неравенство справедливо, так как 2]>12. При я = 2 неравенство несправедливо, так как 22=22. При п = 3 неравенство несправедливо, так как 23<32. При п=4 неравенство несправедливо, так как 24 = 42. При /1 = 5 неравенство справедливо, так как 25>52. При п = 6 неравенство справедливо, так как 26>62. По-видимому, неравенство справедливо при /1=1 и при любом п>4. Докажем это.

1°. При п = 5 неравенство справедливо, 2°. Пусть

2*>k\ (1)

где k — некоторое натуральное число, большее 4.

Задача 27. Доказать, что при любом натуральном п>1

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

Мы знаем, что 2k > 2&+1 при k>4 (задача 25). Поэтому если мы к левой части неравенства (1) прибавим 2Ä, а к правой 2&+1, получим справедливое неравенство (2).

Ответ. 2п>п2, когда п=1 и когда п>4.

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

(1+а)«>1 +па,

где а>—1, а=т^0, п — натуральное число, большее I.

Решение. 1°. При п=2 неравенство справедливо, так как а2>0.

2°. Пусть неравенство справедливо при n=k, где k— некоторое натуральное число, т. е.

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

Покажем, что тогда неравенство и при /г=&+1, т. е.

(l+a)*+i>l + (£+l)a. (2)

Действительно, по условию, 1+а>0, поэтому справедливо неравенство

(1+а)*+*>(1+*а)(1+а), (3)

полученное из неравенства (1) умножением каждой части его на 1+ос.

Перепишем неравенство (3) так:

(1 + а)*+! > 1 + (k + 1) а + ko*.

Отбросив в правой части последнего неравенства положительное слагаемое £ос2, получим справедливое неравенство (2).

Задача 26. Доказать, что при любом натуральном л>1

2"-1 (ап + Ьп) >(а + b)n, (1)

где а+6>0, а=£Ь, п — натуральное число, большее 1.

Решение. 1°, При п=2 неравенство (1) принимает вид

2(о* + Ь*)>{а + Ь)*. (2)

Так как афЬ, то справедливо неравенство

(а-Ь)*>0. (3)

Прибавив к каждой части неравенства (3) по (а+Ь)29 получим неравенство (2).

Этим доказано, что при п=2 неравенство (1) справедливо.

2°, Пусть неравенство (1) справедливо при n=k, где k — некоторое натуральное число, т. е.

2*-i (а* + bk) >(а + Ь)К (4)

Докажем, что тогда неравенство (1) должно быть справедливо и при n=k+l9 т. е.

2*(aft+i + >(а + (5)

Умножим обе части неравенства (4) на а+Ь. Так как, по условию, а+Ь>0, то получаем следующее справедливое неравенство:

2*-i (a* + ô*) (а + ft) >(а + (6)

Для того чтобы доказать справедливость неравенства (5), достаточно показать, что

2* (а**1 + > 2*-1 (а* + &*) (а + Ь), (7)

или, что все равно,

a*+i + ftft+i > akb + abh. (8)

Неравенство (8) равносильно неравенству

(ak — bk)(a — b) >0. (9)

Если а>&, то ak>bk, и в левой части неравенства (9) имеем произведение двух положительных чисел. Если а<Ь, то ak<bk, и в левой части неравенства (9) имеем произведение двух отрицательных чисел. В обоих случаях неравенство (9) справедливо.

Этим доказано, что из справедливости неравенства (1) при n=k следует его справедливость при n = k+\.

Пример 23. Доказать, что при любом *>0 и при любом натуральном п справедливо неравенство

О)

Решение. 1°. а) При п=\ неравенство (1) принимает вид

(2)

Неравенство (2) вытекает из очевидного неравенства

б) При п=2 неравенство (1) принимает вид

(3)

Неравенство (2) справедливо при любом х>0\ значит, оно справедливо и при замене х на х2, т. е.

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

2°. Предположим, что неравенство (1) справедливо при л=£, где k — некоторое натуральное число, т. е.

(4)

Докажем, что тогда неравенство (1) справедливо и при n = ß-f2, т. е.

(5)

Заменив в неравенстве (2) х на xk+2, получаем

(6)

Сложив почленно неравенства (4) и (6), получим неравенство (5),

Подведем теперь итог.

В пп. 1° а) и б) мы доказали, что неравенство (1) справедливо при п=1 и при п=2.

В п. 2° мы доказали, что из справедливости неравенства (1) при n=k вытекает его справедливость и при n = k+2.

Иными словами, п. 2° дает нам право перехода от n = k к n = k+2.

Результаты пп. 1° а) и 2° дают нам право утверждать, что неравенство (1) справедливо при любом нечетном п.

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

В целом мы имеем право утверждать, что неравенство (1) справедливо при любом натуральном п.

Пример 24. Доказать теорему:

Среднее геометрическое нескольких положительных чисел не больше их среднего арифметического, т. е. если йи Яг, •••> ап положительны, то

(1)

Решение. 1°. При л = 2 неравенство (1) принимает вид

(2)

Это неравенство легко получить из справедливого при любых положительных й\ и неравенства

Неравенство (2) имеет простой геометрический смысл. На прямой AB отложим последовательно отрезки а\ и а2. На сумме их как на диаметре опишем окружность.

Тогда î—рз.—радиус этой окружности, a Vaia2 —половина хорды, перпендикулярной к диаметру в общей точке а\ и аг (см. рисунок), из чего и усматривается справедливость неравенства (2).

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

Докажем, что тогда оно справедливо и при м=2£. Действительно,

Неравенство (1) проверено при п = 2 и, таким образом, мы можем утверждать, что оно справедливо при п=4, 8, 16 и т. д., т. е. вообще при п = 2\ где 5 — натуральное число.

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

справедливости неравенства при n*=-k следует его справедливость при n = k—1.

Итак, пусть au ß2, ak-x — некоторые положительные числа. Пусть К — некоторое, пока не определенное, положительное число. Тогда

Выберем X так, чтобы

т. e, положим

Имеем

или

Пусть теперь m — произвольное натуральное число. Если m = 2s, то согласно 2° для него неравенство справедливо.

Если же m =7^= 2s, то найдем такое s, чтобы m было меньше 25, и тогда на основании 2° и 3° утверждаем, что. неравенство верно для n = m.

§ 4. ДОКАЗАТЕЛЬСТВО НЕКОТОРЫХ ТЕОРЕМ ЭЛЕМЕНТАРНОЙ АЛГЕБРЫ МЕТОДОМ МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

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

(1)

1°. Для п=2 формула (1) может быть доказана непосредственным умножением.

2°. Допустим, что формула (1) верна для n = k—1, т. е.

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

где Si—сумма всевозможных попарных произведений, составленных из аи аг» ...» ал> т. е.

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

Теорема 2. п-й член арифметической прогрессии может быть вычислен по формуле

an = a1 + d(n—l), (1)

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

1°. Для /г= 1 формула (1) верна.

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

ak=-a1 + d(k — 1).

Тогда

ak+i — ak + d = al + d(k — l)+d = a1 + dk,

т. е. формула (1) оказывается справедливой и для n=k+l.

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

аЛ = ад«-\ (1)

где а\ — первый член, q —знаменатель прогрессии. 1°. Для м=1 формула (1) верна. 2°. Пусть

Тогда

ak+i = akQ ~ aiQk-

Теорема 4. Число перестановок из m элементов может быть вычислено по формуле

Pm = ml (1)

1°. Прежде всего заметим, что Pi=l и, таким образом, при m=l формула (1) верна. 2°. Пусть Pk=k\, Докажем, что

Из данных k-\-\ элементов а\, аъ, ak9 ak+\ возьмем только первые k и составим из них всевозможные перестановки. По условию, таких перестановок будет kl.

В каждой из этих перестановок поставим элемент ak+i последовательно перед 1-м элементом, перед 2-м,...

перед А-м, после k-ro. Этим путем мы из одной пере-

становки из k элементов получим &+1 перестановок из k+l элементов. Всего имеем

k\(k+l)=(k+ 1)!

перестановок из k+l элементов. Необходимо выяснить:

1) нет ли среди этих (k+l)l перестановок двух одинаковых;

2) все ли перестановки из k+l элементов нами получены.

1) Допустим, что среди (k+l)\ перестановок имеются две одинаковые. Назовем их р\ и рг. Пусть в перестановке р\ элемент ak+1 занимает 5-е место, считая слева. Тогда и в р% элемент ak+x занимает 5-е место считая слева. Удалим из р\ и р% элемент aÄ+1. Получим две одинаковые перестановки из k элементов: р\ и

Выходит, что для получения р\ и р2 в одну и ту же перестановку из элементов au 02, .... ^ два раза на одно и то же место был поставлен элемент ak+1. Это противоречит правилу, по которому построены перестановки.

2) Допустим, что некоторая перестановка р из k+l элементов нами не получена. Пусть в р элемент ak+l занимает 5-е место слева. Удалим из р элемент afc+v Получим перестановку р из первых k элементов. Значит, для получения р достаточно было взять перестановку р и поставить в нее элемент ak+i так, чтобы он занял 5-е место слева.

Мы не могли не взять перестановку р, так как брали всевозможные перестановки из первых k элементов. Мы не могли не поставить элемент ak+i на указанное место, так как ставили его и первым, и вторым,.... и (&-И)-м слева.

Итак, составленные нами перестановки все различны и всякая перестановка из k+l элементов нами получена.

Из сказанного вытекает, что

Теорема 5. Число размещений из m элементов по п может быть вычислено по формуле

Anm = m(tn— l)...(m — n+l). (I)

1°. Прежде всего заметим, что Ахт=т и, таким образом, формула (1) верна при /1=1« 2°. Предположим, что

Akm = m (m — 1)... (m — k + 1),

где &<m. Докажем, что

ЛИ-1 в m (m — 1).. • (m — k).

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

Выходит, что

Теорема 6. Число сочетаний из m элементов по п может быть вычислено по формуле

(1)

1°. Прежде всего заметим, что Cm=m и, таким образом, при п=1 формула (1) верна. 2°, Допустим, что

Докажем, что

Для получения всех сочетаний из m элементов по k+l выпишем все сочетания из m элементов по k и к каждому из них в качестве (А-И)-го элемента присоединим каждый из m—k оставшихся элементов.

Ясно, что таким путем будут получены все сочетания из m элементов по ft+1, но каждое из них получится Л+1 раз.

Действительно, сочетание au Я2, ak, ak+1 получится, когда к сочетанию аг, Яз, ak, ak+i присоединится элемент аи когда к сочетанию а\9 аз, ak, ak+x присоединится элемент аг и т. д., когда, наконец, к сочетанию ßi, «2, elk присоединится элемент ak+1. Таким образом,

Теорема 7. Каковы бы ни были числа а и b и каково бы ни было натуральное число п, имеет место формула

(формула бинома Ньютона).

Г. При п=1 имеем a+b=a+b и, таким образом, для этого случая формула (1) верна.

2°. Пусть

Тогда

Имея в виду, что Csk + C|+1 = Cft.\f получаем

ПОСЛЕСЛОВИЕ

Ю. А. Гастев

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

Но вот мы читаем: «Индукция широко применяется в математике, но применять ее надо умело» (стр. 7 настоящей книги); «... как пользоваться в математике индукцией, чтобы получать только верные выводы?»*) (стр. 6). Что же все это, собственно, значит? Не следует ли понимать дело так, что среди математических методов есть «достоверные», действующие, так сказать, безотказно (дедуктивные), и «не вполне надежные», дающие подчас, особенно в неумелых руках (как выражается автор, «при легкомысленном отношении»), осечку (индуктивные)? Если бы это было действительно так, то где же искать критерии надежности таких «индуктивных» методов? Как вернуть себе уверенность в непреложной обязательности математических выводов? Или это безнадежная затея, и достоверность математических заключений — той же природы, что и опытные обобщения эскпериментальных наук, так что любой

*) Такого рода трактовка «индукции в математике» стала почти традиционной для школьных учебников — вплоть до самых новых (см., например, §§ 62, 63 учебника алгебры Е. С. Кочеткова и Е. С. Кочетковой).

доказанный факт неплохо было бы еще «проверить» (подобно тому как школьникам часто рекомендуется «проверять» правильность выполнения арифметических действий или решения уравнений по общей формуле)?

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

Ну, а как же «метод математической индукции»? Дело все в том, что «математическая индукция» есть дедуктивный метод. В самом деле, разберемся детальнее в структуре математических умозаключений, выглядящих как «переход от частного к общему». Легко убедиться, что так называемая математическая индукция на самом деле вовсе не есть индукция — это чисто дедуктивный метод рассуждения! Доказательство, проводимое этим методом, состоит из двух частей: 1) так называемый базис — доказательство (дедуктивное!) искомого предложения для одного (или нескольких) натурального числа (например, для 0 или 1; это то, что на стр. 11 именуется «Теоремой 1»; 2) индукционный шаг («Теорема 2»), состоящей в доказательстве (опять-таки дедуктивном) общего утверждения: для всех п верно, что из того, что искомое утверждение справедливо для л, вытекает, что оно справедливо и для п+1. «Принцип математической индукции» (стр. 10)—точно формулируемое предложение (интуитивная убедительность которого признается многими математиками как неоспоримая; при аксиоматическом же построении арифметики он фигурирует в качестве аксиомы), позволяющее извлечь из базиса и индукционного шага чисто дедуктивное доказательство рассматриваемого предложения для всех натуральных чисел п. Таким образом, никаких «не учтенных в посылках» случаев, на которые затем («по индукции») надо было бы еще «распространять» заключение, не остается — теорема именно доказывается для всех натуральных чисел: из базиса, доказанного, скажем, для числа 0, мы получаем, по индукционному шагу, доказательство для числа 1, затем таким же образом для 2, затем для 3,... — и так утверждение теоремы может быть обосновано для любого натурального числа*).

*) О встающих в связи с такого рода обоснованием метода проблемах см. указанную ниже литературу.

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

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

Условившись отныне в таком понимании термина, мы можем, конечно, позволить себе теперь и вольные перефразировки вроде «индукции в геометрии»**) или «индукции в математике». Но при этом всегда надо помнить, что первое выражение, строго говоря, имеет совсем не тот смысл, что громоздкое (но точное!) выражение «употребление дедуктивного метода математической индукции для доказательства теорем геометрического содержания» (хотя, для облегчения речи, и употребляется как его синоним), а второе— отнюдь не то же самое (вопреки чисто грамматическим признакам), что «математическая индукция»; последний термин следует воспринимать целиком, и вовсе не в смысле «индукция в математике».

Метод математической индукции (в той форме, в какой он рассматривается в этой книжке) есть метод доказательства арифметических теорем, точнее, теорем, выражающих общие свойства натуральных чисел (0, 1, 2, ...; иногда, как в этой книге, натуральный ряд уславливаются начинать с единицы, что абсолютно не

*) Мы уже упоминали вскользь о чрезвычайно плодотворной роли «обычной» («неполной») индукции в формировании математических догадок, ведущих затем и к открытиям новых фактов; подробнее об этом и о связи «обычной» индукции с методом математической индукции см. в книге Д. Пойа, Математика и правдоподобные рассуждения, ИЛ, 1957, т. I (особенно глава 7).

**) Именно так, например, названа для краткости книжка Л. И. Головиной и И. М. Яглома («Популярные лекции по математике», вып. 21), задуманная авторами в качестве естественного продолжения книжки И. С. Соминского,

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

Чтобы это последнее утверждение не показалось читателю слишком сильным, он должен твердо уяснить себе, что при аксиоматическом (дедуктивном) построении арифметики все ее здание опирается на определение операций над натуральными числами п о математической индукции (например, при определении сложения прежде всего определяется — в качестве базиса индукции, — что значит прибавить единицу или нуль; затем — индукционный шаг определения — определение прибавления произвольного натурального числа сводится к определению прибавления предшествующего числа). И вполне понятно потому, что «добираться» до общих свойств натуральных чисел, связанных, скажем, с операциями сложения или умножения, нам приходится (если уж мы хотим обосновывать их аксиоматически) по той же «лестнице» (на нижней «ступени» которой находится соответствующее свойство для наименьшего натурального числа), по которой мы «совершаем восхождение» к интересующему нас общему понятию; грубо говоря, иначе просто не видно, как за нужное нам доказательство «ухватиться»! И так обстоит дело с доказательством любого общего арифметического утверждения! И если это не видно из школьного курса арифметики и алгебры, то лишь потому, что он (совершенно резонно) опирается не столько на аксиоматический метод, сколько на опыт и интуицию*). В конце концов самый придирчивый и критически настроенный читатель часто довольствуется знанием того, что, скажем, дистрибутивность умножения относительно сложения можно доказать, и уже не требует самого доказательства. (Но такая, пусть вполне обоснованная, уверенность так же отличается от подлинного доказательства, как, скажем, газетная информация от подлинного знания очевидца, причем эта аналогия простирается весьма далеко.) Поэтому-то метод математической индукции и появляется в школьном курсе математики гораздо позже интуитивно прозрачных и легко постигаемых свойств арифметических действий,

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

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

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

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

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

Отметим еще, что метод, оказавшийся столь плодотворным для проведения доказательств, следующих процессу построения натурального ряда 0, 1, 2, может быть обобщен и на процессы совершенно другого вида. Например, в исчислениях математической логики, оперирующих с формулами («высказываниями»), построенными из «элементарных формул» («элементарных высказываний») вида А, В, С с помощью, допустим, знаков & («и»), \/ («или»), ZD («если то ...») и ~~] («не»), общие свойства формул доказываются путем так называемой индукции по построению

*) См. например, уже упоминавшуюся книжку Л. И. Головиной и И. М. Яглома «Индукция в геометрии».

**) То есть сам переход «от п к п+1» доказывается для любого п.

формулы: доказывается, что 1) искомым свойством обладает любая элементарная формула (базис), и 2) из того, что этим свойством обладают формулы I и У, следует, что им обладают формулы (X&Y), (X V У). (XzdY) п ~] X (индукционный шаг); из этого делается вывод о справедливости доказываемого предложения для всех формул указанного вида. Аналогия с рассматриваемой в настоящей книге математической индукцией настолько прозрачна, что бросается в глаза и неподготовленному читателю.

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

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

*) См., например, Л. Генкин, О математической индукции, Физматгиз, 1962; И. В. Арнольд, Теоретическая арифметика, Учпедгиз, 1939, § 13, 14, 17, 19; С. К. Клини, Введение в метаматематику, ИЛ, 1957, § 7, 13, 21, 38 и др.; «Математическая индукция» — Философская энциклопедия, М, 1964 (т. 3).

УКАЗАНИЯ И РЕШЕНИЯ*)

1. Гипотеза:

ип = 3п — 2.

Г. Для п=\ гипотеза верна. 2°. Пусть

uk = 3k — 2.

Тогда

= «а + 3 == 3/5 — 2 + 3 = 3 + 1) — 2.

2. Гипотеза

S„-2«-l. 1°. Для л=1 гипотеза верна. 2°. Пусть

Sft=2*-1.

Тогда

[Можно также сразу образовать разность 2Sn — Sn и показать, что она равная 2п—1.]

3. 1°. При п=1 утверждение справедливо. 2°. Пусть

Тогда

4. Г. При л«1 утверждение справедливо. 2°. Пусть

*) Ниже указываются номера задач. Решения примеров приводятся в тексте.

5. 1°. При п=1 утверждение справедливо. 2°. Пусть

Тогда

6. Iе. При л=1 утверждение справедливо. 2е. Пусть

Тогда

7. Iе. При п=»1 утверждение справедливо. 2°. Пусть

Тогда

8. Iе. При л=1 утверждение справедливо. 2°. Пусть

9. Г. При я=1 утверждение справедливо. 2°. Пусть

Тогда

10. 1°. При л = 1 утверждение справедливо. 2°. Пусть

Тогда

11. Г. При п=1 утверждение справедливо. 2°. Пусть

Тогда

12. 1°. При л=1 и п=2 утверждение справедливо. 2°. Пусть

Тогда

13. 1°, При л = 0 имеем

Следовательно, утверждение справедливо. 2°. Пусть

Тогда

14. При л=1 имеем

При л=2 имеем

При л«=*3 имеем

Это наводит на гипотезу:

Г. При п=1 гипотеза верна. 2°. Пусть

Тогда

15. Г. При п = 0 утверждение справедливо.

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

ЛА«= 11*+2+ 12**+1

делится на 133. Тогда

Мы представили Ak+i в виде суммы двух слагаемых, каждое из которых делится на 133. Значит, Âk+v делится на 133.

16. Г. При л=1 утверждение задачи, очевидно, справедливо. 2°. Предположив, что при п — к утверждение справедливо, т. е. к прямых делят плоскость на 2к углов, (А+1)-я прямая рассекает на части сразу два вертикальных угла, т. е. увеличивает число частей, на которые делится плоскость, на два. Поэтому (£+1)-я прямая делит плоскость на 2^4-2 = 2(^4-1) частей.

17. 1°. При п=1 утверждение справедливо, так как

2е. Пусть

Тогда

18. Г. При /1=1 утверждение справедливо, так как

19. 1°. При п=\ утверждение справедливо, так как

20. 1°. При л=*1 утверждение справедливо, так как

21. 1°. Имеем

Поэтому

Значит, при л«=1 утверждение справедливо. 2°. Покажем сначала, что

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

Значит,

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

(2)

Докажем, что тогда оно справедливо и при л=£ + 1, т. е.

Сложив почленно равенства (1) и (2), получим равенство (3).

22. 1°. При п=\ утверждение справедливо, так как

2°. Пусть

Тогда

23. Г. При п=1 утверждение справедливо. 2°. Пусть

Тогда

24. Ошибочна самая последняя фраза: «Утверждение доказано». В действительности доказано, что неравенство

2" > 2п + 1

справедливо при /г = & + 1, если оно справедливо при n—kf где k — любое натуральное число.

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

Короче говоря, ошибка заключается в том, что доказана только теорема 2, а теорема 1 не рассматривалась и база для индукции не создана.

25. Легко видеть, что 3 — наименьшее натуральное значение п, при котором неравенство 2п >2я+1 справедливо.

Учитывая, что из справедливости неравенства при n—k следует его справедливость при п=£-И (задача 24), утверждаем, что неравенство справедливо при любом натуральном п>3.

26. Г. При п=2 неравенство справедливо, так как

2°. Пусть

Докажем, что

При любом 0 имеет место неравенство

(3)

Действительно, неравенство (3) равносильно неравенству

полученному из него умножением обеих частей на у k + 1 + yk. Сложив почленно неравенства (1) и (3), получим неравенство (2).

16

27. 1°, При л=2 неравенство принимает вид ~~з~~<6 и, следовательно, справедливо. 2°. Пусть

где k>2. Нетрудно проверить, что при k>0

Поэтому

т. е.

Илья Самойлович Соминский

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

(Серия: «Популярные лекции по математике»)

М., 1974 г., 64 стр. с илл.

Редакторы А. П. Баева, В. В. Донченко Техн. редактор Г. А. Полонская Корректор Тш Л. Панькова

Сдано в набор 6/VIII 1973 г. Подписано к печати 12/II 1974 г. Бумага 84х108'/з2. Физ. печ. л. 2. Условн. печ. л. 3,36. Уч.-изд. л. 2,83 Тираж 100 000 экз. Цена книги 8 коп. Заказ 525

Издательство «Наука» Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15

1-я тип. Профиздата, Москва, Крутицкий вал, 18

Цена 8 коп.

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

Вып. 1. Л. И. Маркушевич. Возвратные последовательности.

Вып. 2. И. П. Натансон. Простейшие задачи на максимум я минимум.

Вып. 3. И. С. Соминский. Метод математической индукции.

Вып. 4. А. И. Маркушевич. Замечательные кривые.

Вып. 5. П. П. Коровкин. Неравенства.

Вып. 6. Н. Я. Воробьев. Числа Фибоначчи.

Вып. 7. А. Г. Курош. Алгебраические уравнения произвольных степеней.

Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах.

Вып. 9. Л. И. Маркушевич. Площади и логарифмы.

Вып. 10. Л. С. Смогоржевский. Метод координат.

Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказательствах.

Вып. 12. И. П. Натансон. Суммирование бесконечно малых величин.

Вып. 13. А. И. Маркушевич. Комплексные числа и конформные отображения.

Вып. 14. Л. И. Фетисов. О доказательствах в геометрии.

Вып. 15. И. Р. Шафаревич. О решении уравнений высших степеней

Вып. 16. В. Г. Шерватов. Гиперболические функции.

Вып. 17. В. Г. Болтянский. Что такое дифференцирование?

Вып. 18. Г. М. Миракьян. Прямой круговой цилиндр.

Вып. 19. Л. А. Люстерник. Кратчайшие линии.

Вып. 20. Л. М. Лопшиц. Вычисление площадей ориентированных фигур.

Вып. 21. Л. И. Головина и И. М. Яглом. Индукция в геометрии.

Вып. 22. В. Г. Болтянский. Равновеликие и равносоставленные фигуры.

Вып. 23. А. С. Смогоржеский. О геометрии Лобачевского.

Вып. 24. Б. И. Аргунов и Л. А.Скорняков. Конфигурационные теоремы.

Вып. 25. Л. С Смогоржевский. Линейка в геометрических построениях.

Вып. 26. Б. А. Трахтенброт. Алгоритмы и машинное решение задач.

Вып. 27. В. А. Успенский. Некоторые приложения механики к математике.

Вып. 28. Я. Л. Архангельский и Б. И. Зайцев. Автоматические цифровые машины.

Вып. 29. А. Н. Костовский. Геометрические построения одним циркулем.

Вып. 30. Г. Е. Шилов. Как строить графики.

Вып. 31. А. Г. Дорфман. Оптика конических сечений.

Вып. 32. Е. С. Вентцель. Элементы теории игр.

Вып. 33. Л. С. Барсов. Что такое линейное программирование.

Вып. 34. Б. Е. Маргулис. Системы линейных уравнений.

Вып. 35. Н. Я. Виленкин. Метод последовательных приближений.

Выи. 36. В. Г. Болтянский. Огибающая.

Вып. 37. Г. Е. Шилов. Простая гамма (устройство музыкальной шкалы).

Вып. 38. Ю. А. Шрейдер. Что такое расстояние?

Вып. 39. Н. Н.Воробьев. Признаки делимости.

Вып. 40. С. В. Фомин. Системы счисления.

Вып. 41. Б. Ю. Коган. Приложение механики к геометрии.

Вып. 42. Ю. И. Любич и Л. А. Шор. Кинематический метод в геометрических задачах.

Вып. 43. В. А. Успенский. Треугольники Паскаля.

Вып. 44. И. Я. Бакельман. Инверсия.

Вып. 45. И. М. Яглом. Необыкновенная алгебра.

Вып. 46. И. М. Соболь. Метод Монте-Карло

Вып. 47. Л. А. Калужнин. Основная теорема арифметики.

Вып. 48. Л. С. Солодовников. Системы линейных неравенств.

Вып. 49. Г. Е. Шилов. Математический анализ в области рациональных функций.

Вып. 50. В. Г. Болтянский, И. Ц. Гохберг. Разбиение фигур на меньшие части.

Вып. 51. Н. M. Бескин. Изображения пространственных фигур.

Вып. 52. Н. М. Бескин. Деление отрезка в данном отношении.

Вып. 53. Б. А. Розенфельд и И. Д. Сергеева. Стереографическая проекция.