Методом математической индукции называют способ доказательства истинности некоторого утверждения для любого натурального числа n. Этот способ основан на принципе математической индукции, сформулированном в учебном тексте. Прежде чем приступить к обсуждению способа изложения материала на уроке, приведем шуточный пример, помогающий учащимся понять суть нового метода доказательства. Представьте, что вы подошли к кинотеатру и видите огромную очередь желающих купить билет на новый фильм. Вы становитесь в конец очереди, и к вам подходит человек со словами: «Я прошел от начала очереди и заметил, что в очереди после каждой женщины стоит женщина». Можно ли на основании услышанного утверждать, что в очереди стоят одни женщины? Обычно учащиеся легко справляются с этим вопросом, отвечая, что для истинности утверждения «В очереди стоят только женщины» надо быть уверенным, что первая в очереди женщина. Тогда после каждой женщины стоит женщина и утверждение «В очереди стоят только женщины» будет истинным. Но если первым в очереди стоит мужчина, то это утверждение будет ложным. Вторым примером, которым можно предварить объяснение нового материала, может быть разбор решения задачи 1.45. 1.45. На один из трех штырьков насажены п различных колец так, что большее кольцо лежит ниже меньшего (на рисунке 3 п = 3). За один ход разрешается перенести одно кольцо с одного штырька на другой, при этом не разрешается большее кольцо класть на меньшее. Докажите, что наименьшее число ходов, за которое можно перенести все кольца с одного штырька на другой, равно 2n − 1.
Условие этой задачи учителю лучше сформулировать самому. Тогда у учащихся будет возможность поучаствовать в поиске формулы, выражающей зависимость числа ходов от числа колец, и убедиться, что, даже найдя эту формулу, они пока что не могут доказать ее для любого натурального n, так как натуральных чисел бесконечно много. Рассуждения можно провести так. Одно кольцо (n = 1) можно перенести на новый штырек за 1 ход. Два кольца (n = 2) можно перенести за 3 хода (первое кольцо перенести на второй штырек, второе — на третий, затем первое — на третий). Три кольца (n = 3) можно перенести за 3 + 1 + 3 = 7 ходов, перенеся сначала два верхних кольца за 3 хода, потом нижнее кольцо за 1 ход, потом снова два кольца за 3 хода. Аналогично можно перенести 4, 5, 6 колец за 15, 31, 63 хода соответственно. Наблюдательные учащиеся могут заметить, что для п колец число ходов меньше n-й степени числа 2 на единицу, т. е. выражается формулой 2n − 1. Следовательно, получена гипотеза о выражении числа ходов через n, которую еще нужно доказать для любого натурального n. Но что значит доказать формулу для любого натурального n? Очевидно, что проверить истинность формулы для всех n невозможно. Необходимо соглашение, позволяющее считать, что при выполнении некоторых условий доказываемое утверждение истинно для любого натурального n. После обсуждения рассмотренных примеров учащиеся будут подготовлены к тому, что если истинность некоторого утверждения, зависящего от натурального n, установлена для n = 1 и доказано, что из истинности этого утверждения для некоторого п = k следует его истинность для следующего значения n, равного k + 1, то считается, что это утверждение истинно для любого натурального n (такое соглашение и называют принципом математической индукции). Пример 1 из учебника достаточно прост, чтобы, не отвлекаясь на технические сложности, освоить идею доказательства методом математической индукции. При обсуждении примера 2 можно упомянуть, что выдающийся математик XX столетия А. Н. Колмогоров (1903—1987) еще в детстве проявлял необыкновенные математические способности. В возрасте пяти лет он установил, что:
1 + 3 = 22, 1 + 3 + 5 = 32, 1 + 3 + 5 + 7 = 42
и т. д., т. е. выдвинул гипотезу, что сумма n первых нечетных натуральных чисел равна п2. Доказательство истинности этой гипотезы требует применения метода математической индукции. Обратим внимание на имеющееся в учебнике важное замечание о недопустимости пропуска любого из двух шагов в доказательстве методом математической индукции и об ошибках, к которым может привести такой пропуск. В учебнике имеется достаточное число примеров для обучения доказательству справедливости равенств и неравенств, а после задания 1.35 имеется указание, с помощью которого можно немного сократить запись доказательства некоторых утверждений. Рассмотрим пример применения этого способа оформления доказательства. Докажем равенство 1 1⋅4 + 1 4⋅7 + 1 7⋅10 +...+ 1 ( 3n−2 )⋅( 3n+1 ) = n 3n+1 . (1)
Обозначим A( n )= 1 1⋅4 + 1 4⋅7 + 1 7⋅10 +...+ 1 ( 3n−2 )⋅( 3n+1 ) , B( n )= n 3n+1 . Сначала убедимся в справедливости равенства
A( 1 )=B( 1 ) . Так как A( 1 )= 1 1⋅4 = 1 4 , B( 1 )= 1 3+1 = 1 4 , то равенство А (1) = В (1) доказано, т. е. при п = 1 равенство (1) справедливо. Теперь вычислим разность A(k + 1) − А(k), равную (k + 1)-му слагаемому суммы А(k + 1):
A( k+1 )−A( k )= 1 ( 3k+1 )( 3k+4 ) , и разность В (k + 1) − В (k), равную
B( k+1 )−B( k )= k+1 3k+4 − k 3k+1 = ( k+1 )( 3k+1 )−k( 3k+4 ) ( 3k+1 )( 3k+4 ) = = 1 ( 3k+1 )( 3k+4 ) . Тем самым мы доказали равенство A( k+1 )−A( k )=B( k+1 )−B( k ) . (2)
Предположим теперь, что при n = k равенство (1) справедливо, т. е. что A(k) = В(k), тогда из справедливости равенства (2) следует справедливость равенства A (k + 1) = В (k + 1), т. е. справедливость равенства (1) при n = k + 1. Итак, равенство (1) справедливо при п = 1, и из его справедливости для п = k следует его справедливость для п = k + 1, тогда, согласно принципу математической индукции, равенство (1) справедливо для любого натурального n.
Решения и комментарии
1.31. а) Докажите методом математической индукции, что 0n = 0 для любого натурального числа n. Хотя это утверждение и кажется очевидным, но тем не менее оно должно быть доказано методом математической индукции. Доказательство. При п = 1 справедливо равенство 01 = 0. Предположим, что для некоторого натурального числа п = k справедливо равенство 0k = 0, и докажем, что тогда справедливо равенство 0k + 1 = 0. Используя равенство 0k = 0, имеем: 0k +1 = 0k · 0 = 0 · 0 = 0. Следовательно, равенство 0n = 0 справедливо для любого натурального числа n. 1.38. б) Докажите по индукции, что для любого натурального п справедливо неравенство
1 1⋅4 + 1 4⋅7 + 1 7⋅10 +...+ 1 ( 3n−2 )( 3n+1 ) < 1 3 . Доказательство. Так как левая часть неравенства для любого натурального числа n равна дроби n 3n+1 (доказано по индукции выше), а n 3n+1 = 1 3+ 1 n < 1 3 для любого натурального числа n, то из справедливости равенства (1) для любого натурального числа n следует справедливость доказываемого неравенства для любого натурального числа n. Замечание. Обычно в 9 классе формулы n-го члена и суммы первых п членов арифметической и геометрической прогрессий не доказывают с помощью метода математической индукции, а лишь проводят рассуждение, подводящее к гипотезе. На это нужно обратить внимание учащихся. Для осознания нового уровня владения материалом они должны научиться доказывать эти формулы с помощью метода математической индукции (задание 1.32). 1.43. г) Докажите, что для любого натурального числа п 3n + 4n − 1 делится на 6. Доказательство. Доказываемое утверждение справедливо при n = 1, так как 31 + 41 − 1 = 6, т. е. делится на 6. Предположим, что при n = k сумма 3k + 4k − 1 делится на 6, и докажем, что при n = k + 1 сумма 3k + 1 + 4k + 1 − 1 делится на 6. (Успех доказательства зависит от умения учащихся в сумме 3k + 1 + 4k + 1 − 1 выделить сумму 3k + 4k − 1, которая по нашему предположению делится на 6.)
Слагаемое 3 · (3k + 4k − 1) последней суммы делится на 6, так как один из его множителей делится на 6 по нашему предположению. Осталось доказать, что и слагаемое 4k + 2 также делится на 6. Применим метод математической индукции еще раз. Очевидно, что при k = 1 сумма 41 + 2 = 6 делится на 6. Предположим, что при k = т сумма 4m + 2 делится на 6, и докажем, что при k = т + 1 сумма 4m + 1 + 2 делится на 6. 4m + 1 + 2 = 4 · 4m+ 2 = 4 · 4m + 8 − 6 = 4 · (4m + 2) − 6. Слагаемое 4 · (4m + 2) делится на 6, так как один из его множителей делится на 6 по нашему предположению, число 6 тоже делится на 6, поэтому и разность 4 · (4m + 2) − 6, а значит, и сумма 4m + 1 + 2 тоже делятся на 6. Тем самым доказано, что сумма 4k + 2 делится на 6 для любого натурального k. Но тогда и 3k + 1 + 4k + 1 − 1 делится на 6. Итак, выражение 3n + 4n − 1 делится на 6 при п = 1; из предположения, что это выражение делится на 6 при n = k, следует, что оно делится на 6 и при n = k + 1. Это означает, что выражение 3n + 4n − 1 делится на 6 при любом натуральном числе n. Промежуточный контроль. С—8.
