Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 77
Текст из файла (страница 77)
= в"'Л' 1в = и, ..., и -~- Ь) в левую часть»Ц и полагая ре = 1, получаем Цп) = »п4- й)">Л™в»+ рг»п 4-й — Ц" Л"" -т...-~р»п'"Л" = =Л" (~ „,( +й-1)-Ль-") =Л" (' ,Лв-'~,~ (,.)<Ь-Р --*) = >=о >=о =е = Лапы (~ ( . )п '~> р>Л '>»ь' — г)') = Лапы (~~ ( . )гг 'Р,(Л)), =о >==о >=О где Р,1х) = ~ ~р 1/с — у) х >. Заметим, что Ро»х) = Ргх), где Р - мно>=о гочлен»2). Поскольку Л является т-кратным корнем многочлена Ре, то Регх) — 1х — Л)'Цо»х), где»ве некоторый многочлен.
Нетрудно прова»» рить, что Р,г >1х) = х — Р,1х). Поэтому Р, = 1х — Л) '»в',1х), где Щ Йх многочлен. Отсюда следует, что Р,1Л) = О при всех г < гт Следовательно, ЦЛ) = О. Тем самым»Ц выполнено для последовательности гг'"Л" при гп < т, а тем самым и для последовательностей указанного в условии вида. Докажем теперь, что любая последовательность а„, удовлетворяюп»ая 1Ц при условии, что Л, является корнем кратности т, »г = 1, ..., в) много- члена»2)> имеет вил, указанный в формулировке задачи. При этом без ограничения общности будем полагать, что р» ~ О, т.е.
что нуль не является корнем характеристического многочлена. 1Если р» = О, то можно упростить 1Ц.) Для доказательства 1см. решение задачи 3)) достаточно 377 Гл. 1'111. Элементы комбанаторики показать, что для любых ао, аг, ..., аь г система сг,г -с... -~- с,,г = ао, (сгд -~ сг,г 4-... -~- сг,„)Лг л-... 4- (емг 4-...
л- с. г. ) Л, = аг, (сгд+ сг г(Ь вЂ” Ц+... +сгл,(Ь вЂ” Ц"')Л, '+... ... Ч- 1'смг -~ с.,г(к — Ц + ... + с„,„.(Ь вЂ” Ц'*)Л~ ' = аь имеет решение. Пля этого достаточно показать, что ее определитель не равен нулю, иличтовекторы Ло, ..., Лг ы где Л, = (Лг, гЛ*„..., г" Л'„... ..., Л'„гЛ'„..., г"'Л',) (г = О, ..., Ь вЂ” Ц, линейно независимы. Предположим противное. Тогда существуют константы бо, о1ы ..., дя ы не все рано-1 ные нулю, такие, что Л = о1оЛо +...
+ Оз-гЛь-г = О Пусть Я(х) = )~ Ах' *=о 41 и Л оператор такой, что г51(х) = х —. Положим гЛ~ 7 = гз(гЛь ~Д. Ых То Л = (ЬЗ<Л ), ЛС)(Л,), ..., Л"' г®Л ), ..., ®Л,), ...., Л"-' 'ЕЛ,)). Заметим, что Я(Л) = Лс~(Л) = ... = Л' СГ(Л) при Л = О тогда и только тогда, когда Л является корнем кратности г многочлена Я(х). Таким образом, Л = О означает, что Лг является хорнем кратности гг, Лг является корнем кратности гг, наконец, Л, является корнем кратности г, многочлена С1(х).
Но гг 4- гг + ... + г, = К, а С1(х) является многочленом степени меньше к и, следовательно, не может иметь к корней. Пришли к противоречию. Таким образом, система (л) имеет и притом единственное решенно. 3.2. Ц сг + сг 3". Характеристический многочлен хг — 4х+ 3 имеет корни Лг = 1 и Лг = 3. С использованием задачи 3.1, 3) получаем общее решение с~ Л7 + со Л",. 2) сг( — 3) И'+сг( — Ц" ( — 3)"1г. 3) сгИ14- чг5)г2)" Ч-сги1 — чгб)!2)'. 4) ( — Ц"(сг+ сои).
5) (сг+сггг)( — 4)" +сз( — 2)". 6) ( — Ц" (сг 4- с и 4- сгпг). 3.3. Ц 74-3". Общее решение сг 4-с 3" 1см. задачу 3.2, Ц). Из начальных условий имеем сг + Зсг = 10, хг+ 9сг = 16. Отсюда сг = 7, сг = 1, ао = 7+ 3". 2) 3" + (~/ — Т)" + ( — з/ — Ц". 3) сг ->сгп.-~аз( — 2)", где сг = (14 — Ь вЂ” 4с)/9, сг = (Ьч-с — 2а)гг3, сз = (2Ь вЂ” с — а)/18. 4) сов огг.
Корнями характеристического многочлена являются Лг,г = = е ' = сова хаша. Общее решение а, = сгЛг -> сгЛг. Из равенств аг = = сова, а = сов 2о находим сг = сг = 1/2. Отсюда а = (Лг 4- Лг)/2 = = сазан. 5) 1 — (-Ц". 6) 3" (1+и). 3.4. Ц Подставляя ап+ Ь в (3) вместо а„, получаем, что а(п Ч-2) 4- Ьч+ р(а(п+ Ц + Ь) + д(ад + Ь) = па + гг.
Сравнивая коэффициенты при п в левой и правой частях, а также свободные члены, получаем, что а = = пД1 4- р -~- д), Ь = Я1 -~- р -~ д)13 — п(2 4- р)) Д1 4- р -~- 9) г. 378 Ответы, указания, решенпя 2) Из того, что х = 1 является корнем многочлена х + рх+ д, следует, что р = — 1 — д. Подставляя п(ап 4- Ь) вместо а в равенство а ег -~- +ра„ег — (р+ Ца„= пи+(), получаем, что а = аД2(р+ 2)); Ь = = (211(р -Ь 2) — а(р -Ь 4))Д2(р 4- 2) ). 3) Поскольку х = 1 является кратным корнем многочлена х + рх+ д, г то р = 2, д = 1. Подставляя пг(ап+Ь) вместо а„в равенство а„ег+ + 2а ег + а„= оп + 13 и сравнивая коэффициенты при и, п, п, п, полуз г е чаем, что коэффициенты при пз и иг равны О и а = а/6, Ь = (гд — а)/2.
4) обзцее решение дпя задачи Ц а„= сг Л" ,+ сгЛг' + аггД1 + р+ д) + -Ь (ег(1 4-д -Ь р) — а(р Ь 2))/(1-Ьр 4-д)г), где Л11 гг = ( — р х;/р' — 4д)/2; для задачи 2) а„= сг( — р — Ц" + с + агг/(2(р+ 2)) + (2)3(р+ 2) — а(р х х 4))/2(р -Ь 2) г); для задачи 3) а„= пг((ап/6) т (11 — а)/2) + сгп + сг. 3.5. Ц а.„= 1 4- ( 2) . Общее решение рекуррентного соотношения епЛ а тг — ав = О есть произвольная константа с. Частное решение соотношения Ц будем искать в виде а,', = п(аи+Ь).
Подставляя его в соотношение Ц, получаем, что а,*, = п(п — 1)/2. Обгнее решение соотношения Ц имеет вид а = а' 4-с. Из условия аг = 1 находим, что с = 1, а следовательно, а = 1 -1- п,(п — Ц/2. 2) а = 2( — 4)" — 3 2" 4- 5". Общее решение однородного соотношения а„вг + 2а„ег — 8а = О имеет вид сг( — 4)' + сг 2". Частное решение неоднородного соотношения 2) будем искать в виде а*„= д. 5". Подставляя а," вместо а, (г = и, п+ 1, п+ 2) в соотношение 2), получаем, что е( = 1. Общее решение неоднородного соотношения 2) сг( — 4)" -Ь сг . 2 + 5"; из начальных условий находим, что сг = 2, сг = — 3.
3) 2" ','-(ьг2)" '. 4) — -Ь вЂ” ( — 2)" 4- . 5) 2" з(иг — -~-8). 27 27 18 6) ( — -ь п)2" -ь — ( — 3)". 3.6. Ц Невырожденным является случай, когда либо дг р О, либо рг Ф ф О. Если дг = рг = О, то, очевидно, и„= сгрг, Ь„= сгдг. Пусть дг ~ О. Тогда Ь, = 17(дг(а„ег — рга„)), Ь„ег = 1Ддг(аюы — р~аты)). Подставляя Ь„хг и Ь„во второе соотношение, получаем а вг + ( — рг — дг)а„ег + + (рпдг — ргдг)а„= О. Задача сведена к задача 3.1. а) а„= (5-ь 2п) 2"., Ь = — (1-ь 2и) 2". 3.7.
Ц Индукция по и. При гг = 2 соотношение Гге,„= РгР„, -Ь + ГгГ, ег = Г + Р тг верно ддя всех гп > 1. Индуктивный переход п-гп+1: Г„ег< = Г„т +Г„„, г = Г, гГ +Єà вг+Р„гГ + +Г„,Р „=Äà +Г„„Г,„„. 2) Провести индукцию по Ь. 3) Если бы Г„ег и Г„имели общий делитель е( > 1., то и Г„г и Г„ имели бы тот же общий делитель., поскольку Р г = Р ег — Г„. По индукции отсюда вытекало бы, что и Рг и Гг имели бы делитель е(. 4) Способ представления.
Если Х = 2, то Х = Гг -'г Гп Если гЛе > 2, то выбираем нанбодыпее гг~ такое, что Г„, ( Х, затем наиболынее т~г такое, что Г„г ( гЛе — Г„,, и т.д. Тогда Х = Г„, + Г„+... Поскольку Г„< г > Г„при п > 1, то представление не может содержать двух чисел с одним и тем же индексом п > 2. Представление не можот содержать двух соседних чисел Г„и Г,, г, поскольку Г„4- Г тг = Г„ег, Гл. )СИ1.
Элементы комбинагпорики 379 и, значит, на том шаге, когда было выбрано Р„еы должно было быть выбрано Г лз. 5) Общее решение рокуррентного соотношения Р„лз = Г„ез + Ро дано в задаче 3.2. 3) Используя начальные условия, получаем результат. б), 7) Показательство индухцией по и. 8) Применяя дважды тождество из задачи Ц, имеем Рз = Ро — 1Рз т ГпРз ез — à — 1(Р— 1Г т Г г л1) т Г (Г т Р ез)— = Р,',,Г„-ь Р„, ЄÄ., -~- Р,', —,— Р,'„,(Г„е, — Р„,) = з,з = Ктг ЬРо л à — 11'" +Р езР— з(Р Р ез) = =Р.„-:-Р.
-~Р. зР.-Г.~.зР., =Р;е, ~-Р;. -Р. з з 3 3 3 3 з з 3.8. Ц (1 — Ц '. 2) 1-~-С-Ь... -Ь С = (С' ~' — ЦДС вЂ” Ц. 3) (1 — оС) '. 4) е '. 5) (1-Ь С) '. б) С(1 — С) з. 7) 2Сз(1 — С) 8) (1-~- С) . 9) (1-~- С) . 10) С(С -~- Ц(1 — С) 1Ц Сз1по(1 — 2Ссозо+Сз) '.
12) (1 — Ссозо)(1 — 2Ссозо+Сз) 3.9. Ц е'. По определению Е(С) = ~ ",' = ~ ~—,. Этот ряд сходится к е'. 2) е '. 3) Се". 4) Сзе'. 5) (1-> С) . По определению Е(С) = ~ ~( " = 'у (т)С" — (1 л Ц" б) е'(С -~- С). 3.10. Ц .6) Сравнить хоэффициенты при С~. 311 Ц( )~д™ 'р" 2)1 3)( — Ц"( l) 4)( — Цо '"( ) ) (- ).--~. (- )"'-"(;) („.-'",„) я 8)( 2) 2и — ( 2) 2" . 9)( — Цо 'и ( — цп-' С 10) . Воспользуемся тем, что СС, = агсС8 С. Имеем 2п — 1 1 -~- зз е (1+ я ) ' = ~ ~( — Ц" л ". Интегрируя левую и правую части в пределах ( ц Сз.ез от 0 до С, получаем, что агс18 С = з 2п+ 1 1 3 ...
(2п — Ц 1 С би 1Ц ''' .. Указание. Сс = агсзш 2 4 ... 2п 2па1 зСТ-.Ф о (-2)" Сз 12) при четных и и 0 при нечетных и. (и/2)! ( — цнС' 13) при четных и и 0 при нечетных п. (и/2 -~- Ц! 14) ( — Цн(т 1). 380 Отпветьь указания, реьхеннх 3.12 1) Сравним коэффициенты при 1" в тождестве (1 + 1) *(1+1) ~ = (1+4)" з. С одной стороны, этот коэффициент равен 2) Рассмотреть тождество (1-~1) (1 — 1) = (1 — 4з)'" и сравнить коэффициенты при 1 ". 3) Рассмотреть тождество (1 — 4 ~)"' *(1 — 1) " ' = ( — 1)"'1 "'(1— — 1) " и коэффициенты прис 4) Рассмотреть тождество ((1 -1- 1)" 4- (1 — 1)" ) з = (1 -~- $) " 4- 2(1 — 1~)" ф -Ь (1 — 1) " и коэффициенты при 1 Ь) Рассмотреть тождество ((1 + 1) " -Ь (1 — 1) " )((1+ 1) — (1 — 1) "' ) = (1+1) " — (1 — 1) з и коэффициенты при Ры б) Рассмотреть тождество (1 — Х)з" (1+ 24(1 — 1) )" = (1 +Ьз)" и коэффициенты при 1 '".
3.13. 1) А(4) = ~ ~о„с" = ~ ~—" 1" /е 'х" бх = /е *) — ", (х1)" бх = =о о о = / е 'Е(х1) Их. о х = Ге "с1н = (1 — 1) 1 — С/ о о 3) Для последовательности а„из условия имеем А(1) = ~ (л)з1", Е(1) = з< о<э<- о<э< Палее, е'Е(хс) Их = ~ е ~ ~бх = Г (хс)" (п — 1)! о о э=о ( е 'х" Их = ~> (и) 1" = А(1). э=а 3.14. Ц Воспользоваться тождеством (1 + 1)'+~ = (1 ф 1) . (1 Ь 1)~. Сравнивая коэффициенты при 1", получаем, что Умножая обе части на и!, получаем доказываемое равенство. 2) Положим а' = о/Ь, Ь' = Ь/Ь. Применяя тождество, доказанное в задаче 1), к а' и Ь', получаем, что (о' 4- Ь')„= ~ (',) (а')„я(6')ь, Умножая обе части на Ь", получаем доказываемое тождество (ибо (о'), Ь' = (а), ь).
Гл, )г111. Элементы номбннатпорнни 381 3.15. Ц Умножим равенство а„= ܄— Ь„г на 1" и просуммируем по и. В области сходимости рядов ~ ~а„1" и ~~ Ь„В' справедливы тождества =о ° =о а 1~ ~ ~(Ь Ь ЦП ~ ~Ь Ьг ~ Ь ге В(1)(1 1) =о =о =о »=1 2) Умножим равенство а = Ь тг — 6„на 1"т' и просуммируем по п в пределах от О до ж. Получим 1А(1) = В(1) — Ьо — 1В(1).
3) Заметим, что Ь„= сг„г — а,. Отсюда В(4) = — А(Ц(1 — С) + а причем а г = В(Ц. 4) Умножая равенство а = пб„на 1" и суммируя., получаем А(1) = пЬ 1' = 1 — В(4). =1 6) Аналогично задаче 4). б) Сравним коэффициенты при 1" в равенстве А(1) = (1 — 1) ЯВ(1). Этот коэффициент ддя левой части равен по определению а„а ддя правой (-Ц'(,") Ь„, = , '("+,'. ') Ь„., = Вь(6„). г=о г=о 7) Имеем В(1иг) = ~> Ь„с" ~, В( — 1П') = ~ ~( — Ц" 6„1'о .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
