Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 80
Текст из файла (страница 80)
Но йг-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, или а = ъ Ь, так как а > О.
Если ив = эгь, то а~ = (ав+ 6)ав))2 = = (ьгь-Е эгь))2 = ъ'Ь. По индукции легко получим., что а„= ъ'Ь. Рассмотрим случай, когда ав > Ь (случай ав < Ь аналогичен). Покажем, что в этом случае а„убывает и а„> эгь при всех п > О. Если а„> ъ'Ь при некотором п>О,то а„~.~ — а = ((а„+ — ) /2) — а„= " < О. Таким образом, а„убывает с ростом п, а„— Ь= — (а„+ — ) — ГЬ= " >О. ! / 6 Л <а.— 6)' 2 ~, ав) 2а„ Следовательно, а„убывает и ограничено снизу. Значит, существует предел а = !!ш а„. Как мы убедились, этот предел равен ьеьй з- 2) Как и в задаче Ц, если предел аэ существует, то он равен чЬ.
Рассмотрим случай ав < чь. Так же, как н в задаче 1), доказывается, ззе. что а, монотонно возрастает и а„< убь при всех п. Отсюда следует существование предела а,. Если !!пг аэ = а, то., переходя к пределу в зрекуррентном соотношении, получаем, что а = чЬ. 399 Гл. )г111, Элементы комбонагоороко Отсюда вытекает, что если а„< 1/8, то и а„ог ( 1/8 при и > 3. 2) Пользуясь тем, что а„< 1/8, выведем из (4) новое неравенство: 131 "' Отсюда по индукции а < 9 ( — ) 4 1 гзз тг 3) Используя задачу 2), выводим из (4) а,ег < зз + бба„( — ) Пользуясь последним, получаем, что а = 2 (1+ О (( — ) )). ~~4 5.22. Индукцня по п. При п = 1 имеем аг = аг 1.
Если а„< аг ° п, то а„+г < а„-6 ог ( аг(п -!-1). 1(п, й+1) и — й г. 5.23. Ц Рассмотрим отношение аь = ' = 2 . Ес- 1(п, й) й+1 ли й < (!о871обгп), то аь > 1, если же й > (!обо 1обгп), то ае < 1. Следовательно., максимальное значение /(п, й) достигается либо при й = = (!обг !обг п), либо пРи й = (!обг 1обг п) -!- 1. 2) Тот же результат, что и в задаче 1). 5.24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
