Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 80
Текст из файла (страница 80)
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 Гл. 1715 Элементы номбинагпорини сию (1 — — ) = ~ ~( — ) .
Получаем А(С) = ~ — * ~ ( — ) -~- В(С). =.о =о Отсюда для больших и имеем а„„„, + „, т ...->, „, сзЛ, сз сз сы 2) Рассмотрим сначала случай, когда Р(С) не имеет корней, кроме Лм а СС(С) имеет степень меньшую, чем степень Р(С), и Л~ не является кор— 1 нем СС(С). Тогда Р(С) = (С вЂ” Лс)", Я(С) = ~ ИС'. Разложение Р '(С) по =о степеням имеет вид ~-'()=(-» Л; ( — —,') =(- — „') ~(„") —,'„ =о А(С) = = ( — — ) ~ ( — ) ~ Ц,(~ С)Л',. Отсюда а„= ( — 1)" Л, бл "~ ~ д,(п ",.)Лм В обшем случае А(С) = Аь(С)-~- , где Аз(С) — многочлен, Я,(С) — многочлен степени меньС1,(с) 2.(С Л,.
ше г,. В этом случае асимптотическое значение для а„определяется козффипиентом при Со в разложении дроби СсЗз(С)С(С вЂ” Лз)"'. Задача сводится к уже рассмотренной. 5.18. 1) 2 . 3". Воспользуемся результатами задачи 5.17, 1). Многочлен Рз(С) = ЗС вЂ” 41+ 1 имеет корни Лз = — и Лз = 1. Положим Я(С) = — (1+ С), 3 1 1 3 3 Р(С) = Сз — — С 4- —. Тогда 3 3 с)(1/3) с1~ " с 4/9 Р'(1/3) 13/ 2/3 — 4/3 2) а„— — ( — ) ) . Ваименьшнй по модулю корень многочле- 13 (,2,) на 6Сз + 5С вЂ” 6 равен 21'3. Используя задачу 5.17, Ц, получаем результат. »-~-з 3) ао — — С вЂ” ) (. 4) аз„= О, аг„ез ( — Ц" 2" 13 12) 5) Указание.
6С вЂ” 17С + 351 — 221+4 = 6 (С вЂ” -) (С вЂ” — ) (С вЂ” 1-> 4 з з 2 3 + С чсЗ) (С вЂ” 1 — с чсЗ), и„— 3". 31 6) — 2" ~' 15 7) ( )(чсЗ вЂ” 1) " . Корни уравнения Сз+ 21 — 2 есть Лз = з/3 — 1, го С Лз = — ъ'3 — 1. Представив А(С) в виде аС -Е Ь сС + 4 (С вЂ” Л,)з (С вЂ” Л,)-" 398 Ответы, указания, решенпв найдем методом неопределенных коэффициентов, что а = О, Ь = 1.
С ис- пользованием задачи 5.17, 2) получим, что а„= (-1)гЛ," г (6( ) +Л1а( )) = !АЗ вЂ” 1) ( ). /10з +г е — зз 8) а„! — ) ) ). Наименьший по модулю корень знаменателя 7 равен 0,7 и имеет кратность 2. Заметим, что Е-!-1 2 Н вЂ” 0,7)г зег -!- 1 С использованием задачи 5.17, 2)получаем а„ ! †) 5.19. 1) а„! — 3( — 2)"). Пусть А!!) = ~~> а„!".
Умножая обе части =в соотношения на !" н складывая, получаем, что А!!) — аг! — ав+ »эг -!- 3!(А(!) — ав) -!- 2!гА(!) = О. Отсюда с учетом того, что ав = 1, аг = 2, имеем А!!) = Г1 — !)Д2! + Зе+ Ц. Корни знаменателя есть Лг = — 1)2, Лг = — 1. Используя задачу 5.17, 1), получаем, что а„! — 3( — 2)"). 2) 1)2. Так же, как и в задаче 1), находим, что А(!) = (2(1 — !)) ' -!- -г (2(1 — (д — р)!)) '.
Поскольку д -~- р = 1, р, д > О, то !у — р~ < 1. Корнями знаменателя являются Лг = 1 н Л = 0 — р, !Лг! < !Лг!. Теперь с использованием задачи 5.17, 1) илн непосредственно получаем, что а„1)2. 3) а = !з!и — — з!и — ). 4) а 3". 5) а п 2" ,з1 з з) 5.20. 1) Наводящее соображение; если предел аэ существует и равен а, то нз рекуррентного соотношения получаем, что а = !а -Е 6)а)/2, или а = ъ Ь, так как а > О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
