Лекции Русакова (1021002), страница 21

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

+ a k2(2)(b21+ a k +1 b1 + ... + bk222+ ... + bk2)+ a) + b (ak +1212k +12bk +1 +2)+ ... + a k .2Легко заметить, что для того, чтобы доказать это неравенство,достаточно доказать(2a k +1bk +1 (a1b1 + ... + a k bk ) ≤ a k +1 b1 + ... + bk222) + b (ak +1212)+ ... + a k .2Перенеся все слагаемые в одну сторону, и сгруппировав их, получаемочевидное неравенство:(a k +1b1 − a1bk +1 )2 + (a k +1b2 − a 2 bk +1 )2 + ... + (a k +1bk − a k bk +1 )2 ≥ 0.А это и доказывает неравенство Коши-Буняковского.Определение1. Число(a1 + a 2 + ...

+ a n )n называется средним арифметическимчисел a1 , a 2 ,..., a n .1962. Если a1 ≥ 0,..., a n ≥ 0 , то число (a1 ⋅ a 2 ⋅ ... ⋅ a n )1nназывается среднимгеометрическим чисел a1 , a 2 ,..., a n .Теорема 3 (неравенство Коши)Пусть a1 ≥ 0,..., an ≥ 0 , тогда(a1 + a2 + ... + an )n ≥ (a1 ⋅ a2 ⋅ ...⋅ an ) n .1(1)ДоказательствоШаг первый: сначала индукцией докажем это неравенство длянатуральных чисел вида n = 2 m . При m=1 надо доказать, чтоa1 + a 2≥ a1 a 2 .2Это неравенство эквивалентно a1 − 2 a1 a 2 + a 2 ≥ 0 , то есть(a1 − a 2)2≥ 0.Последнее неравенство верно, значит, и первоначальное верно, так как ониравносильны.

