/
Author: Соминский И.С.
Tags: анализ математика естественные науки серия популярные лекции по математике математическая индукция
Year: 1965
Text
Лопилярные лекции ПО МАТЕМАТИКЕ И.С.СОМИНСКИЙ МЕТОД МАТЕМАТИЧ ЕСКОЙ индукции
ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ ВЫПУСК 3 И. с. соминский МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ ИЗДАНИЕ СЕДЬМОЕ ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1965
512 С 61 УДК 517. 11 (023) Илья Самойлович Соминский Метод математической индукции М. , 1965 г., 56 стр. с илл. Редактор A. Z7. Баева Техн, редактор Л. Ю. Плакше Корректор Е. А. Белицкая Сдано в набор 28/1II 1965 г. Подписано к печати 15/VII 1965 г. Бумага 84 х 1081/з2 Физ. печ. л. 1,75. Условн. печ. л. 2,87. Уч.-изд. л. 2,83. Тираж 75000 экз. Т-10223. Цена книги 9 коп. Заказ № 1384 Издательство «Наука». Главная редакция физико-математической литературы. Москва, В-71, Ленинский проспект, 15. Ленинградская типография № 2 имени Евгении Соколовой Главполиграфпрома Государственного комитета Совета Министров СССР по печати. Измайловский пр., 29.
СОДЕРЖАНИЕ От издательства......................................... 4 Введение ............................................... 5 § 1. Доказательства тождеств; задачи арифметического харак- тера (примеры 1—13; задачи 1—16)................... 15 § 2. Тригонометрические и алгебраические задачи (примеры 14—18; задачи 16—23).................................... 27 § 3. Задачи на доказательство неравенств (примеры 19—24; задачи 24—27)........................................... 31 § 4. Доказательство некоторых теорем элементарной алгебры методом математической индукции (теоремы 1—7).... 37 /О. А. Гастев. Послесловие............................. 42 Указания и решения .................................... 47 1*
ОТ ИЗДАТЕЛЬСТВА Книжка И. С. Соминского «Метод математической индук ции», изданная впервые в 1950 г. и пользовавшаяся большим успехом, переведена на несколько иностранных языков. В серии «Популярные лекции по математике» появилось шесть ее изданий (начиная с третьего — стереотипных). Настоящее издание, подготовленное к печати уже без участия автора (скончавшегося 25 июля 1962 г.), отличается от предыдущего издания 1961 г, незначительными редакци- онными изменениями, некоторым расширением вводной части книги (произведенным с использованием текста упомянутой на стр. 44—45 книги Л. И. Головиной и И М. Яглома), а также кратким послесловием, написанным Ю. А. Гастевым. Немногочисленные подстрочные примечания автора после- словия и редактора всюду отмечаются звез точками; сноски, принадлежащие автору, нумеруются.
ВВЕДЕНИЕ Утверждения подразделяются на общие и частные. Приведем примеры общих утверждений. Все граждане СССР имеют право на образование. Во всяком параллелограмме диагонали в точке пере- сечения делятся пополам. Все числа, оканчивающиеся нулем, делятся на 5. Соответствующими примерами частных утверждений являются следующие: Петров имеет право на образование. В параллелограмме ABCD диагонали в точке пересечения делятся пополам. 140 делится на 5. Переход от общих утверждений к частным называется дедукцией. Рассмотрим пример. Все граждане СССР имеют право на образование. (1) Петров — гражданин СССР. (2) Петров имеет право на образование. (3) Из общего утверждения (1) при помощи утверждения (2) получено частное утверждение (3). Переход от частных утверждений к общим называется индукцией. Индукция может привести как к верным, так и к неверным выводам. Поясним это двумя примерами. 140 делится на 5. (1) Все числа, оканчивающиеся нулем, делятся на 5. (2) Из частного утверждения (1) получено общее утвержде- ние (2). Утверждение (2) верно. 140 делится на 5. (1) Все трехзначные числа делятся на 5. (2) 2 И. С. Соминский 5
Из частного утверждения (1) получено общее утвержде- ние (2). Утверждение (2) неверно. Спрашивается, как пользоваться в математике индукцией *), чтобы получать только верные выводы? Ответ на этот вопрос и дается в этой книжке. 1. Рассмотрим сначала два примера индукции, недопу- стимой в математике. Пример 1. Пусть С __ 1 I 1 I 1 _L -J________________1 " ~ ! . 2 ' 2 • 3 ‘ 3 • 4 ••• /? (л + 1) ’ Легко проверить, что s 1 ~ 1 2 — 2 * S - 1 I 1 - 2 ' с 2 ~ 1.2 + 2 • 3 3 ’ S __J_____, 1 | 1 -3 - 3“ 1.2^ 2-3 Т 3.4 “ 4 ’ На основании полученных результатов утверждаем, что при всяком натуральном п — п 4.1 • Пример 2. Рассмотрим трехчлен х1 4~ х 4- 41, на кото- рый обратил, внимание еще Л. Эйлер. Подставим в этот трехчлен вместо х нуль, получим простое число 41. Под- ставим теперь в эуот же трехчлен вместо х единицу, получим опять простое число 43. Продолжая подставлять в трех- член вместо х последовательно 2, 3, 4, 5, 6, 7, 8, 9, 10, получаем всякий раз простое число 47, 53, 61, 71, 83, 97, 113,. 131, 151. На основании полученных результа- тов утверждаем, что при подстановке в трехчлен вместо х любого целого неотрицательного числа всегда в ре- зультате получается простое число. Почему рассуждения, приведенные в этих примерах, не- допустимы в математике? В чем порочность выводов, которые нами сделаны? Дело в том, что в обоих этих рассуждениях мы высказали общее утверждение относительно любого п (во вто- *) См. Послесловие, стр. 42—46. 6
ром примере относительно любого х) только на основании того, что это утверждение оказалось справедливым для н е- которых значений п (или х). Индукция широко применяется в математике, но при- менять ее надо умело *). При легкомысленном же отношении к индукции можно получить неверные выводы. Так, если в примере 1 сделанное нами общее утвержде- ние случайно оказывается верным, как это доказано ниже в примере 4, то в примере 2 наше общее утверждение оказалось неверным. В самом деле, при более внимательном изучении трех- члена х24~* + 41 обнаружили, что он равен простому числу при х = 0, 1, 2, ...» 39, но при х = 40 этот трех- член равен 412, т. е. числу составному**). 2. В примере 2 мы встретились с утверждением, спра- ведливым в 40 частных случаях и все же вообще оказавшимся несправедливым. Приведем еще несколько примеров утверждений, которые справедливы в нескольких частных случаях, а вообще не- справедливы. Пример 3. Двучлен х"—1, где п — натуральное число, представляет для математиков большой интерес. Достаточно сказать, что он тесно связан с геометрической задачей о делении окружности на п равных частей. Не удивительно по- этому, что двучлен этот всесторонне изучается в математике. Математиков, в частности, интересовал вопрос о разложении этого двучлена на множители с целыми коэффициентами. Рассматривая эти разложения при многих частных значе- ниях п, математики наблюдали, что все коэффициенты раз- ложения по абсолютной величине своей не превосходят еди- ницы. В самом деле, х — 1 = х — 1, х2-1 = (х — 1)(х4~ х3 — 1 = (х •— 1)(х24~х 4- О* X4 — 1 = (х — 1)(х + 1)(х2 4- 1), х5 — 1 — (х — 1)(х4 х2 х О, х6 — 1 -(х 1)(х2 + х 4- 1)(х2 — х 4* 1), *) См. Послесловие, стр. 42—46. **) И уж совсем сразу бросается в глаза, что при х = 41 л2 4- х + 41 — 412 4- 41 4- 41 делится на 41. 2* 7
были составлены таблицы, в пределах которых коэффи- циенты этим свойством обладали. Попытки доказать этот факт для всякого п успеха не имели. В 1938 г. в журнале «Успехи математических наук» (вып. IV) была опубликована заметка выдающегося совет- ского математика Н. Г. Чеботарева, в которой он предложил нашим математикам выяснить этот вопрос. Эту задачу решил В. Иванов1). Оказалось, что указан- ным свойством обладают все двучлены хн — 1, степень кото- рых меньше 105. Одним же из множителей х105—1 является многочлен х48 4- х47 + х46 — х43 — х42 — 2х11 — х40 — х39 + 4 х36 4~ х35 4~ х34 + х33 4- х32 4~ Л;31 — х28 — х26 — х">1 — — х22 — х20 4~ х17 4- х16 4 х15 4- х14 4” %13 + 4“ х12 — х9 — х8 —- 2х7 — х6 — х5 4~ х2 4' + 1» уже не обладающий этим свойством. Пример 4. Рассмотрим числа вида 22 4~ 1- При п = 0. 1, 2. 3. 4 числа 22°4- 1 = 3, 22‘ 4- 1 = 5, 2? + 1 = 17. 2^4 1 = 257, 22' 4 1 = 65 537 — простые. Замечательный французский математик XVII в. П. Ферма предполагал, что все числа такого вида — простые. Однако в XVIII в. Л. Эйлер нашел, что 225 4~ 1 = 4 294 967 297 = 641 • 6 700 417 — составное число. Пример 5. Знаменитый немецкий математик XVII в., один из создателей так называемой «высшей математики», Г. В. Лейбниц доказал, что при всяком целом положи- тельном п число п3— п делится на 3, число п5 — п делится на 5, число п7— п делится на 7*). На основании этого он предположил было, что при всяком нечетном /г и любом натуральном п число nk—п делится на kt но скоро сам заметил, что 29 — 2 = 510 не делится на 9. Пример 6. В ошибку такого же рода впал однажды известный советский математик Д. Л. Граве, предположив, что для всех простых чисел р число 2;’-1—1 не делится ’*) «Успехи математических наук», вып. IV, 1941, стр. 313—317. *) См., например, книгу: ДО. Ш к л я р с к и й, Н. Н. Че н- цов, И. М. Я г л о м, Избранные задачи и теоремы элементарной математики, ч. 1, Физматгиз, М., 1959 (задачи 27а), б), в)). 3
на р2. Непосредственная проверка подтвердила это пред- положение для всех простых чисел р, меньших тысячи. Вскоре, однако, было установлено, что 21092— 1 делится на 10932 (1093 — простое число), т. е. предположение Граве оказалось ошибочным. Пример 7. На сколько частей делят пространство п пло- скостей, проходящих через одну точку, если никакие три из них не проходят через одну прямую? Рассмотрим простейшие частные случаи этой задачи. Одна плоскость делит пространство на две части. Две плоскости, проходящие через одну точку, делят пространство на четыре части. Три плоскости, проходящие через одну точку, но не проходящие через одну прямую, делят пространство на восемь частей. На первый взгляд может показаться, что с увеличением числа плоскостей на единицу количество частей, на которые разбивается пространство, увеличивается вдвое, и, таким обра- зом, четыре плоскости разобьют пространство на 16 частей, пять — на 32 части, а вообще п плоскостей разобьют про- странство на 2п частей. В действительности это не так, а именно: четыре плоскости разбивают пространство на 14 частей, пять плоскостей — на 22 части. Можно доказать, что п плоскостей разбивают про- странство на п(п—1)4-2 частей*). Пример 8. Приведем еще один весьма убедительный при- мер. Подставляя в выражение 991п2-|-1 вместо п последо- вательно целые числа 1, 2, 3.....мы никогда не получим числа, являющегося полным квадратом, сколько бы дней или даже лет мы ни посвятили этим вычислениям. Однако если мы сделаем отсюда вывод, что все числа такого вида не являются квадратами, то мы ошибемся. На самом деле ока- зывается, что среди чисел вида 991n2—|— 1 имеются и квад- раты: только наименьшее значение nt при котором число 991n2+ 1 есть полный квадрат, очень велико. Вот это число: п = 12 055 735 790 331 359 447 442 538 767. Рассмотренные примеры позволяют сделать простой и в то же время важный вывод. Утверждение может бить справедливым в целом ряде частных случаев и в то же время несправедливым вообще. *) Решение см. ниже, на стр. 25—26, пример 13. 9
3- Теперь возникает такой вопрос. Имеется утверждение, справедливое в нескольких частных случаях. Все частные случаи рассмотреть невозможно. Как же узнать, справедливо ли это утверждение вообще? Этот вопрос иногда удается решить посредством приме- нения особого метода рассуждений, называемого методом математической индукции (полной индукции, совершенной индукции). В основе этого метода лежит принцип математи- ческой индукции, заключающийся в следующем: Утверждение справедливо для всякого натураль- ного п, если: 1) оно справедливо для л= 1 и 2) из спра- ведливости утверждения для какого-либо произволь- ного нашурального n = k следует его справедливость для п — k 4- 1 ♦ Доказательство*). Предположим противное, т. е. предположим, что утверждение справедливо не для всякого натурального п. Тогда существует такое натуральное т. что 1) утверждение для п = т несправедливо, 2) для всякого п, меньшего т, утверждение справедливо (иными словами, т есть первое натуральное число, для которого утверждение несправедливо). Очевидно, что w > 1, так как для п=\ утверждение справедливо (условие 1). Следовательно, — 1— натураль- ное число. Выходит, что для натурального числа т — 1 утверждение справедливо, а для следующего натурального числа т оно несправедливо. Это противоречит условию 2. Конечно, при доказательстве принципа математической индукции мы пользовались тем, что в любой совокупности натуральных чисел содержится наименьшее число. Легко видеть, что это свойство в свою очередь можно вывести *) Начинающийся здесь текст до п. 4 читатель может опустить без ущерба для понимания дальнейшего. Дело в том, что упоми- наемый ниже принцип наименьшего числа, с помощью которого здесь доказывается принцип математической индукции, ничуть не более (хотя и не менее) очевиден, чем сам принцип математической индукции. С другой стороны, эти два предложения, как показывает более глубокий их анализ, оказываются эквивалент- ными только после принятия дополнительных допущений. Ограни- чимся поэтому принятием принципа математической индукции как интуитивно чрезвычайно убедительного допущения и запомним, что он является одной из а к с и о м, определяющих натуральный ряд чисел. Подробнее по этому поводу см. Послесловие и указанную там литературу. Ю
как следствие из принципа математической индукции. Таким образом, оба эти предложения равносильны. Любое из них можно принять за одну из аксиом, определяющих натуральный ряд, тогда другое будет теоремой. Обычно за аксиому при- нимают как раз сам принцип математической индукции. 4. Доказательство, основанное на принципе математи- ческой индукции, называется доказательством методом математической индукции. Такое доказательство необ- ходимо должно состоять из двух частей, из доказательства двух самостоятельных теорем: Теорема 1. Утверждение справедливо для п=\. Теорема 2. Утверждение справедливо дляп=к-\Л, если оно справедливо для n = k, где k — какое-либо произвольное натуральное число. Если обе эти теоремы доказаны, то на основании прин- ципа математической индукции утверждение справедливо для всякого натурального п. Пример 9. Вычислить сумму (см. пример 1) с - + 1 1 1.2 ' 2-3 ' 3-4^**’ ' п (п -hl)’ Мы знаем, что Q 1 с — q 3 q 4 д1— 2’’ °2— 3"» д3 — Т» д4 — у- Теперь мы не повторим ошибку, допущенную в при- мере 1, и не станем сразу утверждать, что при всяком на- туральном п с — п Будем осторожны и скажем, что рассмотрение сумм S2, 53, S4 позволяет высказать гипотезу (предположение), с п „ что = при всяком натуральном п. При этом мы знаем, что гипотеза эта верна при п=1, 2, 3, 4. Для про- верки гипотезы воспользуемся методом математической индукции. Теорема 1. Для п = 1 гипотеза верна, так как Sj = у. Теорема 2. Предположим, что гипотеза верна для n = kt т. е. что с _ 1 । 1 . । I _ k k~ 1«2 ‘ 2*3 ’ k(k + l) — k±l 9 11
где k — некоторое натуральное число. Докажем, что тогда гипотеза обязана быть верной и для n = k-\-\t т. е. что с _ * + 1 + k 4-2 * Действительно, 5Л + ! = + (Л 4-1) (Л 4-2) ’ следовательно, по условию теоремы, _____ k . 1 k- 4** 2Aj -J~ 1 k -j-1 k^~~ T+T ' (£ 4- 1) (£ 4” 2) (£4-1)(*4-2) £4-2 • Обе теоремы доказаны. Теперь на основании принципа математической индукции мы утверждаем, что S' 11 п 4- 1 при всяком натуральном п. Замечание 1. Необходимо подчеркнуть, что доказа- тельство методом математической индукции безусловно тре- бует доказательства обеих теорем, 1 и 2. Мы уже видели, к чему привело пренебрежительное отношение к теореме 2 (пример 2). Сейчас мы покажем, что нельзя опускать и теорему 1. Рассмотрим пример. Пример 10, Теорема. Всякое натуральное число равно следующему за ним натуральному числу. Доказательство проведем методом математической индук- ции. Предположим, что £=:/?4-l. (1) Докажем, что Л 4- 1=£-4-2. (2) Действительно, прибавив к каждой части равенства (1) по 1, получим равенство (2). Выходит, что если утверждение справедливо для п — k, то оно справедливо и для n = k-\- 1. Теорема доказана. Следствие. Все натуральные числа равны. Где же здесь ошибка? Ошибка заключается в том, что первая теорема, необходимая для применения принципа мате- матической индукции, не доказана и не верна, а доказана только одна вторая теорема. 12 . я • 4
Теоремы 1 и 2 имеют свое особое значение. Теорема 1 создает, так сказать, базу для проведения индукции. Тео- рема 2 дает право неограниченного автоматического расши- рения этой базы, право перехода от данного частного случая к следующему, от п к п -f- 1. Если не доказана теорема 1, а доказана теорема 2 (см. пример 6), то, следовательно, не создана база для проведе- ния индукции, и тогда бессмысленно применять теорему 2, так как и расширять-то, собственно, нечего. Если не доказана теорема 2, а доказана только теорема 1 (см. примеры 1 и 2), то, хотя база для проведения индукции и создана, право расширения этой базы отсутствует. Замечание 2. Метод математической индукции разо- бран выше для простейшего случая. В более сложных слу- чаях формулировки теорем 1 и 2 должны быть соответственно изменены. Иногда вторая часть доказательства опирается на спра- ведливость утверждения не только для n = k, но и для п — k — 1. В этом случае утверждение в первой части должно быть проверено для двух последовательных значений п. Иногда также вторая часть доказательства состоит в уста- новлении справедливости требуемого рассуждения для ка- кого-то значения п в предположении справедливости его для всех натуральных чисел kt меньших п. Ниже читатель найдет примеры такого рода (см. пример 7 на стр. 20). Иногда утверждение доказывается не для всякого нату- рального п, а для всякого целого /г, превосходящего неко- торое целое т *). В этом случае в первой части доказатель- ства утверждение проверяется для п = т-\-\, а если это требуется, то и для нескольких последующих значений п. 5. Вернемся еще раз к примеру 1 для выяснения одной существенной стороны метода математической индукции. Изучая сумму с _ 1______। 1 п ~ 1 -2 2-3 1 при разных значениях п, мы подсчитали, что Q __ 1 Q _____ 2 Q _____ 3 __ 4 д1— ~2*' d2 — J» — °4 — У’ *) Так, например, любое утверждение, касающееся свойств про- извольных и-угольников, имеет смысл лишь при л > 3. 3 И. С. Сом и некий 13
и это навело нас на гипотезу, что и при всяком п S — п Для проверки гипотезы мы использовали метол математи- ческой индукции. Нам повезло, мы высказали гипотезу, которая подтверди- лась. Если бы мы высказали гипотезу неудачно, то порочность гипотезы обнаружилась бы при попытке доказательства теоремы 2. Пример 11. Рассмотрим суммы 2*3 ’ ’ n(n + \)- Допустим, что, изучая Sn, мы высказали гипотезу с — "+1 п~ Зл-Н ’ При п=\ формула (1) верна, так как = Предполо- жим, что формула (1) верна при n = k, т. е. е _±+1 °* — 3*4-1 ’ (1) Попытаемся доказать, что формула (1) верна и при n = *4~ 1, т. е. что о _ * + 2 * + 1 — 3*4*4 • Имеем ;к+1 — sk4- 1)(^4-2) = _ *4-1 , 1 _ 4-w 4-8*4-2 — 3*4-1 + (* + 1){*4-2) ~ (*4-1)<*4-2)(3*4-1) ’ т. е. результат получился иной. Выходит, что из справедливости формулы (1) при п = * не следует ее справедливость при n = k-}-\. Мы обна- ружили, что формула (1) неверна. Таким образом, метод математической индукции позволяет в поисках общего закона испытывать возни- кающие при этом гипотезы, отб расывать ложные и утверждать истинные. Для того чтобы научиться применять метод математи- ческой индукции, надо рассмотреть достаточное количество задач. И
Чтобы не повторять без конца слова «Теорема 1» и «Теорема 2», мы условимся в дальнейшем помечать пер- вую и вторую части доказательства по индукции (эти части и составляют содержание двух теорем, доказательство ко- торых равносильно пользованию методом индукции) зна- ками 1° и 2°. Кроме того, мы будем различать примеры, снабженные подробными решениями, и задачи, предназна- ченные для самостоятельной работы читателя. В конце книги будут приведены указания, относящиеся к решению всех при- веденных в тексте задач. Иногда эти указания представляют собой лишь ссылку на иную, доступную читателям литера- туру; в других случаях они содержат полное решение задачи. § 1. ДОКАЗАТЕЛЬСТВА ТОЖДЕСТВ; ЗАДАЧИ АРИФМЕТИЧЕСКОГО ХАРАКТЕРА Пример 1. Выпишем в порядке возрастания нечетные положительные числа 1, 3, 5, 7,... Обозначим первое из них uv второе третье zz3 и т. д., т. е. ux — \t zz2 = 3, zz3 = 5, zz4 = 7, ... Поставим перед собой такую задачу: составить формулу, выражающую нечетное число ип через его номер п. Решение. Первое нечетное число можно записать так: zz1 = 2 • 1 — 1; (1) второе нечетное число zz2 можно записать так: zz2 = 2-2 —1; (2) третье нечетное число zz3 можно записать так: z/3 = 2 • 3 — 1. (3) Внимательно рассматривая равенства (1), (2), (3), можно вы- сказать гипотезу, что для получения любого нечетного числг: достаточно от удвоенного номера его отнять 1, т. е. для я-го нечетного числа имеем форму чу ип = 2п — 1. (4) Докажем, что формула эта справедлива. 1°. Равенство (1) показывает, что для п = 1 формула (4) справедлива. 3* 15
2°. Предположим, что формула (4) справедлива для n = kt т. е. k-e нечетное число имеет вид uk — 2k — 1. Докажем, что тогда формула (4) обязана быть справедливой и для (k + 1)-го нечетного числа, т. е. что (k 4- 1)-е не- четное число имеет вид и*и = 2(*+ О— 1. или, что все равно, + 1 = 2& 4 1. Для получения (/? + 1)-го нечетного числа достаточно к Х?-му нечетному числу прибавить 2, т. е. икП = uk + 2- Но, по условию, uk — 2k—1. Значит, ukvX = (2k — 1)4- 2 — 2/г 4 1, что и требовалось доказать. Ответ. ип = 2п — 1. Пример 2. Вычислить сумму первых п нечетных чисел. Решение. Обозначим искомую сумму Sn, т. е. 1 4 3 45 4 • • • + (2*~ 1). Для решения таких задач в математике существуют го- товые формулы. Нам интересно решить эту задачу, не при- бегая к готовой формуле, а пользуясь методом математи- ческой индукции. Для этого прежде всего надо построить гипотезу, т. е. просто постараться угадать ответ. Придаем п последовательно значения 1, 2, 3, .. . до тех пор, пока у нас не накопится достаточно материала, чтобы на основе его построить более или менее надежную гипотезу. После этого останется только эту гипотезу проверить ме- толом математической индукции. Имеем Si=l, S2 = 4, S3 = 9, S4 = 16, S5==25, S6 = 36. Теперь все зависит от наблюдательности решающего за- дачу, от его способности по частным результатам угадать общий. Полагаем, что в данном случае легко заметить, что 5\=12. S2 = 22. S3 = 32, S4 = 42. 16
На основе этого можно предположить, что вообще S„ = и'2. Докажем, что гипотеза эта справедлива. 1°. При п = I сумма представляется одним слагаемым, равным 1. Выражение п2 при п=\ также равно 1. Значит, при п — 1 гипотеза верна. 2J. Допустим, что гипотеза верна для n = k, т. е. Sk = k2. Докажем, что тогда гипотеза должна быть верна и для п = k 4- 1, т. е. (*+ I)2. Действительно, 4~ (2& + 1). Но Sk = k2 и потому ^+i = *2 + (2£ + 1) = (£+ I)2, что и требовалось доказать. Ответ. Sn = п2. Задача 1. Найти ип, если известно, что = 1 и что при всяком натуральном k > 1 uk = llk-\ + 3- Указание. = 3 < 1 — 2, и2 = 3 • 2 — 2. Задача 2. Найти сумму Sn = 1 + 2 4- 4- 23 4- ... 4- 2"*1. Указание. = 2—1, S2 = 22—1, S3 = 23—I. Пример 3. Доказать, что сумма п первых чисел нату- п (п 4-1) рального ряда равна —— Решение. Эта задача отличается от предыдущих тем, что гипотезу здесь строить не надо, она дана. Нужно только доказать, что гипотеза верна. Обозначим искомую сумму Snt т. е. = 1 4” 2 4~ 3 4- • • • т я. 1°. При п = 1 гипотеза верна. 2°. Пусть < 119 3 1 । а Ze (# 4- 1) — 1 4- 2 Т з т ... 4- Ze =---------- 17
Покажем, что о __(£+W + 2) ^*-11— 2 ’ В самом деле, S», = *,. + (* + 1) = ^Ц^ + № + 1)= + * . Задача решена. Пример 4. Доказать, что сумма квадратов п первых чисел п (л + 1)(2л + 1) натурального ряда равна -1---5— Решение. Пусть S2 (zz) — I222-|-З2-(-••• я2. Г. М1)^Р=Аа + 1><? + >. 2°. Предположим, что s,w="(“+1>6(2"+'»: Тогда Хг(«+1)=1’+2!+3!+...+«’ + (»+!)’ = = "<1+1)№+Ч +(д+ ,)8 и окончательно S2 (az + 1)^ (и + 1)[(и+1)+1][2(и + 1)+1] . Пример 5. Доказать, что 5д = 1 — 22Н- 32 — 42+ ... +(—1)л-’п2 = __1)«-1 (я +1) Решение. 1э. При п=1 гипотеза, очевидно, верна ((-1)0=1). 2°. Пусть Sft= 1 — 224-32— ... -И—1)*-1&2 = (— 1/-1 А^ + 1),. Докажем, что sA+1 = 1 - 2?+З2 - ... + (—1)*-1 &2+(- 1/ (k 4- I)2 = _/ (* + 1)(*4-2) 18
Действительно, Sft+i = Sft + (-D*(A+l)2 = =(_ 1/-1 -н—I/(k + I)2= = (-1/ [(£ + 1)- 4] (* + 1) = (-D* +*-+-1)2(* + 2)-. Задача 3. Доказать, что 12_|_32_|_52„|_ _ Ч-(2п— 1)2 = Д(—~.1)<2"+1) , о Задача 4. Доказать, что сумма кубов п первых чисел г п (п 4* 1) 12 натурального ряда равна —. Задача 5. Доказать, что 1 +-х4-х2+ -Ьхл=4^—-р- (х+1). Пример 6. Доказать, что 1.24-2.34-3.44- ... 4-(я - 1)в = -(-~1)”(п + 1), о Решение. Г. 1 . 2 = - *. 2°. Если 1.2 4-2. 34-3. 4 + ... +(п~ 1)п=:-^^-1-)Аг(Аг + 1)>, то 1’2 4“ 2 • 3 4" 3 ' 4 4* • « • “1“ (п — 1) Z2 4“ 22 (/2 4" 1)== (22—1) 22(22+1) я + _ 27 (П 4- 1) (П 4-2) , 3 3 Пример 6 можно также вывести из результатов при- меров 3 и 4, если заметить, что 1.2 + 2.34-3.4+ ... +(я — 1)п = = 1(14-1)4-2(2-+1)+3(3 + 1)+ ... ... +(/2—1)1(22- 1)4- 1| = (12 + 22+ ... -+(/2— 1)214- + [1 4-24- ... +(22— 1)]. Задача 6. Доказать, что 1.2.3 + 2- 3.4+3-4.5+ ... 4~ 22 (п + 1) (/2 + 2) = _ /г(/г+1)(/2 + 2)(п + 3)_ ~’ 4 19
Задача 7. Доказать, что 1-3 ^3-5 ' ••• -Г (2п— 1)(2«+ 1) 2л+ 1 Задача 8. Доказать, что 1' , 22 , л2 _____ п (п -f- 1) 1-ЗЧ.5 ' •“ ~Ь(2л—1)(2« +1)~ 2(2и+ 1) ‘ Задача 9. Доказать, что _L + JL4._1_+ +_______!______= —2_. 1.4 ‘ 4 • 7 “ 7 • 10 ' “ (Зл — 2) (Зл 4- 1) Зл 4- 1 Задача 10. Доказать, что + +_1_+ . +_____________*______= L_ 1 -5 “ 5-9 ’ 9- 13“ (4л — 3)(4л 4-1) 4л4-1 Задача 11. Доказать, что а (а + 1) ' (а 4- 1) (а -Ь 2) ' ’ * 4“ л — 1) (я + п) а (а 4- п) * Пример 7. Доказать, что если v0=2, v{ = 3 и для всякого натурального k имеет место соотношение 1 = Зх»* — 2г»л_п ^ = 2"+1. Решение. Г. Для п = 0 и /г — 1 утверждение спра- ведливо по условию. 2°. Предположим. что Тогда = ^ = 2*4-1. vA4J = 3(2* 4- D — 2(2*-1 Н- 1) = 2*и 4- 1. Задача 12. Доказать, что если и для всякого натурального k > 2 имеет место соотношение = <а + Р) «»-1 — <Ф'4-2> аЛ,1_рЛ^1 а — р 20
Пример 8, Произведение 1-2.3... п обозначается зна- ком п\ и читается так: «п факториал». Полезно запомнить, что 1 != 1, 21 = 2, 31 = 6, 4! = 24, 51= 120. Вычислить 5Й=1- 11+2.21 + 3.3!+ ... + п-п! Решение. S1== 1 . 1 != 1, S2 = 1 • 1 ! + 2 • 2! = 5, S3 = 1 • 1 ! + 2 • 2 ! + 3 • 3 ! = 23. S4 =1-11+2.21 + 3.31+4.4!=119. Присматриваясь к этим результатам, можно заметить, что S1 = 2I—1, S2=31—1, S3=41—1, S4 = 5I—1. Это дает возможность высказать гипотезу, что $„ = (« 4-1)1- 1. Проверим эту гипотезу. 1°. Для п—1 гипотеза верна, так как Sj = 1 • 1! = 2! — 1. 2°. Пусть = 1 • 1! 4-2 • 2! 4- ... 4-й-й! = (й4-1)1 —1. Покажем, что 5я + 1 = 1 • 11 4-2 • 2 >4- ... +k • й !4-(й4-1)(й 4- 1)1 = = (й 4- 2)! — 1. Действительно, 1 + (А 4- D(*4- 1)1 = [(А 4-1)1-И+ 4-(й4- 1)(й4-1)! = (й4-1)![1 +(й + 1)] - 1 = = (Й4- 1)!(й4-2)— 1 =(й4-2)! — 1. Задача 13. Доказать тождество _J___. 2 < 4 , 8__, , 2« __ 1 ' 1 4-х2 ' 1 4-х< “Г 1 + х« ~г • • • -г ! 4_Х2« ~~ 1 + 1 — Л — 1 1—х2" + 1 ' 21
Пример 9. Дано: а + р — т, сф = а, Л2 = /п — —, . а Л а Аа = т------------, Ал—т--------------------и т. д., J а 4 а т-------г- т------------- т — 1 а т--------г т — I т. е. для k > 1 An + i = m — ~т~ ("»¥=!; a #= p). k Доказать, что Решение. Г. Докажем сначала, что формула (1) верна для п = 2. Но условию, А, = nt и _______ оф _az + P2 + a₽ — a — ;5 //z—!““ (а-|-Э)—1~ а + £ —1 ho формуле (1) ? (а2_ jb2) —(а_ю • Сократив последнюю дробь на a—р, имеем — с*2 + Р2 + — a ~~~ Р к р -— 1 чго4 и требовалось доказать. 26 fly сть формула И) справедлива для п = Л, т. е. . \ад": — р* + 1) — (а* — р*) k — ~k Т\ ( k~l !i~\\ • kr —р*) —(аЛ — p ) Докажем, что тогда она должна быть справедлива и для я — /г у- 1, т. е. Л^} (а*11 — |3ft + 1) —-(aA — pft) ’ Действительно, /1йм = /?1-ф- или ЛЛ)1=(а + Р) ft Z1ft 22
Пользуясь равенством (2), имеем A „+1 = (а + Р) - = (а* +1 — р* + 0 — (а* — (afe+2_pfe+2)_(a* + i_flfe + i) (a* + 1 —р* + 1) —(а*--р*) Теорема доказана. Задача 14. Упростить многочлен 1 X , Х(Х — 1) , 1чЛ Х(Х— 1) ... (X — /7-4-1) 1 4-----2!------••• -Н-1) --------------п!----------• Ответ, , . п (х— 1)(х —2) ... (х — и) k ' и! Пример 10. Доказать, что любое целое число рублей, большее 7, можно уплатить без сдачи денежными билетами, достоинством в 3 и 5 рублей. Решение. 1°. Для 8 рублей утверждение справедливо (ибо 8 руб. = 3 руб. 5 руб.). 2°. Пусть утверждение верно для k рублей, где k — целое число, большее или равное 8. Возможны два случая: 1) k рублей уплачивается одними трехрублевыми билетами и 2) k рублей уплачивается денеж- ными билетами, среди которых есть хоть один билет пяти- рублевого достоинства. В первом случае трехрублевых билетов должно быть не менее трех, так как в этом случае k > 8. Для того чтобы уплатить k 1 рубль, заменим три трехрублевых билета двумя пятирублевыми. Во втором случае для уплаты k -J- 1 рубля заменим один пятирублевый билет двумя трехрублевыми. Пример 11. Доказать, что сумма кубов трех последова- тельных натуральных чисел делится на 9. Решение. 1°. Сумма 13+23 4“ З3 делится на 9. Значит, утверждение справедливо, когда первым из трех последова- тельных натуральных чисел является 1. 2°. Пусть сумма &3+(&+ 1 )3—]—(&—}—2)3, где k — неко- торое натуральное число, делится на 9. Сумма (k -I- 1)3-Н (k 4- 2)3 + (k + 3)3 = = (ft+ l)3 + (ft + 2)3 + A3 + 9ft2_|_27ft + 27 = = ^3+(fe+l)3 + (* + 2)2l + 9(fe2+3ft + 3) 23
представляет собой сумму двух слагаемых, каждое из кото- рых делится на 9, а потому тоже делится на 9. Задача 15, Доказать, что при целом я О А„ = 11л+2+ 122п+1 делится на 133. Пример 12. Из 2п чисел 1, 2, .... 2п произволь- но выбрали п 4- 1 число. Доказать, что среди выбранных чи- сел найдутся хотя бы два числа, из которых одно делится на другое. Решение1). 1°. Для двух чисел 1, 2 утверждение справедливо. 2°. Допустим, что из 2п чисел 1, 2, ...» 2п, где п 2, удалось выбрать так п 1 число, что ни одно из них не делится на другое. Совокупность всех этих чисел обозначим для краткости Л4л41. Докажем, что тогда из 2п — 2 чисел 1, 2.....2п — 2 можно выбрать п чисел таких, что опять ни одно из них не будет делиться на другое. Возможны четыре случая: 1) Мп + 1 не содержит ни 2п—1, ни 2п. 2) содержит 2п—1 и не содержит 2/г. 3) Мп^л содержит 2п и не содержит 2п — 1. 4) Л4я+1 содержит и 2п — 1, и 2п. Случай 1. Исключим из Л4л + 1 какое-нибудь число. Останется п чисел, каждое из которых не больше, чем 2п — 2. Ни одно из этих чисел не делится на другое. Случай 2. Исключим из Л4л + 1 число 2п—1. Оста- нется п чисел, каждое из которых не больше, чем 2п~ 2. Ни одно из этих п чисел не делится на другое. Случай 3. Исключим из Л1л + 1 число 2п и опять по- лучим тот же результат. Случай 4. Прежде всего заметим, что в Л4л + 1 не со- держится число л, так как иначе в Л1л41 нашлось бы два числа (2п и п), из которых одно делится на другое. Исключим из Жл + 1 числа 2п—1 и 2п. Совокупность оставшихся zz— 1 чисел обозначим Mn_v Присоединим к /Ил-1 число п. Получим п чисел, каждое из которых не пре- восходит 2п — 2. Остается показать, что среди этих п чисел ни одно не делится на другое. J) Это решение принадлежит М. Фридману. 24
В Л1л + 1 не было двух чисел, из которых одно делится на другое. Значит, таких чисел не было и в Л1Л_Р Остается только убедиться в том, что таких чисел не появилось и тогда, когда мы к присоединили число /г. Для этого достаточно убедиться в том, что: 1) ни одно число, входящее в не делится на п и 2) число п не делится ни на одно из чисел, входящих в Мп_х. Первое вытекает из того, что все числа, входящие в Мп_19 не превосходят 2п — 2. Второе вытекает из того, что число 2п не делится ни на одно из чисел, входящих в Mn_v Итак, если допустить, что утверждение неверно для 2п чисел 1, 2, .... 2nt то оно неверно и для 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 число. Совокупность этих чисел обозначим Л1л + 1. Каждое четное число, входящее в Л4л+1, разделим на такую степень двойки, чтобы частное было нечетным. Сово- купность этих частных и всех нечетных чисел, входящих в /ИлИ, обозначим через А1л+ь В содержится п -f- 1 нечетное число, каждое из которых меньше 2п. Так как всех положительных нечетных чисел, меньших 2п, имеется всего п, то в Л1п±1 имеются хотя бы два равных числа. Каждое из этих чисел пусть равно Полученный результат означает, что в А1л+1 было два числа 2sk и 2*k (где одно из чисел s и t может равняться нулю). Но одно из чисел 2sk и 2lk делится на второе. Задача 16*). Доказать, что п различных прямых, про- веденных на плоскости через одну точку, делят плоскость на 2п частей. Пример 13. Доказать, что п плоскостей, проходящих через одну точку так, что никакие три из них не проходят *) Задача 16 и пример 13 отнесены к этому параграфу, посколь- ку они имеют, по существу, чисто арифметический характер, хотя и связаны с геОхметрнческой проблематикой. 25
через одну прямую, делят пространство на Ап = п(п— частей. Решение. 1°. Одна плоскость делит пространство на две части, и Д, = 2. Для п—\ утверждение справед- ливо. 2°. Предположим, что утверждение справедливо для n = kt т. е. k плоскостей делят пространство на k(k — 1)-|-2 частей. Докажем, что тогда &4-1 плоскостей делят пространство на k(k~|- 1)-|- 2 частей. Действительно, пусть Р есть (&4~ плоскость. С каждой из первых k плоскостей плоскость Р пересекается по неко- торой прямой и, таким образом, плоскость Р разбита на части посредством k различных прямых, проходящих через одну точку. На основании задачи 28 утверждаем, что плоскость Р разбита на 2k частей, каждая из которых представляет собой плоский угол с вершиной в данной точке. Первые k плоскостей делят пространство на некоторые многогранные углы. Некоторые из этих многогранных углов делятся посредством плоскости Р на две части. Общей гранью двух таких частей служит часть плоскости, ограниченная двумя лучами, по которым Р пересекается с гранями данного многогранного угла, т. е. один из 2k пло- ских углов, на которые плоскость Р разбита. Это означает, что число многогранных углов, разбивае- мых на две части плоскостью Р, не может быть больше, чем 2k. С другой стороны, каждая из 2k частей, на которые разбивается плоскость Р, в результате пересечения ее с пер- выми k плоскостями, является общей гранью двух много- гранных углов и таким образом делит многогранный угол, образованный первыми k плоскостями, на две части. Это означает, что число многогранных углов, которые разбиваются на две части плоскостью Р, не может быть меньше, чем 2k. Итак, плоскость Р разбивает на две части точно 2k частей пространства, образованных первыми k плоскостями. Поэтому если k плоскостей разбивают пространство на k(k — 1) —|—2 частей, &4-1 плоскость разбивает простран- ство на [k(k— 1) + 21Ч-2А? = ^(^+ 1)4-2 частей. Утверждение доказано. 26
§ 2. ТРИГОНОМЕТРИЧЕСКИЕ И АЛГЕБРАИЧЕСКИЕ ЗАДАЧИ Пример 14. Доказать тождество о л пп sin 2п 41 а cos а cos 2а cos 4а ... cos 2 а = . 2rt + 1sina Решение. Г. При п = 0 тождество справедливо, так 2°. Пусть тождество справедливо при n — k, т. е. о sin2*41a cos a cos 2a ... cos 2*a ==------. 2*+1 sin a Тогда оно справедливо и при n ==&-}- 1. Действительно, cos a cos 2a ... cos 2*a cos 2*+]a — __sin 2fe~l~1a cos 2fe+Ia sin +2a 2*+1sina 2*+2sina Пример 15. Доказать, что Hn = cos n0, если известно, что = cos 0; Л2 = cos 20 и для всякого натурального k > 2 имеет место соотношение Ak = 2cQsQAk_x — Ak_2. Решение. 1°. Утверждение справедливо при п=\ и п = 2°. Пусть Лл_2 = соз(£— 2)0, Ла,_1 = соз(£— 1)0. Тогда Ak = 2 cos 0 cos (k — 1)0 — cos (k — 2) 0 = cos kft. Пример 16. Доказать, что n 1 sin —g— x sin x + sin 2x-p ••• H-sinnx=—----------------sin-—-. sin-J Решение. 1°. При n=l утверждение справедливо. 27
2°. Пусть sin х 4- sin 2x + ... —|—sin/?A7 =-------------sin-y-. sin-y Тогда sin x-h sin 2x 4~ ... +sin^x + sin(^-p l)x = sin——x , 2 . kx . . / r * 1 x --------sin —4~ sin (* 4~ 1)* = sin-y . *4-1 Sin --!- 2 *л . r, . *4-1 sin 2sin —— x cos sin y 2 . *4-2 sin—2“ sin у sin —j ибо Л *4-1 . X . *4-2 . kx 2 COS-----X Sin у = Sin --2---x — sin —. Задача 17. Доказать, что 2 , 2/1 + 1 sin !— -5- + COS X 4- cos 2x 4- cos nx — — 2 2siny Задача 18. Доказать, что sin x 4-2 sin 2x +3 sin 3x4- ••• 4~ttsinnx = __ (/г 4~ 1) sin nx — n sin (/2 4~ 1) 4 sin2 у Задача 19. Доказать, что cos x 4- 2 cos 2x 4- ••• +/zc°sflx = __ (л 4” 1) cos лх — n cos (n 4- 1) x—1 x 4 sin2 у 28 0
Задача 20. Доказать, что 1 . х . 1 . х , . 1 . х 2~ ”2 । 2*"* *2^ 2Л 9/7 = -^Г ct£ — ct£ х (х Задача 21. Доказать, что arc ctg 3 + arc ctg 5 4- ... 4~ агс ctg(2n 4- 1) = = аге tg 2 4- аге tg у 4- ... 4- arc tg — — n аге tg 1. Пример 17. Доказать, что п /1 । п ' п9 I ПЛ । • . ПЛ \ (1 + 0 = 2 2 l^cos —Н sin —). Решение. 1°. При п=\ утверждение справедливо, так как l + i = 2^ (cos-J-Hsin-J). 2°. Пусть (1 +1)” = 2~ (cos 4- Isin . Тогда k 1 Ь.1.1 Q { kjZ k^\i \ л п I Л । .. Л \ (1 -f- /)*+’=22 (cos —-|-,sin—J 22 ^cos ^--f-zsin^-^ (*+ 1)я , . . (*+ 1)л\ = 2 2 (cos-2—--------}-zsin-——I, Задача 22. Доказать, что (|/3-/)'’==2"[cos^-/isin^j. Пример 18. Доказать теорему: Если в результате конечного числа рациональных действий (т. е. сложения, вычитания, умножения и деления) над ком- плексными числами х2, ..., хп получается число и, то в результате тех же действий над сопряженными комплекс- ными числами хр х2......хя получится число и9 сопря- женное с и. 4 И. С. Соминский 29
Решение. 1°. Прежде всего покажем, что утверждение верно для каждого из четырех действий над двумя комплекс- ными числами. Пусть Xj = а Ы, х2 = с + di. Тогда Xj —|— х2 == (л с) —(b —|— tZ) i = и, х1 4~ х2 = (а — bi) 4- (с — di) = (а 4- с) — (Ь 4“ d) i = и. Точно так же утверждение проверяется для вычитания, умно- жения и деления. 2°. Пусть теперь дано некоторое рациональное выраже- ние от комплексных чисел хр х2, .. ., хп. Вычисление такого выражения сводится, как известно, к последовательному выполнению одного из четырех действий над двумя комплекс- ными числами, причем действия эти могут быть занумерованы. Например, пусть ц_ Л|Л2 Ц- *1+*2 —*3 Для вычисления и достаточно произвести действия: 1) Х1Х2 = “1. 4) и3— х3—и4. 2) Х3Х4 = и2, 5) И] п2 = «5, 3) хг 4~ *2 = ^з, 6) и5:и4 = и. Предположим, что утверждение верно для всех выраже- ний, которые для вычисления их требуют не более k «дей- ствий». Термин «действие» здесь означает сложение либо вычитание, либо умножение, либо деление двух комплексных чисел. Покажем, что тогда утверждение должно быть верно и для выражений, требующих &4~1 «действий». Действительно, последнее (k-}~ 1)-е «действие» мы выпол- няем над числами и г/у, которые сами вычислялись посред- ством не более чем k «действий». В результате замены чисел хр х2, ..., хп сопряженными, числа ut и Uj заменяются сопряженными uk и а тогда и результат (&4~0"го «действия» над ними, т. е. число и, также заменится сопряженным числом и. Задача 23. Доказать, что при любом натуральном п (cos х 4~ I sin х)п = cos пх 4- Z sin пх. 30
§ 3. ЗАДАЧИ НА ДОКАЗАТЕЛЬСТВО НЕРАВЕНСТВ Пример 19. Доказать, что при любом натуральном п > J 1 I 1 I ! 1 13 и + И и + 2 + • ’ • 2п > 24 • Решение. Обозначим левую часть неравенств через 5Л. ю о 7 14 о 1 . 52 = -у2' — 24~> следовательно, при я = 2 неравенство справедливо. 13 2°. Пусть Sfe > при некотором k. Докажем, что тогда 13 и > “24 е Имеем с __J_ ।___________________!_I 1 Л k~~~ £4-1 "т" А?4-2 * “• * 2£ ’ 5 — _ 1 _ I * _1_!__1_ 1 । 1 °£ + 1— ^4-2^ £4-3 2£^2£4-1^2£4-2‘ Сравнивая Sk и 5Л + 1, имеем с _____с __ 1 I *__________1_ °£ + 1 °£— 2£4-1 2£4-2 £4-1’ т. е. с _________________с _________!_______ k 2 (£-|- 1) (2£ 4~ 1) ’ При любом натуральном k правая часть последнего ра- 13 венства положительна. Поэтому Но Sfe > о 13 значит, и S* + l >-24 • Задача 24. Найти ошибку. Утверждение. При любом натуральном п справедливо неравенство Т > 2п 4~ Ь Доказательство. Пусть неравенство справедливо при n = k, где k — некоторое натуральное число, т. е. 2*>2£-Н. (1) Докажем, что тогда неравенство справедливо и при п = k 4~ Ь т. е. 2ft + 1 > 2(Л+ 1)4- 1. (2) 4* 31
Действительно, 2* не меньше 2 при любом натуральном k. Прибавим к левой части неравенства (1) 2\ а к правой 2. Получим справедливое неравенство 2Л + 2* > 2k + 1 + 2, или 2* + 1 > 2{k -+ 1)+ 1. Утверждение доказано. Задача 25. При каких натуральных п справедливо не- равенство 2п > 2п + 1? Пример 20. При каких натуральных п справедливо не- равенство 2п > п-? Решение. При п—\ неравенство справедливо, так как 21 > I2. При п = 2 неравенство несправедливо, так как 22 = 22. При я=3 неравенство несправедливо, так как 23 < З2. При п = 4 неравенство несправедливо, так как 21 = 42. При п = 5 неравенство справедливо, так как 25 > 52. При п = 6 неравенство справедливо, так как 26 > 62. По-видимому, неравенство справедливо при п — 1 и при любом п > 4. Докажем это. 1°. При п = 5 неравенство справедливо. 2°. Пусть 2Л>^2, (1) где некоторое натуральное число, большее 4. Докажем, что 2*и >(&+ I)2. (2) Мы знаем, что 2* > 2k 4~ 1 при k > 4 (задача 44). Поэтому если мы к левой части неравенства (1) прибавим 2*, а к правой 2k 4~ 1, получим справедливое неравенство (2). Ответ. 2п > я2, когда п=1 и когда п > 4. Пример 21. Доказать, что (1 + а)п > 1 + па, где а > — 1, а =/= 0, п - натуральное число, большее 1. Решение. 1°. При п = 2 неравенство справедливо, так как а2 > 0. 32
2°. Пусть неравенство справедливо при n = k, где k — неко- торое натуральное число, т. е. (1+а)*> 1Ч-йа. (1) Покажем, что тогда неравенство и при n = k-\-\, т. е. (1 —f—сх) > 1 -|-(& 1)а. (2) Действительно, по условию, поэтому справедливо неравенство (1 + а)4+1>(1+^а)(1+а), (3) полученное из неравенства (1) умножением каждой части его на 1 4- а. Перепишем неравенство (3) так: (1 4-a)*+1 > 1 + (& + 1)а 4- /га2. Отбросив в правой части последнего неравенства положи- тельное слагаемое &а2, получим справедливое неравенство (2). Задача 26. Доказать, что при любом натуральном п > 1 ТТ+У2+ ••• Задача 27. Доказать, что при любом натуральном п > 1 4я (2гг)! л-Н < (nl)2 * Пример 22. Доказать, что 2п-\ап + Ьп)>(а+Ь)п, (1) где a^b, п—натуральное число, большее i. Решение. 1°. При п = 2 неравенство (1) принимает вид 2(а2+ b2)>(a+b)2. (2) Так как а =# Ь, то справедливо неравенство (а — Ь)2 > 0. (3) Прибавив к каждой части неравенства (3) по (а + ft)2, полу- чим неравенство (2). Этим доказано, что при п = 2 неравенство (1) справедливо. 2\ Пусть неравенство (1) справедливо при n = kt где k — некоторое натуральное число, т. е. 2*''(я*+ />*)> (<* + *)*• 0) 33
Докажем, что тогда неравенство (1) должно быть спра- ведливо и при n = k-\- 1, т. е. 2ft(a*+4-M+1) > (5) Умножим обе части неравенства (4) на а-\-Ь. Так как, по условию, а-)-/>> 0, то получаем следующее справед- ливое неравенство: 2*-1(а*+ ^)(ff + />)>(fl + 6)‘+1. (6) Для того чтобы доказать справедливость неравенства (5), достаточно показать, что 2*(а^'Ч-/>*+!)> 2ft"'(^ + ^)(« + *). (7) или, что все равно, ak*1 4- bk+l > akb + abk. (8) Неравенство (8) равносильно неравенству {ак — Ьк)(а — Ь)>0. (9) Если а > Ь, то ак > Ьк, и в левой части неравенства (9) имеем произведение двух положительных чисел. Если а < Ь, то ak < Ь\ и в левой части неравенства (9) имеем произве- дение двух отрицательных чисел. В обоих случаях неравен- ство (9) справедливо. Этим доказано, что из справедливости неравенства (1) при n = k следует его справедливость при n = k-\-\. Пример 23. Доказать, что при любом х > 0 и при любом натуральном п справедливо неравенство хп + хП-2 + хП-4+...+_^_Н-------(1) X X X Решение. 1°. а) При п=\ неравенство (1) прини- мает вид x+j->2. (2) Неравенство (2) вытекает из очевидного неравенства (х— 1)2>0. б) При д = 2 неравенство (1) принимает вид ^+1+4>з- <з> 34
Неравенство (2) справедливо при любом х > 0; значит, оно справедливо и при замене х на х2, т. е. Прибавив к каждой части последнего неравенства по 1, получим неравенство (3). 2°. Предположим, что неравенство (1) справедливо при n = kt где k — некоторое натуральное число, т. е. + ... Ч—1^4-+ 1. (4) X хк Докажем, что тогда неравенство (1) справедливо и при п = k 2, т. е. + -+^+^ + -^>4 + 3. (5> Заменив в неравенстве (2) х на xk+\ получаем + (6) Сложив почленно неравенства (4) и (6), получим неравен- ство (5). Подведем теперь итог. В пп. Г а) и б) мы доказали, что неравенство (1) спра- ведливо при п=\ и при /г = 2. В п. 2° мы доказали, что из справедливости неравен- ства (1) при n — k вытекает его справедливость и при я = &4-2. Иными словами, п. 2° дает нам право перехода от п = k к п = k 4~ 2. Результаты пп. 1° а) и 2Э дают нам право утверждать, что неравенство (1) справедливо при любом нечетном п. Точно так же результаты пп. Г б) и 2° дают нам право утверждать, что неравенство (1) справедливо при любом четном п. В целом мы имеем право утверждать, что нера- венство (1) справедливо при любом натуральном /г. Пример 24. Доказать теорему: Среднее геометрическое нескольких положительных чисел не больше их среднего арифметического, т. е. если a{t а2> ...» ап положительны, то 14^2 ••• Дд<а'+а2+ ••-+-Дп. (1) 35
Решение. 1°. При п = 2 неравенство (1) принимает вил Д1 ^2 2 V4 # 1^2 (2) Это неравенство легко получить из справедливого при любых положительных ах и а2 неравенства (yfll-v4)2>0. Неравенство (2) имеет простой геометрический смысл. На прямой АВ отложим последовательно отрезки ах и л2. На сумме их как на диаметре опишем окружность. Тогда ——-—радиус этой окружности, а |/ аха2 — половина хорды, перпендикулярной к диаметру в обшей точке ах и а2 (см. рисунок), из чего и усматривается справедливость не- равенства (2). 2°. Предположим, что неравенство (1) справедливо при п —k. Докажем, что тогда оно справедливо и при n — 2k. Действительно, Д2 4~ • • ak | ak+l + • - » k “r k 2 ~ ^1+^2 + • •• 4- ... + a<2k ~ 2k 36
Неравенство (1) проверено при п = 2 и, таким образом, можем утверждать, что оно справедливо при п = 4, 8, 16 и т. д., т. е. вообще при п = 25, где s — натуральное число. 3°. Для того чтобы доказать справедливость неравен- ства (1) при всяком натуральном п, покажем, что из спра- ведливости неравенства при n = k следует его справедли- вость при n — k — 1. Итак, пусть av .........ak-\ — некоторые положитель- ные числа. Пусть X—некоторое, пока не определенное, положительное число. Тогда k Yaxa2 ... ак_хк < а'+аг+ -,^+^-,+А . Выберем л так, чтобы Д] + а2 + ••• 4-^-1+Х ___ al-j-a24- ... 4-^ft-i k — *k — 1 т. e. положим a a\ + й2 + ••• Л~аЪ-\ k—\ Имеем ^/~ аха2 ... _ j (а} 4- а2 4- ... ^а\ 4- л2 + • • • 4* V k — i k — i или Пусть теперь nt — произвольное натуральное число. Если т — 2s, то согласно 2° для него неравенство справедливо. Если же m=£2s, то найдем такое $, чтобы т было меньше 2\ и тогда на основании 2° и 3° утверждаем, что неравенство верно для п = т. § 4. ДОКАЗАТЕЛЬСТВО НЕКОТОРЫХ ТЕОРЕМ ЭЛЕМЕНТАРНОЙ АЛГЕБРЫ МЕТОДОМ МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ Теорема 1. Квадрат многочлена равен сумме квад* ратов всех его членов, сложенной со всевозможными их удвоенными попарными произведениями, пг. е. (°1 4 4" • • • 4- ап}2 “ а\~Ь а14- • • • + “h 2 (^1^2 + ••• ~^ап-\ап)' (1) 37
Г. Для п = 2 формула (I) может быть доказана непо- средственным умножением. 2°. Допустим, что формула (1) верна для n = k— 1, т. е. (Л1 + а24- ... + oft_1)2 = a?+fl2 + ... + e|_14-2S, где S — сумма всевозможных попарных произведений, соста- вленных из а2........яЛ_р Докажем, что («J—|— Л2Н— ... + ak-\ + акУ ~ = а* + а* + ... +4_i + a2+2Sp где Sj — сумма всевозможных попарных произведений, соста- вленных из Др а2.....аь-у ak* т- е- Sj =S 4-(£] Действительно, (£j 4- ... + = [(^i + ••• + ал-1)+ я*12 = = (01+ ••• + o^-j)2 + 2(flj 4- ... 4-ofc_i)o*+ «'i = —+’+ ••• + o|_14-2S4-2(aI4- ... 4-= = Oi + a|+ ••• +al + 25r Теорема 2. n-й член арифметической прогрессии может быть вычислен по формуле an = ax-{-d(n — \), (1) где а{ — первый член, d — разность прогрессии. 1°. Для /г=1 формула (1) верна. 2°, Предположим, что формула (1) верна для n = kt т. е. ak = d(k — 1). Тогда а % +1 = a k 4- d а। —d (k — 1) 4“ d=== aj -j— dk, т. e. формула (1) оказывается справедливой и для n~k-\-\. Теорема 3. я-й член геометрической прогрессии может быть вычислен по формуле an = a1qn~l. ' (1) где ах —первый член, q — знаменатель прогрессии. Г. Для /г = 1 формула (1) верна. 2°. Пусть ак = а^-\ Тогда 0й+1 = <М=01Л 33
Теорема 4. Число перестановок из т элементов может быть вычислено по формуле Рт = т\. (1) Г. Прежде всего заметим, что Рх — 1 и, таким образом, при т—\ формула (1) верна. 2°. Пусть Pk = k\. Докажем, что ^1=(£+1Д Из данных &4-1 элементов а2, ..., ak, ak¥X возьмем только первые k и составим из них всевозможные переста- новки. По условию, таких перестановок будет k\. В каждой из этих перестановок поставим элемент ak+A последовательно перед 1-м элементом, перед 2-м, .... перед &-м, после &-го. Этим путем мы из одной перестановки из k элементов получим k + 1 перестановок из k 1 элементов. Всего имеем k\(k+ 1) = (£+ 1)! перестановок из &+1 элементов. Необходимо выяснить: 1) нет ли среди этих (&-|-1)! перестановок двух оди- наковых; 2) все ли перестановки из k 4~ 1 элементов нами получены. 1) Допустим, что среди (k -)- 1)! перестановок имеются две одинаковые. Назовем их р1 и р2. Пусть в перестановке р{ элемент ak+1 занимает s-е место, считая слева. Тогда и в р2 элемент ak^i занимает s-е место, считая слева. Удалим из рх и р2 элемент ak+v Получим две одина- ковые перестановки из k элементов: р{ и р2. Выходит, что для получения р{ и р2 в одну и ту же перестановку из элементов av а2, ..., ak два раза на одно и то же место был поставлен элемент ak+v Это противоречит правилу, по которому построены пере- становки. 2) Допустим, что некоторая перестановка р из k -4-1 элементов нами не получена. Пусть в р элемент зани- мает s-е место слева. Удалим из р элемент лЛ+1. Получим перестановку р из первых k элементов. Значит, для полу- чения р достаточно было взять перестановку р и поставить в нее элемент ak+i так, чтобы он занял s-е место слева. Мы не могли не взять перестановку р, так как брали всевозможные перестановки из первых k элементов. 39
Мы не могли не поставить элемент ak+y на указанное место, так как ставили его и первым, и вторым, и (Л -1- 1)-м слева. Итак, составленные нами пе рестановки все различны и всякая перестановка из k 1 элементов нами получена. Из сказанного вытекает, что Теорема 5. Число размещений из т элементов по п может быть вычислено по формуле Апп1~ т(т — 1) ... {т — п + 1). (1) 1°. Прежде всего заметим, что Ат = т и, таким образом, формула (1) верна при /г = 1. 2°. Предположим, что Акт = т(т — 1) ... (т — k -f- 1), где k < т. Докажем, что Л*/1 = т (т — 1) ... (т — k). Для получения всех размещений из т элементов по k + I элементу достаточно взять все размещения из т элементов по k и к каждому из них приписать в конце каждый из оставшихся т — k элементов. Нетрудно убедиться, что составленные таким образом размещения из т элементов по k 1 все различны и, кроме того, всякое размещение из т элементов по k-\-\ содержится среди полученных. Выходит, что Акт 1 = Akm (т — k) = т (т — 1) ... (т — k). Теорема 6. Число сочетаний из т элементов по п может быть вычислено по формуле ГП _ т{т—\} ... (л?г — ZZ 4- 1) Ьт~ 1-2... п * 1°. Прежде всего заметим, что Схт — т и, таким обра- зом, при я=1 формула (1) верна. 2°. Допустим, что Ск __ т(т — \) ... (т — k 40
Докажем, что ^k+\__ /«(w —1) ... (w — k 4- 1) (m — k) btn — I - 2 ...£(£ 4 I) Для получения всех сочетаний из т элементов по k 4- 1 выпишем все сочетания из т элементов по k и к каждому из них в качестве (& 4 0-го элемента присоединим каждый из т — k оставшихся элементов. Ясно, что таким путем будут получены все сочетания из т элементов по k 4 1, но каждое из них получится k 4 1 раз. Действительно, сочетание ах, .... ak, получится, когда к сочетанию я2, а3, .... ak, akiX присоединится эле- мент ах, когда к сочетанию я3, aka присоеди- нится элемент а2 и т. д., когда, наконец, к сочетанию а{, ak присоединится элемент ak±x. Таким образом, + \___________nk ?n — k т (т — . (т — k) Ьпг —£4 1 — 1-2 ... £ (£4 1) ‘ Теорема 7. Каковы бы ни были числа а и b а каково бы ни было нашу ральное число п, имеет место формула (а h)n = ап -\-C\an~'b 4- ... 4 С\ап~ sbs 4- ... ... +Сг‘ГхаЬг‘-} + Ьп (1) (формула бинома Ньютона). Г. При /г = 1 имеем а 4 b = b 4и, таким образом, для этого случая формула (1) верна. 2°. Пусть (Д 4 z>)ft = a* 4-С*а*_1*4-С1«й-2*24- ... + t>k. Тогда (а 4 Ь) (# 4 (л 4 <0= = (д* 4--4 ... 4-^)(д + &) = - 4- (1 4 Cl) а ”Ь 4- (<Д 4- a^'b2^ ... ... 4(С1 4CrV'V+14- ... 4 Имея в виду, что 4 С& + 1 = С|+1> получаем (я 4 0) = а 4w4]£ М Cfe4i« b 4 • • ♦ х>5 4 -SiV + 1 । гЛ-М ... 4CH1o b -t ... 4<> .
ПОСЛЕСЛОВИЕ Ю* А. Гастев Индукция (лат. inductio — наведение) — переход от частного к общему; дедукция (лат. deductio — вывод) — переход от общего к частному. Всем известна роль процессов обобщения результатов отдельных наблюдений и опытов (т. е. индукции) для эмпириче- ских, экспериментальных наук. Математика же издавна считалась классическим образцом осуществления чисто дедуктивных методов, поскольку явно или неявно всегда подразумевалось, что все мате- матические предложения (кроме принятых за исходные — аксиом) доказываются, а конкретные применения этих предложений выводятся из доказательств, пригодных для общих случаев (дедукция). Но вот мы читаем: «Индукция широко применяется в матема- тике, но применять ее надо умело» (стр. 7 настоящей книги); «... как пользоваться в математике индукцией, чтобы получать только верные выводы?» *) (стр. 6). Что же все это, собственно, зна- чит? Не следует ли понимать дело так, что среди математических методов есть «достоверные», действующие, так сказать, безотказно (дедуктивные), и «не вполне надежные», дающие подчас, особенно в неумелых руках (как выражается автор, «при легкомысленном отношении»), осечку (индуктивные)? Если бы это было действи- тельно так, то где же искать критерии надежности таких «индуктив- ных» методов? Как вернуть себе уверенность в непреложной обя- зательности математических выводов? Или это безнадежная затея, и достоверность математических заключений — той же природы, что и опытные обобщения экспериментальных наук, так что любой доказанный факт неплохо было бы еще «проверить» (подобно тому как школьникам часто рекомендуется «проверять» правильность выполнения арифметических действий или решения уравнений по общей формуле)? *) Такого рода трактовка «индукции в математике» стала почти традиционной для школьных учебников — вплоть до самых новых (см., например, §§ 62—63 учебника алгебры Е. С. Кочеткова и Е. С. Кочетковой). 42
В действительности дело обстоит не так. Индукц и я т. е. «наведение* (на мысль, на догадку, на гипотезу) играет в математике, безусловно, очень большую, но чисто эври- стическую роль: она позволяет догадываться о том, каким, по всей видимости, должно быть решение. Устанавли- ваются же математические предложения только дедуктивно. Ни один математический результат не может пре- тендовать на достоверность, истинность, коль скоро он не выведен из исходных посылок. Ну, а как же «метод математической индукции»? Дело все в том, что «математическая индукция» есть дедуктивный метод. В самом деле, разберемся детальнее в структуре математических умозаключений, выглядящих как «переход от частного к об- щему». Легко убедиться, что так называемая математическая индук- ция на самом деле вовсе не есть индукция — это чисто дедук- тивный метод рассуждения! Доказательство, проводимое этим мето- дом, состоит из двух частей: 1) так называемый базис — доказа- тельство (дедуктивное!) искомого предложения для одного (или нескольких) натурального числа (например, для 0 или 1; это то, что на стр. 11 именуется «Теоремой 1»); 2) индукционный шаг («Теорема 2»), состоящей в доказательстве (опять-таки дедуктивном) общего утверждения: для всех п верно, что из того, что искомое утверждение справедливо для л, вытекает, что оно справедливо и для п + 1. «Принцип математической индукции» (стр. 10) — точно формулируемое предложение (интуитивная убедительность которого признается многими математиками как неоспоримая; при аксиома- тическом же построении арифметики он фигурирует в качестве аксиомы), позволяющее извлечь из базиса и индукционного шага чисто дедуктивное доказательство рассматриваемого предложения для всех натуральных чисел п. Таким образом, никаких «не учтен- ных в посылках» случаев, на которые затем («по индукции») надо было бы еще «распространять» заключение, не остается — теорема именно доказывается для всех натуральных чисел: из базиса, доказанного, скажем, для числа 0, мы получаем, по индукционному шагу, доказательство для числа 1, затем таким же образом для 2, затем для 3 ... —и так утверждение теоремы может быть обосно- вано для любого натурального числа *). Иначе говоря, название «математическая индукция» обусловлено тем, что этот метод просто ассоциируется в нашем сознании с традиционными «индуктивными» умозаключениями (ведь базис действительно доказывается только для частного случая); индук- ционный шаг, в отличие от основанных на опыте критериев правдо- подобности индуктивных умозаключений в естественных (и обще- ственных) науках, есть общее утверждение, не нуждающееся ни в какой частной посылке и доказываемое по строгим канонам дедуктивных рассуждений. Потому-то и называют матема- тическую «индукцию» «полной», или «совершенной», что она (в противоположность обычной, «несовершенной» индукции, не обеспечивающей нам полного знания) есть дедуктивный («сто- процентно надежный») метод доказательства. *) О встающих в связи с такого рода обоснованием метода проблемах см. указанную ниже литературу. 43
Итак, в качестве метода доказательства индук- ция в математике не применяется*), что. разумеется, никак не исключает широкого применения в ней дедуктивного ме- тода «математической индукции». Условившись отныне в такОхМ понимании термина, мы можем, конечно, позволить себе теперь и вольные перефразировки вроде «индукции в геометрии»**) или «индукции в математике». Но при этом всегда надо помнить, что первое выражение, строго говоря, имеет совсем не тот смысл, что громоздкое (но точное!) выра- жение «употребление дедуктивного метода математической индук- ции для доказательства теорем геометрического содержания» (хотя, для облегчения речи, и употребляется как его синоним), а второе — отнюдь не то же самое (вопреки чисто грамматическим признакам), что «математическая индукция»; последний термин следует воспри- нимать целиком, а вовсе не в смысле «индукция в математике». Метод математической индукции (в той форме, в какой он рас- сматривается в этой книжке) есть метод доказательства арифме- тических теорзм, точнее, теорем, выражающих общие свойства натуральных чисел (0, 1, 2, ...; иногда, как в этой книге, нату- ральный ряд уславливаются начинать с единицы, что абсолютно не принципиально). И для арифметики натуральных чисел этот метод, в известном (достаточно разумнОхМ и сильном) смысле, является универсальным (а часто и единственным) орудием доказа- тельств. Чтобы это последнее утверждение не показалось читателю слиш- ком сильным, он должен твердо уяснить себе,что при аксиоматическом (дедуктивном) построении арифметики все ее здание опирается на определения операций над натуральными числами по матема- тической индукции (например, при определении сложения прежде всего определяется, — в качестве базиса индукции, — что зна- чит прибавить единицу или нуль; затем — индукционный шаг опреде- ления—определение прибавления произвольного натурального чис- ла сводится к определению прибавления предшествующего числа). И вполне понятно потому, что «добираться» до общих свойств натураль- ных чисел, связанных, скажем, с операциями сложения или умноже- ния, нам приходится (если уж мы хотим обосновывать их аксиома- тически) по той же «лестнице» (на нижней «ступени» которой нахо- дится соответствующее свойство для наименьшего натурального числа), по которой мы «совершаем восхождение» к интересующему нас общему понятию; грубо говоря, иначе просто не видно, как за нужное нзхм доказательство «ухватиться»! И так обстоит дело с доказательством любого общего арифметического утверждения! И *) Мы уже упоминали вскользь о чрезвычайно плодотворной роли «обычной» («неполной») индукции в формировании математи- ческих догадок, ведущих затем и к открытиям новых фактов; подробнее об этом и о связи «обычной» индукции с методом мате- матической индукции см. в книге Д. П о й а, Математика и правдо- подобные рассуждения, М., ИЛ, 1957, т. I (особенно глава 7). **) Именно так, например, названа для краткости книжка Л. И. Г о л о в и н о й и И. М. Яг л ом а («Популярные лекции по математике», вып. 21), задуманная авторами в качестве естествен- ного продолжения книжки И. С. Соминского. 44
если это не видно из школьного курса арифметики и алгебры, то лишь потому, что он (совершенно резонно) опирается не столько на аксиоматический метод, сколько на опыт и интуицию *). В конце концов самый придирчивый и критически настроенный читатель часто довольствуется знанием того, что, скажем, дистрибутивность умножения относительно сложения можно доказать, и уже не тре- бует самого доказательства. (Но такая, пусть вполне обоснован- ная, уверенность так же отличается от подлинного доказательства, как, скажем, газетная информация от подлинного знания очевидца, причем эта аналогия простирается весьма далеко.) Поэтому-то ме- тод математической индукции и появляется в школьном курсе мате- матики гораздо позже интуитивно прозрачных и легко постигаемых свойств арифметических действий, например, в связи с формулой бинома Ньютона, которая уже отнюдь не такова, чтобы справедли- вость ее «бросалась в глаза». В той мере, в какой другие разделы математики опираются на арифметическую основу, они нуждаются в методе математической индукции. Потребность эта бывает двоякого рода. Прежде всего многие разделы математики просто строятся на базе арифметики натуральных чисел (скажем, теория рациональных чисел приводя- щая в спою очередь к теории действительных чисел), другие же могут быть интерпретированы в арифметических терминах (например, любой факт евклидовой геометрии можно выразить на «координатном языке» действительных чисел). В этих случаях утвер- ждения, предположим, геометрического содержания могут быть доказаны именно для такой арифметической интерпретации с помо- щью математической индукции. Можно сказать, что геометрическая или какая-либо иная «специфика» подобных предложений не более существенна для самого доказательства, чем, например, природа рассматриваемых объектов в задаче о сложении трех огурцов с пятью огурцами или трех пароходов с пятью пароходами. (При- меры такого рода читатель сможет сам найти в книге.) Но бывает так, что базис индукции доказывается существенно неарифметическими методами **). И в этом случае, однако, индук- ционный шаг (даже если он опирается на геометрические или какие- нибудь другие аксиомы) представляет собой некоторое общее утверждение о натуральных числах, поскольку в нем идет речь о выполнении некоторого свойства для любого натураль- ного числа п ***). Итак, математическая индукция по натуральным числам есть метод доказательства теорем, арифметических «по форме», но, быть *) В тех же случаях, когда в школьном курсе доказываются какие-либо общие свойства натуральных чисел, то доказательство, если и не проводится по индукции, то лишь благодаря тому, что в качестве посылок (часто неявных) используются предложения, для строгого обоснования которых индукция все же необходима (подобно тому как употребление постулата о параллельных в евкли- довой геометрии можно «замаскировать», пользуясь вместо него каким-нибудь из его следствий). **) См., например, уже упоминавшуюся книжку Л. И. Голо- вино й и И. М. Я г л о м а «Индукция в геометрии». ***) То есть сам переход «от п к п-\-1» доказывается для любого п. 45
может, геометрических или каких-нибудь других (скажем, механиче- ских) «по содержанию». Отметим еще, что метод, оказавшийся столь плодотворным для проведения доказательств, следующих процессу построения нату- рального ряда 0, 1, 2, может быть обобщен и на процессы совершенно другого вида Например, в исчислениях математической логики, оперирующих с формулами («высказываниями»), построен- ными из «элементарных формул» («элементарных высказываний») вида А, В, С .,с помощью, допустим, знаков & («и»), V («или»), зэ («если то .,.») и («не»), общие свойства формул доказы- ваются путем так называемой индукции по построению формулы: доказывается, что 1) искомым свойством обладает любая элементарная формула (базис), и 2) из того, что этим свой- ством обладают формулы X и К, следует, что им обладают фор- мулы (X & У), (X V У), (X зэ У) и ”] X (индукционный шаг): из этого делается вывод о справедливости доказываемого предложения для всех формул указанного вида. Аналогия с рассматриваемой в на- стоящей книге математической индукцией настолько прозрачна, что бросается в глаза и неподготовленному читателю. Вообще, любая математическая (или логическая) конструкция, состоящая в переходе от одного или нескольких исходных объектов к новым объектам с помощью одной или нескольких операций пере- хода, может служить основой соответствующего «индуктивного» (являющегося, как мы уже видели, чисто дедуктивным) метода определения и доказательства. (Относительно подчиненная роль метода математической индукции в математическом анализе, кстати, объясняется именно тем обстоятельством, что действительные числа, в отличие от натуральных, не являются продуктом такой развертывающейся четко очерченной конструкции, так что различ- ного рода «индукции по действительным числам» далеко не обла- дают той универсальностью, как метод математической индукции в арифметике и его модификации в математической логике.) Для разрешения тех вопросов о б ще логического и обще- математического характера, которые могли бы возникнуть те- перь у читателя, отсылаем его к специальной литературе *). За- дачу же первоначального ознакомления с конкретными приме- нениями метода математической индукции в элементарной матема- тике может с успехом выполнить эта книжка. *) См., например, Л. Г е н к и н, О математической индукции, М., Физматгиз, 1962; И. В. Арнольд, Теоретическая арифметика, М., Учпедгиз, 1939, § 13, 14, 17, 19; С. К. Клин и, Введение в математику, М., ИЛ, 1957, § 7, 13, 21, 38 и др.; «Математическая индукция» — Философская энциклопедия, М., 1964 (т. 3).
УКАЗАНИЯ И РЕШЕНИЯ*) 1. Гипотеза: ип = Зп — 2. Г. Для п = 1 гипотеза верна. 2°. Пусть uk — 3k — 2. Тогда uk + \ ~ Uk 3 = 3k — 2 4" 3 == 3 (k 1) — 2. 2. Гипотеза V2fl-1. Г. Для п— 1 гипотеза верна. 2°. Пусть $4 = 2* —1. Тогда Sft4i = ^ + 2* = 2* + 1-l. [Можно также сразу образовать разность 25Л — Sn и показать, что она равна 2'2— 1.] 3. 1°. При п = 1 утверждение справедливо. 2°. Пусть Р 4-32 4-52 -I- ... 4- (2k — I)2 = ?(2*~ о Тогда Р 4- З2 4- ... 4- (2А — I)2 4- (2А + I)2 = = £(2fe— 1)(2&4- 1) + {2k + 1)2 _ (£ 4- 1Н2Л-+-1)(2£4-3) 4. Г. При п ~ 1 утверждение справедливо. 2°. Пусть 134-234- ... 4-&3= Op *) Ниже указываются номера задач. Решения примеров приводятся в тексте. 47
Тогда 1’ + 2г + ... +*’ + (*4-1)’ = _ +(t +_ [(ЩКЩ]'. 5. Г. При п «в 1 утверждение справедливо. 2°. Пусть 1 + л + х2+ ... +x^Z__L. Тогда ..£4 1 , „£ч 2 i 1 + х + х24- ... + х* + х*п = х -у- + Х^л = -. 6. 1и. При п~ 1 утверждение справедливо. 2°. Пусть 1.23+2-3.4+ +Mt+0U + 2)-^+W±2Hl+^. Тогда 1-2-34-2.3-44- ... + *(* +1)(* + 2)+ (* + i)(*4-W4-3) = ~ * <* + l> (* + 2) (£+31 + (, + 1} (fe + 2) (, + 3) (* + 1) (*+ 2) (* + 3) (* + 4) 4 7. 1°. При п — 1 утверждение справедливо. 2“. Пусть 1 -3 3-5 ” "Г (2* — 1)(2*+ 1) 2* + I ' Тогда 1-3 3-5 ••• (2* — 1)(2*4-1) (2* + 1)(2* +3) k , 1 _ *+1 ~ 2* + 1 + (2* + 1)(2* + 3) 2/г+З’ 8. 1°. При п~ 1 утверждение справедливо. 2°. Пусть I2 , 22 , , *2 _ *(*+1) 1-3 + 3-5 + •••’’ (2£—1)(2* + 1) 2(2£-Н) ‘ Тогда Р , 22 , , *2 , (й+1)2 1-3 -г 3-5 ' (2й — 1)(2й+1) -Г (2*+1)(2й + 3) “ *(*+!) , (*+D2 _.b , n *(2* + 3) + 2(fe + l) -2(2А+1) 1 (2£+1)(2Л + 3)-1 'Г' 2(2й+1)(2й + 3) (*+ 1)(4k’ + Lk + 2) (k + 1)(2*+ l)(* + 2) _(Л+1)(Л+2) 2(2* + 1)(2* + 3) ~ 2 (2* + 1) (2* + 3) 2 (2* + 3) ’ 48
9. Г. При п == 1 утверждение справедливо. 2°. Пусть _1_+_L+ ... +_______________!_______= 1-4 '4-7^ [31г — 2)(3;-+ 1) З*н-Г Тогда _J__ ! L- i_ ।_______________L_________।__________!______ 1 .4 4-7 **• ‘ (ЗАг2) (ЗА? 4~ 1) (ЗА? 4~ 1) (ЗА? + 4) ~ _ k 1 /?4-1 3k 4- 1 ' (ЗА? 4* 1) (3k + 4) ~ 3k + 4 * 10. 1°. При п == 1 утверждение справедливо. 2°. Пусть L _1_ -J 1 j______________!______________ 1 • 5 ~ 5 • 9 ~ ‘ ‘ (4А? — 3) (4А? -(-I) 4А? + 1 ’ Тогда 1*5 ‘ 5*9 (4А?~3)(4А?+ 1) (4А?+ 1)(4А? + 5) ~ __ А? 1 А?4-1 4k + 1 (4А? + 1) (4k + 5) ~ 4k + 5 ’ It 1°. При п == 1 утверждение справедливо. 2°. Пусть 1—... J_______!-----— 4- ... 4_________!------;_ = __-____. а (а + 1) (л 4" 1) (л 4* 2) (л 4" — 0 4~ л (й 4~ Toi да _____1—4________*--... а (а 4- 1) (# 4~ О (й + 2) ... +______1________+________!_______= ((I 4- А? — 1) (а 4* k) (а 4~ k) (а 4~ k 4~ 1) _ k________________1_________ А? 4- 1 а (а 4~ А?) ((I 4" A?) (ci 4~ k 4~ I) и {(i ~4~ k 4“ 1) 12. 1°. При П" 1 и п 2 утверждение справедливо. 2°. Пусть аи-1_ pt-i а* —В* R 1 а —р R 1 а —р Тогда •= (а + Ь)-а₽ --ц_; = —tt_g 13. Г. При п —• 0 имеем _L_ = _J_ + _2_. 1 4 л х — 1'1 — л2 Следовательно, утверждение справедливо. 49
2® Пусть 1 । 2 1- 4 -1- I. 26 _ 1 - 2* + 1 14-* 1 14-х2 1 14-х4 ' 14-х2* х-1 1 Тогда 1 । 2 L 4 ... 1 9^ + 1 4- 14-х 1 14-х2 b 14-х4 I 4- х^к 1 14-х2*н 2iu L ~ 2*1-2 1 — xift *1 1 4- х2/? 1 х — 1 1 - — х-к h2 14. При п = 1 имеем При /г = 2 имеем 1 х । х(<х— О х— 1 1 х^х— 1) _ (-v — 1) (jt — 2) 1-~ТТ ‘ 2! “ 1 + 2 ““ 21 При п = 3 имеем 1 х | х(х—1)(х—-2) __ 1 2! 3! ~ (.г — 1) (л — 2) х(х—1)(х— 2) (х—1)(х— 2)(х— 3) ” 2 6 3! Это наводит на гипотезу: х х(х— 1) х(х—1) ... (х —«4-1) 1 И "Г 2! U п! ~ - 1 У* (*—!)(* —2) --- V ' nl 1°. При п = 1 гипотеза верна. 2°. Пусть X . x(.t— 1) 1! + 21 пл 1) (х—*4-1) _ ’ k\ ~ (_ 1)* (л~ ОС*—2) ••• (* —*) (.v_l)(.v_2) ,..(х-й4-1) -------------------------------(. £1 Тогда 1 х _l £(£~1) _ _____________________ 1 1! + 21 *г' 4 k\ ,, пЫ х(х— 1) ... (х — k} , 4(лг—1)(х—2) ...(.г —Л) , + (-1) -------(Г+Т)1------+ , ..h+1 х(х—1) ... (X — *) __ + ( (*-Н)! ,й+1 (х-1)(х-2) ... (х-А) [ *1 L*4-i j _,МП (-V — 1)U — 2) ... (v — X) (л- — * — 1) ^4-Т)! 50
15. 1°. При и = 0 утверждение справедливо. 2°. Предположим, что утверждение справедливо при п « k, т. е. что 11*+2+ 122 **+l делится на 133. Тогда = Ц^З+122(^1) + 1 _ 11НЗ + 122НЗ!= = 11 . 11*4 2+ 144- 122* + 1 = = 11 • llft42+ 133 - 122Zm1 + 11.122*41 = = 11 (11* + 2+ 122ZH 1)+ 133 - 122Л? +1 = 114 + 133-122*4 1. Мы представили Ak + \ в виде суммы двух слагаемых, каждое из которых делится на 133. Значит, + 1 делится на 133. 16. 1°. При п = 1 утверждение задачи, очевидно, справедливо. 2°. Предположив, что при п ~ k утверждение справедливо, т. е. k прямых делят плоскость на 2k углов, (# + 1)-я прямая рас- секает на части сразу два вертикальных угла, т. е. увеличивает число частей, на которые делится плоскость, на два. Поэтому (k + 1)-я прямая делит плоскость на 2k 4- 2 — 2 (k -f- 1) частей. 17. 1°. При п = 1 утверждение справедливо, так как . За- , х . / . Зх , sin-у- sin I sin --------sIn у I -------==--------------------------- = 4- cos x. o . x o . x 2 1 2 sin у 2sin-y 2°. Пусть , 2*4-1 1 sin----— x у 4~ cos x + cos 2л 4~ ... + cos kx -------------• Л 2 sin у Тогда у + cos x 4- cos 2x + ... 4" cos kx 4- cos (k 4- 1) x ~ ,2*4-1 2*4-1 . o , л Sin X Sin 4— A'4-2 Sin yCOS (*4~ l)x «------+ cos (* 4-1) Л =-----------/------------------------= 2siny- 2sin-y . 2*4-1 . /, 2*4-3 , 2*4-1 \ , 2*4-3 Sin 4— Jv4~(sin 4 —sin — л) Sin 4 x 2 sin у 2 sin у 18. 1°. При л= 1 утверждение справедливо, так как 2 sin л — sln2x 2 sin л (1—cos х) --------------—---------1L == sin х. 4 sin2 4 4 sin2 4 51
2°. Пусть . , п . о । । «. . t {k + 1) sin kx — k sin (k + В x sin x + 2 sin 2x + • • • + sin kx = -—!— --------------*—-—. 4 sin2 ~ Тогда sin x 4- 2 sin 2л 4" ... 4“ k sin kx + 4" 0 sin + 0 x ~ = (^+l)sin^-ASjn(A+l)x+(fe+1)sjn(fe + 1)x^ 4 sin2 4 __ (&4~ l)sin#x — #sin(# 4- l)x 4-2(Л4- l)sin(# 4“ 0r0 — cosx)_ A • 9 X """ 4 sin2 -y — + %)sin 0 •* 4- (^ + 1) sin kx __ 4 sin2 4 2 (6 4~ В cos x sin (& + 1) x _ 4 sin2 y __ 4~ 2) sin (Z? 4 i) 4 + i) sin ____ 4 sin2 y (Z? 4~ 1) [sin 4 2) л 4 sin Aly] __ 4 sin2 -y _(£ 4- 2) sin (A? 4- 1) л — (/г 4- 1) sin (k -U 2) x A • ? X 4sin^ у 19. Г. При n = 1 утверждение справедливо, так как 2 cos х — cos 2х—1 2cosx — 2cos2x cosx(l — cosx) .............. =--------------------------------------- = COS X. 4sin2-^- 4sin2-^- 2sin2-^ 2°. Пусть n 1 n о I I A A (&4-1)cosZly—£cos(£4“l)*—1 cos 2x + 2 cos 2x 4- ... 4- £ cos kx = -—’— -------*—'—-—=—. 4 sin2 y Тогда cos x 4- 2 cos 2x 4- • • • 4" cos kx 4- (k 4- 1) cos (k 4-1) x = = (fe+l)cos^-^cos(fe+l)-v-l + {k + i) cos {k + i) x = 4 sin2 4 52
(k 4. 1) COS £x — & COS (£ 4“ 1) X —• 1 4 sin2 * 4 ~ + . 2 (ft 4-1) cos (fe 4- 1) x (1 •— cos x) 4sin2-^- (k 4- 2) cos (# 4~ 1) x 4- (Л 4-1)CQS kx 4 sin2 у 2(#4~ 0cos x cos (£ 4- 0 x 4~ 1 _ 4 sin2-у (k 4- 2) cos (Z? 4~ 0 x 4~ 4~ 0 cos kx ___ 4 sin2 (Z? 4~ 0 [cos (A? 4* 2) x 4~ cos kx] 4~ 1 4 sin2 -~ == (Л 4-2) cos (fe + 1) x — (& 4-1) cos (* + 2) x— 1 4 sin2 -y 20. 1°. При Г2= 1 утверждение справедливо, так как 1 tg2 — tg2 — 1 lg 2 g 2 lx x — x 2 g 2 ‘ 2tg^ 2tg| 1 t X , 1 A X 2 c g У C X e 2 c g ”2 2°. Пусть 1 . x । 1 , x — tg —--------tg — 2 2 22 22 Тогда L . x . 1 . x . . 1 . x 2 g 2 22 S 22 2ft S 2* -1_ tg 2*+i ctg2 —-------1 1 , x 1 t„ x 1 2ft+1 = — ctg —г — ctgx 4-------------tg---------------------------------- 2ft 2ft 2ft+1 2ft+1 2ft+1 c.g x 2»+1 -------------Ctg-r - Ctg----- 2*+icIg_±_---2*+I 2Л + ‘ Ctgx. 53
21. 1д. Имеем 2 — 1 1 tg (arc tg 2 — arc tg 1) = = ~3 ’ Поэтому arc tg 2 — arc tg 1 = arc tg у — arc ctg 3. Значит, при n = 1 утверждение справедливо. 2°. Покажем сначала, что arc cig (2* + 3) = arc tg р — агс fg L О) Действительно, *+2 , I . А + 2 . Л+ 1 1 ^arctg^-arc tgl) = —-^-g- = + г Значит, arc tg 21ТУ = агс ctg (2^ + 3) агс tg TTY агс tg L Предположим, что утверждение справедливо при п = k, т. е arc ctg 3 4- arc ctg 5 4- ... + arc ctg (2k 4- 1) = = arctg2 + arctg-|4- ... + arc tg -±2 — k arc tg 1. (2) Докажем, что тогда оно справедливо и при п k 4- 1, т. е. arc ctg 3 4-arc ctg 5+ ... 4- arc ctg (2k 4- 3) = h _L 2 = arctg24- ... 4-arc tgy^ —(A?4-1) arctgl. (3) Сложив почленно равенства (1) и (2), получим равенство (3). 22. 1°. При я = 1 утверждение справедливо, так как у 3 — i = 2 (cos — i sin -г . \ о о / 2°. Пусть *\k Cik I k^l . kit \ (КЗ— I) =2 ( cos -ё----г sin — I. Тогда (У' 3 — == 2k (cos — i sin 2 (cos -5- — i sin -5-) \ b 6 / \ 6 6 ' -.2* fees + <!+'>»]. Lb 6 J 54
23. 1°. При n —- 1 утверждение справедливо. 2°. Пусть (cos х + i sin x)k — cos kx 4- i sin kx. Тогда (cos x 4- i sin a')/? + 1 == (cos kx 4~ i sin kx) (cos x + i sin x) = = (cos kx cos x — sin kx sin x) + i (cos kx sin x 4- sin kx cos x) == = cos (# + 1) x + i sin (k 4- 1) x. 24. Ошибочна самая последняя фраза: «Утверждение доказано». В действительности доказано, что неравенство 2” > 2п ф 1 справедливо при л=#-|-1, если оно справедливо при п — k, где k — любое натуральное число. Отсюда еще не следует, что неравенство это справедливо хотя бы при одном значении п и тем более при любом натуральном п. Короче говоря, ошибка заключается в том, что доказана только теорема 2, а теорема 1 не рассматривалась и база для индукции не создана. 25. Легко видеть, что 3 — наименьшее натуральное значение п, при котором неравенство 2п > 2п 4- 1 справедливо. Учитывая, что из справедливости неравенства при п = k следует его справедливость при п = k 4-1 (задача 23), утверждаем, что неравенство справедливо при любом натуральном п > 3. 26. 1°. При п = 2 неравенство справедливо, так как 1 + > К 2. / 2 2°. Пусть Докажем, что 4=г + -4= + • • • + Н-7=-=:- > /Г^П. (2) /1/2 / k / *+ 1 При любом k 0 имеет место неравенство FFTT>,/t + 1-^ <3> Действительно, неравенство (3) равносильно неравенству полученному из него умножением обеих частей на k 4- 1 4~ К Сложив почленно неравенства (1) и (3), получим неравенство (2). 55
21. 1°. При n = 2 неравенство принимает вид -,.-<6 и, следо- о вательно, справедливо. 2°. Пусть 4й (2k) I k+ 1 < (Л!)2 ’ где й > 2. Нетрудно проверить, что при k > О 4 (k + 1) (2й-|- 1, ;2й-{-2) k + 2 < (*4-1)2 Поэтому 4* 4(А + 1) (2й)! (2А-] 1) (2k -J- •>' А: 4-1 k + 2 < (й!)2 ' (/,'+ I)2 т. е. 4*+1 (2k+ 2)1 k + 2 < [(*+ DI]2 •
Цена 9 коп, ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ Вып. 1. А И. Маркушевич Возвратные последовательности. Вып. 2. И П. Натансон Простейшие задачи на максимум и минимум Вып 3. И. С. Соминский. Метод математической индукции Вып. 4. А. И Маркушевич. Замечательные кривые Вып 5 П П Коровкин. Неравенства Вып. 6 Н Н Воробьев Числа Фибоначчи. Вып. 7. А. Г. Курош. Алгебраические уравнения произвольных степеней Вып. 8 А. О Гельфонд. Решение уравнений в целых числах Вып. 9. А. И Маркушевич. Площади и логарифмы Вып. 10. А С. Смогоржевский. Метод координат Вып. 11. Я. С. Дубнов Ошибки в геометрических доказательствах Вып 12. И П Натансон Суммирование бесконечно малых величин Вып. 13. А И. Маркушевич Комплексные числа и конформные ото- бражения Вып. 14. А. И. Фетисов. О доказательствах в геометрии. Вып. 15. И Р. Шафаревич. О решении уравнений высших степеней Вып 16. В Г Шерватов. Гиперболические функции Вып. 17. В Г. Болтянский. Что такое дифференцирование? Вып. J8. Г М. Миракьян Прямой круговой цилиндр Вып. 19. Л А. Люстерннк. Кратчайшие линии Вып. 20. А. М Лопшиц. Вычисление площадей ориентированных фигур Вып. 21. Л И. Головина и И М Яглом. Индукция в геометрии Вып. 22. В Г. Болтянский. Равновеликие и равносоставленные фигуры Вып. 23. А. С Смогоржевский О геометрии Лобачевского. Вып. 24. Б. И Аргунов и Л. А Скорняков Конфигурационные теоремы Вып. 25. А. С. Смогоржевский. Линейка в геометрических построениях. Вып. 26. Б А Трахтенброт Алгоритмы и машинное решение задач Вып. 27. В А Успенский. Некоторые приложения механики к матема тике. Вып. 28. Н А. Архангельский и Б И Зайцев Автоматические цифро- вые машины. Вып. 29. А. Н Костове кий. Геометрические построения одним циркулем Вып. 30. Г- Е. Шилов. Как строить графики Вып. 31 А. Г Дорфман. Оптика конических сечений Вып. 32. Е. С. Вентцель. Элементы теории игр. Вып. 33. А. С Барсов Что такое линейное программирование Вып. 34. Б. Е. Маргулис. Системы линейных уравнений Вып. 35. Н. Я. Виленкин. Метод последовательных приближений Вып. 36. В Г Болтянский. Огибающая Вып. 37. Г. Е Шилов. Простая гамма (Устройство музыкальной шкалы) Вып. 38. Ю. А Шрейдер. Что такое расстояние Вып. 39. Н. Н Воробьев Признаки делимости. Вып 40 С В Фомин Системы счисления