Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 80
Текст из файла (страница 80)
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иС) ) Верхняя и нижняя оценки совпадают с требуемой точностью. 5.16. Указание. Показать сначала, что С(С) = О(С) при С вЂ” С со. Тогда исходное равенство можно будет записать в виде всНс1 = С+ о(С). Пользуясь этим неравенством, показать, что С" (С) = 0(1), и преобразовать с.С С с! 1и С исходное равенство в е Н = С+ 0(1). Наконец, доказать, что у(С) = — + 0(-,') 5.1У.
1) Разложим А(С) на простые дроби: А(С) = + +... Лс — с Лз — с -1- В(С), где В(С) многочлен. Для нахожцения коэффициен— О(с) та сс умножим А(с) на Лс — С. Тогда (Лс — С) А(С) = (с — Лэ)... (с — Л,„) ' — с)(л ) При С = Лс левая часть равна сс, а правая, . Таким образом, сс = Р'(Лс) — с)(л ) . Аналогично можно вычислить и коэффициенты с, (с = 2, ... Р'(Л ) 1 ..., т). Дробь можно разложить в геометрическую прогрес- 1 — С!Л„ 397 Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
