Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 80
Текст из файла (страница 80)
яи1 2 сов — (сов — + гейл — ) й) яи 7Г = 2 сов — < 2 сое —. й й Отсюда ь — ! ~ ехр ( — ) (1 -Е ехр ( ~™ )) ~ < (й — 1) (2 сов — ) = О ( — ) . =! 3) Воспользоваться результатом задачи 1,207 1) и заметить, что ~1+ не~ '1ь~ < 1 — о+ 2п сов — < 1+ и при О < и < й.
4) С использованием задач 1.18, 9) и 5.3, 2) получаем лш (е) Е(л )( ) ( ) Я( ) 2 )(Я Е 7! — 1 и ва аг < 1 для й < . Для й > — неравенство вытекает из соображений 2 2 симметрии. 3) Первое неравенство докажем индукцией по и. При и = 1 неравенство верно. Предполагая его справедливость при некотором и > 1,имеем ( )=2 ( ) 2 2(п-!-Ц1 22п-!-1 72пз 2п+1 4" ) >2 — > и-!-1 и+1 и и-';-1 2!77! > (2п -!- 1) „1 4" > огпп+Т 2~/ 41 Второе неравенство можно цоквзать по индукции с использованием задачи 5.1, 7).
5.3. Ц (2п — 1)9 = (2п)г(77!) '. 2 Зг'2~г(2п)(27!) "е в" (2яп) ~1~а е" 2 "' Г72п" е —" 2". 2) ( ) = (2п)!(и!) и74ягг(2п)~" е з (27гп) х х и з"24" вш(яп) 717 4' 5) (2п)!!((2п — 1)9) ' = (27!)!((2п — Ц!!) з. Далее можно использовать формулу Стирлинга и результат задачи 1). ! 1 2" т! 1 5.4. 1) /(14-1)" Я = (14-1)"+'( = — . С другой стоп-!-1 о -!-1 и-!-1 о о ро, /'(14-1)-41=/'~ (й)1'=~ (й)~1й41=~'„' (й). о о г=о г=о г=о 2) Воспользовавшись результатом задачи 1.19, 3), имеем 390 Отпвгтпы, укагвнпв, решенпв 5.5.
1) Да. Справедливость неравенств следует из того, что (Ь)а" < ( („)Ьв < (,)с . 2) Нет. Контрпримером может служить последовательность 1Ьь) такая, что Ьь = 2 ° 3 Я при Ь четном, Ьг = 3 1 при Ь нечетном. Полагая о = 1/3 и с = 2/3, имеем 0 < а" < Ьг, < сг < 1. Однако в силу задачи 1.22, Ц получаем ( ць©ь, ~,— ( ц ©(-')'+,',--(,",) ( ) = (1 — — ) 4- — Я1+ — ) + (1 — — ) ) > 11 — а)". 5.6. 1) Имеем Ра = — ~ ~1а, — а) > — 2 1а, — о) > 614 .
Отсюда бг < Р /4~ в,=.1 "., )., тд>1 2) Рассмотрим множество А = 1ов7 аг, ..., аг 1), в котором а ЧИСЛО ЕДИНИЦ В ДВОИЧНОМ ВЕКТОРЕ Й = 1О1, ..., 11п), ИМЕЮЩЕМ НОМЕР Ы. 71 Заметим, что а = 2 " ~ ~а = 2 " ~ Ь( ) = —. Заметим, далее, что 2 в«г" в<1<1 число, стоящее в левой части доказываемого неравенства, равно числу тех а, для которых ~а — а~ > 4 чтть В силу задачи 1) это число не превосходит Ра/14 1/п)г.
Но 2"Ра= ~ 1а — а.)г= ~ та~ — а)= — 2"а + ~ Ь~( )= в«г" в«г * в<я< = -2" (-) + (и + п)2" г = п2" Таким образом, 2" Ра/11 з/й)г = 2" ~/4~. 3) Оценка снизу. Положим 4 = 1пн, С учетом задачи 2) имеем ~Х-< Ьг (Ь) ~-~ (Ь) (п/241гти)г г-в (Ь) 4 / „2в') 2в"" > )71 — 41 1/п)г ' 11 I 711 Оценка сверху. Заметим сначала., что ( ) < ( — ) в силу задачи 5.2, 1) и („1)/(Ь) = < — при Ь < —. Поэтому К" г(")-' ~: (")' —.' К ©' 4- ( — — 4 з/и) ~ ( ) ( 14е)"~ ~~ 3 ' 4- 1 Ш вЂ” !г~<1„' =о + — (1+(471 11)) 2'<и ~.2"~.
391 Га. 'гИ1, Элементы кожбинагпорики 5.7. 1) Используя формулу (2), имеем ()= ,,/п ио (1 -< О(1,~и)) гга>лг еь — )-— Положим х = игг2 — к; тогда полученное выражение можно переписать в Имеем, далее, 4) Положим х| = х -!- 2 ьг!пи, )г(х) = и.а+ х >гйа Тогда а -~- 1 К (".)"= К (".)а+ К ("')а >И*О Ы 1« Ы*г1 >Л1 1 Но ~ ~(и)а' < и( )а", где ио =]й(хг)[, В силу задачи 2) получаем >М*,1 отсюда, что ,г ( )а <ы и(2яиа) ~~з(1-~ а)"~~ ехр( — — 1) = >Ям,1 = и ~ (2я) ~ (1 + а)" 'г ехр ( — — — х чг!и и — 2 1п и) < 2 ~< и '~ (2я) 'г (1+а)'Рые * гз — туг!пх.
(*) С другой стороны, из задачи 3) следует, что (и) (а -!-1)" (е гг е *г1~) зц1« Ы О Из (*) и (**) вытекает искомая опенка. 5.8. 1) Используя неравенство (2) и вытекающее из него неравенство и! > з/2яии" е ", получаем 1 (") ч'2хи и" ехр ( — и -1- — ) ег Вз"! < — С(ии Л). лиl 2яизглл(ли)л" (ли)ни ехр( — лп — лиг >гзхилллл"ле" 392 Отпветьь указания, решения С другой стороны, (п) пЛ ъг2яп п" ехр ( — п) 2яп хЛр р(Лп)""(рп)1 ехр ~ — Лп — рп а— 12рп. 12Лп ехр ( — (11(12и))(1!Л а 1)р)) О2ят~ЛрЛЛ рв () 1 1 ) < С(п, Л) ехр Лп! ) 12п 12Лп 12ри 360(Лп)з 360(рп)з ~ 1 1 Без ограничения общности можно считать, что Л > р.
Тогда — < —, 12п 12Лп 1 1 1 1 1 а — — < — — < О. Следовательно, 360(Ли)з 360(Рп)з 12рп 180рзпз 12рп (ь) "(и ') 3) используя нижнюю оценку из задачи 2), получаем © > с(и л) х — ( 11 х ехр — (. Но ехр( — (12пЛр) ') > ехр( — (Зп) ') > ехр с — — з > 12иЛр ) 9 > — при и > 3, ехр ) — — ~ > —.
При п = 2 и Лп, = рп = 1 выполняется равенство. 4) Верхняя оценка „К © ("п)К(',')'=„',(:.) 5) а) Неравенство легко проверяется в случаях, когда Л = — (поскольку ~ ~("„) < 2" = (-) (-) ); ь> /з п — 1 Лп = и — 1 (левая часть есть п -1- 1, а правая равна ( ) и); си — 1/ 3 < п < 5, п/2 < Лп < п — 1 (непосредственно). Пусть теперь и > 5 < Ли < и — 2. Из задач 4) и Ц следует, что (1) < Л(2Л Ц (Л ) < Л 1 (2Л вЂ” Ц '(2яп(1 — Л)) '1 Л "вр "".
б) в) и и/2 к>л Положим у(Л) = Лцз(2Л вЂ” Ц '(2кп(1 — Л)) Пз. Требуется показать, что 1(Л) < 1 при Л Е (1/2 4-е, (и — 2)/и), где е = 1,1п при четных и и 1/(2п) при нечетных и. Дифференцируя по Л., замечаем, что функция 1(Л) выпукла вниз на исследуемом сегменте. Поэтому максимальные значения следует искать на концах сегмента. Имеем ~ ( — -~ е) = )/ — +е (1-~-2е) (2ки ( — — е)) = ((1 — 4е ) 2ки) < ((1 — — ) 2кп) < 1 при всех и > 5. 2) Нижняя оценка вытекает из решения задачи Ц.
Для получения верхней оценки, воспользовавшись неравенствами (2), имеем 393 Гл. '1П1. Элементы комбннаторики Рассмотрим правый конец интервала: нри п ) б. Если Л < 1/2, то гг = 1 — Л > 1!г2. б) Поскольку С ) = С ), то с использованием задачи о) получаем,что ~ ~(,)= 2 ( )<р '"Л о<й<Л йг И й — ! гй — ! 59. Ц (п)!. = п П (1 — — ) = и, ехр (~!в (1 — — )), но =о =1 й — 1 й-1 г й — 1 !в(1 — — ) = — ~ ~2 — ( — ) = — ~ ~— ~ ~г . =1 =1 =1 =! й — 1 2) Очевидно, что (п)й ( пй. С другой стороны, (п)й = П(п — г) > =о ) (п — й) ' = и'(1 — С вЂ” )) > г!'(1 — — ) (так как й = о(й)п!)) п (1— — о(Ц). й-1 3) Воспользуемся тем (см.
задачу 5.13, 2))! что ~г г = (и,'- Ц й"+ -й *=1 -й О(й'). Отсюда в силу задачи Ц имеем цри й — й оо и й = о(п) (п)й = п" ехр ( — ~ ~(ип") '((р+ Ц 'й"~' -й О(й')) ~ = =и ехр~ — ~ ~( +О( — ( — ) ))(. Но йг-1-! 1, .1-! -й ~ о(и -г- Ци ~ и(и -!- Ци ~ и(~ -!- Ци =-1 =1 >т ~ — "„= й ~ (-") = й (-"), ', = О ( — '„, ) . Отсюда и следует искомое равенство. 4) Следует воспользоваться задачей 3) лри гп = 3. 5.10. Ц В силу задач 1.13, б) и 5.9, Ц имеем 2) Использовать задачу 5.9, 3). 394 Ответы, указания, решенпя 5.11.
1) Имеем ( 'У(") ='",,' =П('-." 1) = = ехр ~~ 1п (1 — — )~ = ехр( — ~~! й-! й — ! .а = ехр ~ — в ~ п — ! 2 еп — !)! =о .=а С использованием задачи 5.12 имеем й — ! й — ! к.',=..;„"(-.') к,„', =," „(-.(-,')) '"„.'„'„, = Е-.' ('„') й — ! йеп — !) " = !е!еп — й -й 1) "~ — п ~ ) -~- Ой!!о — й) ) и — 1 е=а вытекает требуемая оценка. задачи 1). Использовать решение задачи 1) с учетом неравенств в 8 ) < —, при 2в+й(п, и и — !) 1п — й-!-1)! -( )-- -ЕК =а =! ! †! 1 и 1 Е < 1п и — ! и — йа1 п.— йх1 =а — 1п11 — о) (о-йо пРи 0(о(1е!2, 1п (1 — ) < — —. 5.12.
Указание. Сумма ~~ з!еа) является верхней, а ~ !'йй) й= -!-! й= нижней интегральной суммой пля / ! 1х) ейх. 5.13. 1) Имеем йсм. задачу 5.12) ) 1пй ( / 1пхе1х -!- 1пт, й=! ! Отсюда ~ 1п й < т 1п т — т й 1 й 1и т. й.— ! при и ) 2. Отсюда 2) Вытекает из 3) Указание.
й-! 1пхе1х = х1пх — ) е1х = х1пх — х+ 1. ! ! 395 Гж )ЛП1. Элементы комбиногаорики С другой стороны (см. задачу 5.12), 1п Й > / 1лкдк = т1пт — т -Р 1. 1=1 1 2) .7) Аналогично задаче 1). 5.14. Ц Индукцик по тл. При и = 1 имеем р! = Ро — ар, '= 1 — а. Ото сюда О < р! < 1.
Пусть О < р < 1 для некоторого п > 1. Тогда р +! = = р„— арр! = Р„(1 — ар,", '). Поскольку О < а < 1, /1 > 1, О < р„< 1, то и О<р <1. 2) Следует из того, что р +! — р = -ар„< О. з 3) Оценка сверху. Имеем л ' л = 1. Отсюда е арл.— 1 1 </ = р„- -1. РА--1 — РА < /ие 1 1 е / аке аф — ц р Отсюда р„' Е > 1-1- а(/1 — 1)п, или, что то же самое, р„< (1+ а(Д вЂ” 1)п) Д р»/р — 1 < 1 — а/(1-1- а(Д вЂ” 1)(п — 1)).
Палее Ц / "* <~, Рл 1-РА (ААА) а(!у — 1) " у е Ре р„л=! Заметим, что из (АА) слепует, что р, > р (1 — а) 1 < й <) / — ( и РА ~>РА — !(1 — (с/А/й)) при )л >)А/пл[, где с -- константа. Отсюда с учетом того, что (РА-1 — РА)/(арл !) = 1, получаем Рл — 1 — Рл Е е ар Р!.— 1 РА '5 РА — 1 Рл + Ъ < (а(1 — а)) ~А/и(+ = п+ О(А/и). получаем,что при /) > 1 С учетом (***) 1 (Р1 д 1) <и+О(/и) а(Р' — 1) Отсюда ро >м (а(л! — 1)(п Р 0(1/и)))п!1 ~А. таким образом, при и -+ оо .. -(-(1 - Ип)""-" Оценка снизу. Из (*) и из рекуррентного соотношении р„= = Р -1(1 — ар„',) следует, что 396 Ответы, указания, решения 5.15. 1) Перепишем уравнение в виде х = 1иС вЂ” 1п(х) (в). Поскольку С -э оо, то можно считать, что С > е, и, следовательно, х > 1.
Тогда из (*) вытекает, что х < 1п С, т. е. 1 < х < 1и С. Отсюда 1и т = 0(1и 1и С). Таким образом, х = !и! -С- 0(!и1вС) при С вЂ” с оо. Логарифмируя, находим, что l!п!и С Л Л ' 1и 1и С Л 1их = 1и!и!+ !и (1+ 0 ( — )) = 1и!иС-1-0 ( — ) . Подставляя в (в), 1и С рп с С 1и 1и С Л получаем новое приближение х = 1и С вЂ” 1п !и С + 0 ( — ). Вновь логариф!ис )' мируя и подставляя результат в правую часть (в), получим еще одно приближение, дающее требуемую точность (смз Нв Брейн Н.Г.
Асимптотические методы в анализе. Мз ИЛ, 19б1). 2) Поскольку С вЂ” с оо, то и х в сю. Поэтому е' < С, или, что то же самое, х < 1п С. Отсюда е' = С вЂ” 1их > С вЂ” !и 1п С и х > 1п С + 1и (1 — — ) = 1п С вЂ” ~ — ( — ) =3 1и !и С ((1и 1и С ) з) = !и! — -1-0 с с С использованном этого неравенства получаом — х < — ( — "," +0 (( "," ) ) ) = =С вЂ” !и1пС вЂ” 1п(! — +0( — ( ) )) =С вЂ” 1п!и!+О( ). Прологарифмировав, получаем х<!и(С вЂ” ВПиС+О( '"')) =!и!+!и(1 — '"'"'+О('"„')) = 1и1 С ((! 1иС) ) Верхняя и нижняя оценки совпадают с требуемой точностью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
