AOP_Tom1 (1021736), страница 140
Текст из файла (страница 140)
Эту последовательность изучали Жан Бернулли П1 (3еап Вегпои!й 1П) в 18 веке, А. А. Марков — в 19 веке, а впоследствии — многие другие математики; см. К. В. Бсо1агайу, Санат)1ап МасЛ. Ви11. 19 (1976), 473-482 37. [Г1Ьопасс1 аьиага 1 (ПесешЬег, 1963), 9-12.] Рассмотрим систему чисел Фибоначчи из упр. 34. Если в ней и = Гат + - + Г»„> О, то положим д(п) = Г»„. Пусть д(0) = оо. Докажем следующие свойства. (А) Если и > О, то д(п — д(п)) > 2д(п). Доказательство.
Р(п — й(п)) = Г»„т > Г»„аа > 2Г»„так как Ь, > 2. (В) Если 0 < т < Га, то д(т) < 2(Г» — т). Доказательство. Пусть д(т) = ГВ т < Га-» + Га-з+. + Гт»1»-а-Ю аь т = Гт-~+1»-»Юньы + Г» < »Гт + Г». (С) Егл™ 0 < т < р(п), то 1»(п — та(п) + т) 2(и(п) — т). Доказательствоо. Следует из (В). (П) Если 0 < т < д(и), то д(п — т) < 2т.
Доказательство. В (С) положим т = д(п) — т, Теперь докажем, что если имеется и фишек и на следующем ходе можно взять мак- симум 9 фишек, то данный ход будет выигрышным тогда и только тогда, когда д(п) < д. Доказательствоо. (а) Если д(п) > 9, то после каждого хода получается положение и', д', где д(и') < д'. [Это следует из (П); см выше.] (Ь) Если д(п) < 9, мы можем либо выиграть на атом ходу (если 9 > и), либо сделать ход, который приведет к положению и', д', где д(п') > 9'. [Это следует из (А); см, выше, Делая ход, мы должны взять д(п) фишек.] Можно легко показать, что если и = Г», + + Га„, то выигрышные ходы состоят в том, чтобы брать Г», + + Га„фишек для некоторого у, 1 < у < т, при условии, что т = 1 либо Г»,, > 2(Г», + + Га„).
Для числа 1 000 имеем следующее представление Фибоначчи: 987+ 13. Существует единственный удачный ход, позволяющий добиться победы, — взять 13 фишек. Заметим, что первый игрок всегда имеет шансы выиграть; исключение составляет случай, когда и не является числом Фибоначчи. Решение для более общих игр подобного типа было получено А. Швенком (А, ЗсЬъепй) [Г! Ьоласс1 Яиаггег!у 8 (1970), 225-234]. 39.
(3" — ( — 2)")/5. 40. Индукцией по т докажем, что У(п) = т для Г~ < и < Гмеь Во-первых, 1(п) < птах(1+ у(Г ), 2+ у(п — Г )) = т. Во-вторых, если 7(п) < т, существует некоторое /с < и, такое, что 1+7(/с) < т (отсюда (т < Г т) и 2+т(п — 1с) < т (отсюда и-1» < Г -з).
Следовательно, и < Г,„» + Г,„з. [Таким образом, деревья Фибоначчи, которые будут определены в разделе 6,2.1, минимизируют максимальную стоимость внутреннего пути от корня до листа, если правая ветвь стоит вдвое дороже, чем левая.] 41 Г»т+т + . + Г»„ат — — фп+ (ф'"' ч- . + ф' ") — зто целое число, а величина в скобках лежит между р~+тз~+ = ф ' — 1 и ф Ч-Чт" + = ф '. Аналогично Г»т»-~- .+Г»„-т = ф и+(ф '+'' + ф ") = 1(ф 'и).
[Такое смещение чисел Фибоначчи представляет собой удобный способ перевода в уме миль в километры и наоборот; см СМаГЬ, з6.6.] 42. [87Ьопасст Яиагаег1у 6 (1968), 235 — 244.] Если существует такое представление, то имеем тГи-г+пГи = Г»т+и+Га,+и+ +Г»„+и для всех целых Ат. Следовательно, существование двух различных представлений противоречило бы упр. 34.
Обратно, существовштие таких совместных представлений для всех неотрицательных т и и можно доказать по индукции. Но гораздо интереснее воспользоваться предыдущим упражнением и доказать, что такие совместные представления существуют, возможно, и для отрицательных целых т и и тогда и только тогда, когда тч-фп > О.
Пусть Ат достаточно велико для того, чтобы выполнялось неравенство ]ттз ~ ' + п»5~] < ф ~, и представим тГи-т + лГи с помощью соотношения (тт, Тогда тГи + пГи+т — — ф(тГи т+ пГи) + (тф + пф ) = тт(ф(тГи-т + пГи)) = Г»,аист ч- . ч- Га.+и+в Отсюда следует, что (*) выполняется для всех Ат. Теперь положим Ат = 0 и Ат = 1. РАЗДЕЛ 1.2.9 1. 1/(1 — 2х) + 1/(1 — Зх) 2. Она следует из (6), так как (,") = и'/Ь'(п — Ь)' 3. С'(х) = 1п(1/(1 — х))/(1 — г) + 1/(1 — г) Отсюда и из формулы для С(х)/(1 — х) следует, что 2 ",' Нь = пН„- п, это согласуется с 1 2 7 — (8) 4. Положим Г = 0 5.
Согласно (11) и (22) коэффициент при хь равен .-".к,1.-' )(,") Теперь применим 1 2 6-(46) и 1 2 6-(52) (или продифференцируем и используем 1 2 6-(46)) 6. (1п(1/(1 — х))) Производная равна удвоенной производящей функции для гармонических чисел, поэтому сумма равна 2Н„~/п 8. 1/((1 — х)(1 — г~)(1 — х~) ) [Исторически это один из первых случаев применения производящих функций Интересный рассказ об исследовании этой производящей функции, которое проводил Л Эйлер в 18 веке, можно найти в книге С Р61уа, 1пг(всгюп апг( Апаlобу зп МагЬешапсэ (Рппсегоп Ргшсесоп Сштегэпу Ргеээ, 1954), СЬарсег 6 (Пойа Д Математика и правдоподобные рассуждения, т 1 Индукция и аналогия в математике (М Изд-во иностр лит, 1957) ] ээ Я! + 1 5! Яэ + э 52 + э 5153 + 1 54 10.
С(х) = (1 + хгл) (1+ х„х) Логарифмируя, как при выводе соотношения (38), получим те же формулы, но соотношение (24) заменит (17) Ответ будет точно таким же, только ЯюЯжЯе, заменятся -Ям — Яэ, -Яе, Имеем а~ = Ям ог = 55~ — 55м г 1 оз = 251 — >Я~Яг+>Ямов = ПЯ~ — 1515>+15>Р+эЯ~Яз — 15а (см упр 9) Аналогичное(39) рекуррентиое соотношение выглядит следующим образом па = Я~а„-~ — Яэа„-э + Замечание Формулы, которые дает это рекуррентное соотношение, называются шождесгпеами Ньютона, так как впервые они были опубликованы Исааком Ньютоном в работе АпгЬтепса 1/шгегазйэ (1707), см П д Яггшй Яоигсе Воой гп МагЬешагкн (Нвгтагб 1)штегэпу Ргещ, 1969), 94 — 95 11. Так как 2 >, Ямх~/ш = 1пС(г) = 2'ь> (-1)ь (Ь~х+ Ьтх~+ ) /Ь, нужный коэффициент равен ( — 1)"'+ '+ т" 'т(Ь~ + Ьэ + + Й,„— 1)'/Ь~'Ьэ~ Ь ' [Умнохгаем на (-1) ', чтобы получить коэффициент при а",'аэ' а" в формуле, где Я выражено через а из упр 10 Альбер Жирар (А1Ьегс Сгагг)) сформулировал соотношения для Ям Ям Яз и Яэ, выразив их через ам ам аз и аэ Эти формулы приводятся почти в самом конце его работы 1пишноп Нопге11е еп А!ядбге (Апшгегс1апц 1629), так родилась теория симметричных функций [ 12.
) а чш х = ) ( )ш г = ) (14~ш) г >в 1/(1 — х — шх) >о >о чйе 13. („'' е "/(Г) 41 = (ее+ +а )(е *" — е ц"+О)/э Сложив эти выражения для всех п, получим 1/(э) = С(е ')/э 14. См упр 1 26-38 15. С»(х) = С -~(г) + хС -э(х) -ь бчо, поэтому Н(ш) = 1/(1 — ш — хш~) Отсюда окончательно находим ГМ=(( ) — ( ) )/ Т 1, Сь( — 1) = (и+ 1)/2 при и > 0 /1 — хеы !" 16. С/,(х) = (1+ х+ .'+х")" = ~ ) . [Обратите внимание на случай г = ао.) ~ 1-. ) ~ ~(-ю) ь рю(ю+1)...
(ю+/г — 1) ь ю ~ ~51 ь ь рл (Есть и другой способ: записать эту функцию в виде е !"!г/!' '!1 и разложить сначала по степеням ю.) 18. (а) Для фиксированного и и переменного г согласно (27) производящая функция равна ~- ~~и+ 1~ „+! (см. формулу (27)). Отсюда получаем ответ: [ "э!'„[. (Ь) Аналогично согласно (28) производящая функция равна 1 — х 1 — 2х 1 — пх ~~ 1п.( поэтому получаем ответ: ("+"). 19. ~ „гЯ вЂ” 1/(и+р/д))х э" = 2 гю "р1п(1 — юьх) — хр1п(1 — х )+эхр =/(х)+д(х), гдею=е ~'/! и э-! р !(х) = ~ " 1п(1 — " ), д(х) = (! — х ) 1п(1 — ) + д р 1 — х Теперь получим 1гш„~! д(х) = д/р — 1пд. Из тождества р/2 — р/2 1п(1 — е'Р) = 1и (2енв "!/! ) = 1п2+ !г(д — я) + 1пэгп— ) ! 2 можно записать /(х) = А+ В, где э-! ьр / пг !8!!5 А ж р ю Р~1п2 — — + — ) = — 1п2+ — + 24/ 2(юр — 1)' э-! В = Э ю "1пгйп-т = гэ (ю э+и !' !Р)1пгйп -!г /г <- г, ь !г ь=! О<э<!/2 д 2рй, /г = 2 ~ ~сов !г 1п эгп — э.
0<э<э/2 Окончательно получаем ! 1+ Р; Р/! + -Р/э = -сос -гг. 2 (ю Р— 1) 2 11 — юр/ 2 1 юг/э — ю-Р/э ! 2 [Гаусс вывел эту формулу в 333 своей монографии, посвященной гипергеометрнческим рядам (соотношенне [75]), но доказательство было недостаточно строгим, Абель обосновал данный результат в работе Сге!!е 1 (1826), 314-315.[ 20.
с ь = /г!(™) согласно соотношению 1.2.6-(45). 21. Находим г С'(2) + 2С(2) = С(г) Ч- 1. Решением этого дифференциального уравнения будет С(г) = (-1/2)е ьи(Е1(-1/2) + С), где Е!(2) = 1 с 1а!2/й а С вЂ” константа. Эта функция "очень плохо себя ведет" в цкрестиости точки г = О, и С(2) нельзя разложить в степенной ряд. Действительно, так как функция !/и! и/е не ограничена, ряд в представлении производящей функции расходится. Однако при г < О для данной функции существует асимптотическое представление. [См. К. Кпорр, 1пбп!ге Яедоепсез алс) Яепеэ (Потег, 1956), Бесс!оп 66.] 22. С(2) = (1+ 2)"(1+ г )'(1+ 2 )" (1+ 22)"... = (1 — 2) ".
Отсюда следует, что исходная сумма равна ("~" ). 23. При т = 1 получаем биномиальную теорему, где /1(2) = г, а Д1(2) = 1+ 2. Прн т > 1 МОЖНО уВЕЛИЧИтЬ т На 1, ЕСЛИ ЗаМЕНИтЬ г На г (1+г +1) И ПОЛОжнтЬ / +1(21,..., хм+1) = 2!э ! 1/ (21,..., г -1, г !(1+2! .!.!)), Д .!.!(21,...,2 +1)=2 +!д!э(21,, 2 -1,2 (1+2 +1)). Тесла Д2(21, 22) — 21 + 22 + 2! 22 И -1 2! Дт (21,..., ггэ) / (21,,2 ) 2 1+ 1+ 2 Оба многочлена, /и и дм, удовлетворяют одному и тому же рекуррентному соотношению /» = 2 / -1+2 — !/ -г, д = г д -!+2,-192!-г с начальнь!ми условиями / ! —— О, /э = д-! = Де = ге = 1. Отсюда сведует, что дм — сумма всех членов, которые можно получить, начиная с 2!...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
