Учебнометодическое пособие Рекомендовано методической комиссией радиофизического факультета для студентов ннгу, обучающихся по направлениям подготовки
 Скачать 212 Kb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Нижегородский государственный университет им. Н.И. Лобачевского Национальный исследовательский университет А.В. Леонтьева СБОРНИК ЗАДАЧ (МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ) Учебно-методическое пособие Рекомендовано методической комиссией радиофизического факультета для студентов ННГУ, обучающихся по направлениям подготовки 10.05.02 «Информационная безопасность телекоммуникационных систем», 11.05.02 «Специальные радиотехнические системы» Нижний Новгород 2014 УДК 510.2:510.6(072) ББК B176p30 Л-47 Л-47 Леонтьева А.В. СБОРНИК ЗАДАЧ (МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ): Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2014. – 19 с. Рецензент: к.ф.-м..н., ст. преп. Е.А. Рябова В учебно-методическом пособии рассматриваются задачи по одной из основных тем математики – методу математической индукции. В пособии разбираются такие темы, как доказательство равенств, доказательство неравенств, доказательство утверждений о делимости и доказательство общих формул числовых последовательностей, заданных рекуррентным способом. По каждой теме разобраны наиболее важные типы задач. В конце пособия по каждой из тем предлагаются задачи для самостоятельного решения. Электронное учебно-методическое пособие предназначено для студентов военных специальностей радиофизического факультета ННГУ, изучающих курс «Дискретная математика». Также пособие будет полезно студентам всех специальностей, изучающим курсы «Дискретная математика» и «Математический анализ». Ответственные за выпуск: председатель методической комиссии радиофизического факультета ННГУ, к.ф.-м.н., доцент Н.Д. Миловский, д.ф.-м.н., профессор Е.З. Грибова УДК 510.2:510.6(072) ББК B176p30 © Нижегородский государственный университет им. Н.И. Лобачевского, 2014 1. Теоретические сведения Принцип математической индукции Пусть имеется какое-то утверждение, зависящее от натурального n . Если это утверждение истинно при 1 = n и из истинности его при каком - то произвольном натуральном k n = следует его справедливость и при следующем n , равном 1 + k , то данное утверждение верно для всех натуральных n . Метод математической индукции Способ доказательства математических утверждений с помощью принципа математической индукции называется методом математической индукции , который состоит в следующем : 1. Проверяют истинность утверждения при 1 = n – первый шаг доказательства ( первый индукционный шаг ). 2. Допускают , что утверждение справедливо при k n = , где k – произвольное натуральное число ( N ∈ k ), и доказывают , что тогда утверждение верно и при 1 + = k n – второй шаг доказательства ( второй индукционный шаг ). Если обе части доказательства проведены , то на основании принципа математической индукции утверждение истинно для всех натуральных n ( N ∈ n ) – вывод В самом деле , если утверждение справедливо при 1 = n , то по доказанному в шаге 2 оно верно и при 2 1 1 = + = n Далее , из того , что оно верно при 2 = n вытекает его справедливость при 3 1 2 = + = n Затем от 3 = n переходят к 4 = n и т д Ясно , что при этом рано или поздно мы доберемся до любого натурального числа n , а потому данное утверждение истинно для всех N ∈ n Метод математической индукции можно применить и для доказательства утверждений , выполняющихся при всех целых n , начиная с некоторого целого , не равного 1. В этом случае речь идет об обобщенном принципе математической индукции Обобщенный принцип математической индукции Если утверждение ( ) n A , в котором n – целое число , истинно при m n = и из истинности его для k n = , где k – любое целое число , большее или равное m , следует его справедливость и для следующего 1 + = k n , то утверждение ( ) n A верно для любого целого значения m n ≥ Метод математической индукции применим для доказательства формул n - ых членов числовых последовательностей , заданных рекуррентным способом , т е выражением n - го члена через один или несколько предыдущих Иногда при рекуррентном задании числовой последовательности условиями определяются сразу два ее первых члена , а ее n - ый член выражается через два предыдущих. В таком случае для доказательства формулы n -го члена последовательности приходится использовать еще одну разновидность обобщенного принципа математической индукции. Обобщенный принцип математической индукции (разновидность) Утверждение ( ) n A , в котором n – целое число, истинно для всех целых m n ≥ ( Z ∈ m ), если выполнены 2 условия: 1) утверждение ( ) n A справедливо при m n = и при 1 + = m n ; 2) для всякого целого m k ≥ из истинности утверждений при k n = и 1 + = k n следует справедливость утверждения при 2 + = k n 2. Доказательство равенств Пример 1: Доказать, что для всех натуральных n верно равенство ( ) 4 1 3 2 1 2 2 3 3 3 3 + = + + + + n n n . (1) Доказательство : 1) проверим , выполняется ли равенство при 1 = n В этом случае левая часть этого равенства принимает вид 1 1 3 = , а его правая часть принимает вид ( ) 4 1 1 1 2 2 + и тоже равна 1. Значит , при 1 = n равенство верно 2) обозначим левую часть равенства через n S : 3 3 3 3 3 2 1 n S n + + + + = Допустим, что исходное равенство (1) является истинным при каком-то произвольном k n = ( N ∈ k ), т.е. что верно равенство ( ) 4 1 3 2 1 2 2 3 3 3 3 + = + + + + k k k или 4 ) 1 ( 2 2 + = k k S k Докажем, что тогда исходное равенство верно и при 1 + = k n , т.е. что справедливо равенство ( ) 4 ) 2 ( ) 1 ( 1 3 2 1 2 2 3 3 3 3 + + = + + + + + k k k или 4 ) 2 ( ) 1 ( 2 2 1 + + = + k k S k Рассмотрим левую часть последнего равенства и распишем k -ое слагаемое в этой сумме ( ) ( ) = + + + + + + = + + + + + 3 3 3 3 3 3 3 3 3 1 3 2 1 1 3 2 1 k k k слагаемых k первых сумма 4 4 4 3 4 4 4 2 1 по предположению сумма первых k слагаемых равна 4 ) 1 ( 2 2 + = k k S k , ( ) ( ) ( ) ( ) = + + + = + + + = + + + = 4 1 4 ) 1 ( 4 1 4 ) 1 ( 1 4 ) 1 ( 2 2 3 2 2 3 2 2 k k k k k k k k k ( ) 4 2 ) 1 ( 2 2 + + = k k Таким образом, доказали, что равенство (1) верно при 1 = n и из истинности его при каком-то произвольном натуральном k n = следует его справедливость и при следующем 1 + = k n . В силу принципа математической индукции это означает справедливость равенства для всех натуральных n . Пример 2: Доказать, что для всех натуральных n верно равенство 2 2 )! 2 ( )! 1 ( 2 ! 4 2 3 ! 3 2 2 ! 2 2 1 3 2 − + = + ⋅ + + ⋅ + ⋅ + ⋅ n n n n n *. (2) __________________________________________________________________ *По определению n n ⋅ ⋅ ⋅ ⋅ = 3 2 1 ! ( 1 ! 0 = ). В частности 1 ! 1 = , 120 5 4 3 2 1 ! 5 = ⋅ ⋅ ⋅ ⋅ = , ( ) ( )( ) ( ) ( ) 2 ! 1 2 1 ! ! 2 + + = + + = + n n n n n n Доказательство: 1) обозначим левую часть равенства через n S : )! 1 ( 2 ! 4 2 3 ! 3 2 2 ! 2 2 1 3 2 + ⋅ + + ⋅ + ⋅ + ⋅ = n n S n n Проверим справедливость исходного равенства (2) при 1 = n . Левая часть равенства принимает вид 1 ! 2 2 1 1 = ⋅ = S , правая – 1 2 3 2 2 ! 3 2 2 )! 2 1 ( 1 = − = − = − + Левая часть равенства (2) равна правой части равенства Значит исходное равенство верно при 1 = n 2) допустим , что исходное равенство верно при k n = ( N ∈ k ) 2 2 )! 2 ( )! 1 ( 2 ! 4 2 3 ! 3 2 2 ! 2 2 1 3 2 − + = + ⋅ + + ⋅ + ⋅ + ⋅ k k k k k , т е 2 2 )! 2 ( − + = k k k S , и докажем , что равенство (2) верно при 1 + = k n , т е докажем , что выполняется равенство 2 2 )! 3 ( )! 2 ( 2 1 ! 4 2 3 ! 3 2 2 ! 2 2 1 1 1 3 2 − + = + ⋅ + + + ⋅ + ⋅ + ⋅ + + k k k k k или 2 2 )! 3 ( 1 1 − + = + + k k k S Рассмотрим левую часть последнего равенства = + ⋅ + + + ⋅ + ⋅ + ⋅ = + + )! 2 ( 2 1 ! 4 2 3 ! 3 2 2 ! 2 2 1 1 3 2 1 k k S k k распишем k - ое слагаемое в этой сумме = + ⋅ + + + ⋅ + + ⋅ + ⋅ + ⋅ = + )! 2 ( 2 1 )! 1 ( 2 ! 4 2 3 ! 3 2 2 ! 2 2 1 1 3 2 k k k k k S k k 4 4 4 4 4 4 3 4 4 4 4 4 4 2 1 сумма первых k слагаемых , по предположению , равна 2 2 )! 2 ( − + = k k k S , = + ⋅ + + − + = + ⋅ + + = + + )! 2 ( 2 1 2 2 )! 2 ( )! 2 ( 2 1 1 1 k k k k k S k k k k ( ) ( ) ( ) 2 2 ! 3 2 2 3 )! 2 ( 2 1 2 2 )! 2 ( 1 1 1 − + = − + + = − + + + = + + + k k k k k k k k Поскольку выполнены оба условия принципа математической индукции , то равенство (2) справедливо для всех натуральных n . Пример 3: Доказать , что при любом натуральном n 1 ) ( − = ′ n n nx x . (3) Доказательство: 1) При 1 = n формула принимает вид: 1 = ′ x . Это соотношение верно Значит , при 1 = n формула (3) верна 2) Предположим , что она верна при k n = , то есть 1 ) ( − = ′ k k kx x , и , исходя из этого , докажем , что формула (3) должна быть верна и при 1 + = k n , то есть ( ) k k x k x 1 ) ( 1 + = ′ + Действительно , = ′ ⋅ + ⋅′ = ′ ⋅ = ′ + ) ( ) ( ) ( 1 k k k k x x x x x x x по предположению 1 ) ( − = ′ k k kx x , к тому же 1 = ′ x , ( ) 1 1 + = + = ⋅ + = − k x kx x kx x x k k k k k Оба условия принципа математической индукции выполняются , и поэтому формула (3) верна при любом натуральном n . 3. Доказательство утверждений о делимости Пример 4 : Доказать , что для всех натуральных n выражение 1 4 − n делится без остатка на 3 . (4) Доказательство: 1) Если 1 = n , то 3 3 1 4 M = − n – истина, так как 1 3 3 = . Значит, исходное утверждение (4) верно при 1 = n 2) Предположим, что выражение 1 4 − n кратно 3 при каком-то произвольном натуральном k n = , т.е. допустим, что ( ) 3 1 4 M − k Докажем, что тогда выражение 1 4 − n делится на 3 и при 1 + = k n , т.е. докажем, что ( ) 3 1 4 1 M − + k Действительно, ( ) 3 3 1 4 4 3 4 4 4 1 4 4 1 4 3 1 M 3 2 1 M + − ⋅ = + − ⋅ = − ⋅ = − + k k k k По допущению 1 4 − k кратно 3 , значит ( ) 3 1 4 4 M − ⋅ k , 3 тоже делится на 3 без остатка. Так как оба слагаемых суммы делятся на 3 , то и вся сумма делится на 3 . Следовательно, ( ) 3 1 4 1 M − + k Поскольку выполнены оба условия принципа математической индукции, то 1 4 − n кратно 3 при всех натуральных n . Пример 5: Доказать, что для всех натуральных n выражение n n 5 3 + кратно 6 . (5) Доказательство: 1) проверим справедливость утверждения (5) при 1 = n : 6 6 1 5 1 3 M = ⋅ + – верно; 2) предположим, что утверждение верно при k n = : ( ) 6 5 3 M k k + – пусть верно, и докажем, что (5) верно при 1 + = k n : ( ) ( ) ( ) 6 1 5 1 3 M + + + k k – доказать. ( ) ( ) ( ) = + + + + = + + + + + = + + + 6 3 3 5 5 5 1 3 3 1 5 1 2 3 2 3 3 k k k k k k k k k k ( ) ( ) 6 6 1 3 5 6 2 6 3 M 4 3 42 1 3 2 1 4 3 42 1 M M M + + + + = k k k k По допущению k k 5 3 + кратно 6 , второе слагаемое ( ) 1 3 + k k кратно 6 , поскольку числа k и 1 + k – последовательные числа, а значит одно из них четное, а второе нечетное, следовательно, произведение ( ) 1 + k k обязательно делится на 2 , а значит, число ( ) 1 3 + k k делится и на 2 и на 3 одновременно , значит ( ) 1 3 + k k делится на 6 , и , наконец , третье слагаемое 6 делится на 6 . Следовательно , вся сумма делится на 6 без остатка На основании принципа математической индукции утверждение справедливо при всех натуральных n . 4. Доказательство неравенств Пример 6 : Доказать неравенство Бернулли для всех натуральных n ( ) nx x n + ≥ + 1 1 ( 0 ≥ x ). (6) Доказательство: 1) при 1 = n неравенство имеет вид: x x + ≥ + 1 1 – тождественно верно для любых x ; 2) допустим, что неравенство (6) верно при k n = ( |