Допустим, неравенство верно при m=k, то естьa1 + a 2 + ... + a 2k2k(≥ a1 ⋅ a 2 ⋅ ... ⋅ a 2k)12k.(2)Докажем неравенство (1) для m=k+1, то есть докажем, чтоa1 + a 2 + ... + a 2k +12(≥ a1 ⋅ a 2 ⋅ ... ⋅ a 2k +1k +1)12 k +1 .В самом деле,a1 + a2 + ... + a2k +12 k +1 a1 + a2 + ... + a2k a2k +1 + a2k + 2 + ... + a2k +1 ×= +kk22()1 a1 ⋅ a 2 ⋅ ... ⋅ a 2k× ≥2(a)1= a1 ⋅ a 2 ⋅ ... ⋅ a 2k +1)11(2k(+ a 2k +1 ⋅ a 2k + 2 ⋅ ...

⋅ a 2k +1)12k2⋅ a 2 ⋅ ... ⋅ a 2k≥12k(⋅ a 2k +1 ⋅ a 2k + 2 ⋅ ... ⋅ a 2k +12 k +1 .197)12k=≥Итак, мы доказали неравенство Коши, когда количество чисел всредних есть степень двойки. А как быть с остальными? Для них мы докажемнеравенство Коши, используя еще одну модификацию индукции – "индукциювниз". Допустим, что неравенство Коши верно для n=k, то есть допустим, что(a1 + a 2 + ...

+ a k )k ≥ (a1 ⋅ a 2 ⋅ ... ⋅ a k ) k ,1(3)и докажем это неравенство для n=k-1. Для этого в неравенстве Кошиположим a k =a1 + a 2 + ... + a k −1(a1 + a 2 + ... + a k −1 ) +kk −1, тогда (3) будет иметь вид:a1 + ... + a k −11a1 + ... + a k −1  kk −1≥  a1 ⋅ a 2 ⋅ ... ⋅ a k −1 ⋅ .k −1После элементарных алгебраических преобразований получили:1a1 + a2 + ... + ak −1≥ (a1 ⋅ a2 ⋅ ... ⋅ ak −1 ) kk −11 a + a2 + ... + ak −1  k⋅ 1 .−k1Сократим неравенство на второй множитель правой части: a1 + a2 + ... + ak −1 k −1k −1k≥ (a1 ⋅ a2 ⋅ ... ⋅ ak −1 ) k .1И, наконец, возведем обе части неравенства в степень1a1 + a2 + ... + ak −1≥ (a1 ⋅ a2 ⋅ ...

⋅ ak −1 ) k −1 .k −1Неравенство Коши доказано полностью.6.04. Примеры задач и упражнений.Пример 1Доказать, что1 + 2 + ... + n =n(n + 1).2(1)Доказательство198k:k −1Метод математической индукции будем оформлять по следующейсхеме.1. Базис индукции: проверим равенство при n = 1 . Левая часть (ЛЧ)=1,правая часть (ПЧ)=1⋅ 2= 1 . Равенство при n = 1 , то есть базис индукции,2выполняется.2.

Индуктивное предположение: допустим, равенство (1) верно приn = k , то есть допустим, что1 + 2 + ... + k =k (k + 1).2(2)3. Индуктивный переход: докажем равенство (1) при n = k + 1 , то естьдокажем,что1 + 2 + ... + k + (k + 1) =1 + 2 + ... + k + (k + 1) =(k + 1)(k + 2) .2Всамомделе,k (k + 1)+ (k + 1) . Здесь мы применили индуктивное2предположение.

Далееk (k + 1)k (k + 1)(k + 2 ), что и+ (k + 1) = (k + 1) + 1 =222 требовалось доказать.На основании ММИ равенство (1) верно при любом n .Пример 2Доказать, что для любого n ∈ N1 ⋅1!+2 ⋅ 2!+... + n ⋅ n!= (n + 1)!−1 .(3)Доказательство1. Базис индукции: проверим утверждение (3) при n = 1 . ЛЧ=1 ⋅ 1! = 1,ПЧ= (1 + 1)!−1 = 2!−1 = 1. Базис индукции доказан.2. Индуктивное утверждение: допустим, (3) верно при n = l , то естьдопустим:1 ⋅1!+2 ⋅ 2!+... + l ⋅ l!= (l + 1)!−1.(4)1993.

Индуктивный переход: докажем (3) при n = l + 1, используя (4), тоесть докажем, что1 ⋅ 1!+2 ⋅ 2!+... + l ⋅ l!+(l + 1)(l + 1)!= (l + 2 )!−1.В самом деле,(1 ⋅1!+2 ⋅ 2!+... + l ⋅ l!) + (l + 1)(l + 1)!== (l + 1)!−1 + (l + 1)(l + 1)!== (l + 1)!(l + 2 ) − 1 = (l + 2 )!−1 .Пример 3Доказать, что для любого n ∈ N 4 n + 15n − 1 делится на 9. (5)Доказательство1.

Базис индукции: проверим (5) при n = 1 . ЛЧ=4+15-1=18 делитсяна 9.2. Индуктивное предположение: допустим, (5) выполняется приn = m , то есть 4 m + 15m − 1 делится на 9.(6)3. Индуктивный переход: докажем (5) при n = m + 1 , используя (6), тоесть докажем, что 4 m+1 + 15(m + 1) − 1 делится на 9.4 m+1 + 15(m + 1) − 1 = 4 ⋅ 4 m + 15m + 15 − 1 == ( 4m + 15m − 1) + ( 3 ⋅ 4m + 15) .Первая скобка делится на 9 по индуктивному предположению.Осталось доказать, что второй слагаемый делится на 9, то есть надо доказать,что 4 m + 5 делится на 3. Это утверждение мы будем доказывать методомматематической индукции, то есть нам придется применять "индукцию виндукции".

При m=1 4+5=9 делится на 3. Допустим, 4 k + 5 делится на 3.()Докажем, что 4 k +1 + 5 делится на 3, но 4 k +1 + 5 = 4 ⋅ 4 k + 5 = 4 k + 5 + 3 ⋅ 4 k .Первый слагаемый делится на три по индуктивному предположению, а200второе – очевидно. Таким образом, мы доказали, что 4 m + 5 делится на 3, авместе с этим, что 4 n + 15n − 1 делится на 9.Пример 42 n > n для любого n ∈ N .ДоказательствоПри n=1 неравенство очевидно: 2>1. Допустим, 2 k > k . Докажем, что2 k +1 > k + 1 . В самом деле, 2 k +1 = 2 ⋅ 2 k = 2 k + 2 k > k + 1 , так как 2 k > k поиндуктивному предположению и 2 k > 1 – очевидное неравенство.Пример 52 n > n 2 для любого натурального n ≥ 5 .ДоказательствоПри n=5 получаем верное неравенство 32>25.

Допустим, неравенствоверно при n = k ≥ 5 , то есть 2 k > k 2 . Докажем, что 2 k +1 > (k + 1)2 . Этонеравенство равносильно 2 k + 2 k > k 2 + 2k + 1. Если мы докажем, что2 k > 2k + 1 (k ≥ 5) , то будет доказано и исходное неравенство. Неравенство2 k > 2k + 1(k ≥ 5)доказываем индукцией (индукция в индукции). Приk = 5 имеем верное неравенство 32 > 11 . Допустим, неравенство верно приk = m , то есть 2 m > 2m + 1. Докажем при k = m + 1 , то есть докажем, что2 m+1 > 2(m + 1) + 1 = 2m + 3 или2 m + 2 m > 2m + 1 + 2 . Очевидно, что этонеравенство верно в силу индуктивного предположения.6.05.

Задачи для самостоятельного решения.2016.1 Доказать методом математической индукции, что для любого.6.2Доказать методом математической индукции, что для любого;6.3Доказатьметодомматематическойиндукции,любогочтодля.6.4 Доказать методом математической индукции, что для любого.6.5 Доказать методом математической индукции, что для любого;6.6 Доказать методом математической индукции, что для любого.6.7 Доказать методом математической индукции, что для любого;6.8 Доказать методом математической индукции, что для любого.6.9 Доказать методом математической индукции, что для любогосправедливо равенство6.10Доказать методом математической индукции, что длялюбого6.11Доказать методом математической индукции, что длялюбого.2026.12Доказать методом математической индукции, что длялюбого6.13.Доказать методом математической индукции, что длялюбого6.14.Доказать методом математической индукции, что длялюбого6.15.Доказать методом математической индукции, что длялюбого6.16.Доказать методом математической индукции, что длялюбого6.17.Доказать методом математической индукции, что длялюбого6.18.Доказать методом математической индукции, что длялюбого6.19.Доказать методом математической индукции, что длялюбого6.20;Доказать методом математической индукции, что длялюбого.203Глава 7.

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

Еще математикамДревнего Востока была известна формула, выражающая число сочетанийчерез биноминальные коэффициенты и Бином Ньютона для натуральных n .С мистическими целями изучались свойства магических квадратов 3-егопорядка.Комбинаторика как раздел математики появилась в трудах БлезаПаскаля и Ферма по теории азартных игр. Эти труды, составив основу теориивероятностей, одновременно содержали принципы нахождения числакомбинаций элементов данного конечного множества.204СпоявлениемработыЛейбницаиБернулли«Искусствопредположений» посвященной теории вероятностей комбинаторные схемывыделились в отдельную часть математики.Возрождение интересов к комбинаторике относится к 50 годам ХХвека.

Этот интерес связан с развитием кибернетики. Большой развивающийсяраздел комбинаторики это теория блок-схем. Основные проблемы этогораздела связаны с вопросами классификации, условиями существования иметодами построения некоторых классов блок-схем.Рассмотрим k множеств M 1 , M 2 ,..., M k , содержащий по m1 , m2 ,..., mkэлементов соответственно.

Будем выбирать по одному элементу из каждогомножества и составлять новое множество. Число способов, которыми этоможно сделать равно m1 ⋅ m2 ⋅ ... ⋅ mk . Будем рассматривать такие множества, вкоторых каждый элемент входит не более одного раза. Такие соединенияназываются без повторений.Будем считать, что рассматриваем множество A , состоящее из nразличных элементов.Определение:Размещением без повторений из n элементов по k элементов k ≤ nназываются k -элементные подмножества множества A , отличающиеся одинот другого или самими элементами или их порядком. Обозначаем Ank .Теорема.Число размещений без повторений равноAnk = n( n − 1)( n − 2)...( n − ( k − 1))Доказательство.205Для того чтобы расположить k элементов в определенном порядкевыберем один и будем считать его «первым».

Это можно сделать nспособами. Оставшееся множество содержит n − 1 элемент. Из него выберемещё один и будем считать его «вторым». Для выбора второго элементасуществует n − 1 способ. Осталось n − 2 элемента. Продолжая рассуждатьподобным образом понятно, что k -ый элемент можно n − ( k − 1) способами.Пользуясь утверждением, приведенном в начале параграфа получимAnk = n( n − 1)( n − 2)...( n − ( k − 1))Определение.Перестановками из n элементов называются множества из nэлементов, отличающиеся один от другого порядком элементов. ОбозначаемPn .Теорема.Число Перестановок без повторений равно Pn = n!Доказательство.Повторяет доказательство предыдущей теоремы, полагая k = n .Определение.Сочетаниямибезповторений,содержащимиkэлементов,выбранных из n элементов заданного множества, называются всевозможныемножества из k элементов, отличающиеся хоть одним элементов (порядок неучитывается), при этом все элементы различны.

Характеристики

Список файлов лекций