AOP_Tom1 (1021736), страница 26
Текст из файла (страница 26)
г г г г 31. [М20] Покажите, что гг ф шод 1 = 1 — ф г" и гг егф шоб 1 = ф 32. [М24] Остаток от деления одного числа Фибоначчи на другое равен ш число Фибр наччи, Покажите, что по модулю Е„ 33. [НМ24] Пусть з = я/2+ г1пф, Покажите, что агппг/з(па = гч "Е . Е;, ( цг.~.г г ( — 1)" К., ( Ц ч-1+»2 если тшоб4 = О; если т шод 4 = 1; если т шоб 4 = 2; еглн т шоб 4 = 3. ° 34. [М24[ (Сиссаема чисел Фибоначчи ) Пусть запись /с » т означает, что 2 > т+2.
Покажите, что для любого положительного целого и существует единственное представление и = Р», +Е», + +Е»„где (сс >> Ьг » » сс » О. Зб. [М24) (Сисспема фи-чисел.) Рассмотрим действительные числа, записанные с помощью цифр 0 и 1 по основанию ф (например, (100.1)е = ф + ф ').
Покажите, что существует бесконечное множество способов такого представления числа 1, например 1 = (.11)е = (.011111...)е. Но если потребовать, чтобы две единицы подряд не встречалось и чтобы это представление не заканчивалось бесконечной последовательностью 01010101..., то для каждого неотрицательного числа будет существовать единственное представление. Каким будет представление для целых чисел? ° 36. [М22[ (Строки Фибоначчи.) Пусть Яс = са", бг = "Ь" и Я„~.г = Я„»сб„, и > О. Другими словами, Я +г образуется путем помещения б„справа от Я„ес. Имеем Яг — — "Ьа", Яс = "ЬаЬ", Яс = "ЬаЬЬа" и т. д, Очевидно, что в строке 5 содержится Е„букв. Исследуйте свойства 5 .
(Где встречаются две буквы цодряд? Можете ли вы предсказать, какой будет Ь-я буква 5 ? Какова плотность буквы Ь? И т, д.) ь 37. [Муб[ (Р. Ю, Гаскел (К. Е. Саэ1се11) и М. Дж. Виниган (М. 1.%Ыпраап).) Двое играют в следующую игру. Имеется и фишек; первый игрок берет любое количество фишек (но только не все сразу). После этого момента игроки ходят по очереди, причем каждый из них берет одну или несколько фишек, но не более чем двукратное количество фишек, еглтмх предмдуисим игроком, Выигрывает тот, кто заберет последнюю фишку, (Рассмотрим эту игру на конкретном примере. Пусть п = 11.
Игрок А взял 3 фишки; значит, игрок В может забрать до б фишек, но он берет 1. Остается 7 фишек. Игрок А может взять 1 или 2 фишки; он берет 2. Теперь игрок В может взять до 4 фишек; он берет 1. Остается 4 фишки. На этот раз игрок А берет 1 фишку; теперь игрок В должен взять по меньшей мере одну фишку, поэтому на следующем ходе игрок А выигрывает.) Сколько фишек следует взять первому игроку в начале игры, если первоначально имеется 1 000 фишек? 2? сьпнс1 жкнй'в, 38. [86[ Напишите такую компьютерную программу итры, описанной в предыдущем упражнении, чтобы она велась оптимальным образом. 39.
[М24[ Найдите выражение в замкнутой форме для а„при условии, что ао — — О, ас ж 1 и анег = а„+с + ба„ для и > О. 40. [М26[ Найдите решение рекуррентных соотношений ~(1) = 0; )(и) = ппп шах(1 + у((с),2 + у(п — ?с)) для и > 1 е<»<с ° 41. [Мйб] (Юрий Матиясевич (сит( МаИуаэекюб), 1990,) Пусть у(х) = [х+ ф '). Докажите, что если и = Р»с + . + Р»„— это представление числа и в системе чисел Фибоначчи (см. упр, 34), то Р»с+с + + Р»„»с =,с(фп).
Найдите аналогичную формулу для Р»с» + + Р»„— с. 42, [М26[ (Д. А. Кларнер (Р. А. К!агпег).) Покажите, что если пс и и — неотрицательные целые числа, то существует единственная последовательность индексов?сс «?сг ««сс, такая,что а=Р»с+К»с+ +Р»., пжР»с»с+2'»г-»с+ "с+У»,»». (Заметим, что й могут быть отрицательными, а г — нулем.) 1.2.9. Производящие функции Каждый раз, когда необходимо получить информацию о последовательности чисел (а„) = ао, аы аг,..., можно рассмотреть бесконечную сумму от "параметра" г Жг) = ао+агг+агг + .. = ~~' а„г" п>о А теперь можно заняться исследованием свойств функции С.
Данная функция характерна тем, что с ее помощью можно представить всю последовательность. Это очень важно, особенно если последовательность (а„) была определена методом индукции (т. е. если а определяется через оо, аы..., а„г). Более того, с помощью методов дифференциального исчисления по функции С(г) можно восстановить все члены последовательности ао, аы ... (при условии, что бесконечный ряд (1) сходится для некоторого ненулевого г). С(г) называется производящей функцией для последовательности ао, ам аг,....
Использование производящих функций открывает новые горизонты методов и приемов и существенно расширяет наши возможности при решении задач. Как уже упоминалось в предыдущем разделе, А. де Муавр ввел производящие функции, чтобы решить линейные рекуррентные соотношения в общем виде. Джеймс Стирлинг применил теорию де Муавра для решения более сложных рекуррентных соотношений и показал, как применять для этого не только арифметические операции, но также дифференцирование и интегрирование (МегЛодиэ 1ИгегепиаЪ (Еопдоп, 1730), РгороэЖоп 15).
Через несколько лет Л. Эйлер нашел новые способы использования производящих функций, например, при исследовании разбиений [Соштепгагй Асад. Ясй Реа 13 (1741), 64-93; Мог1Соштепа Аеас(. Вой Реп 3 (1750), 125 — 169). Дальнейшее развитие зти методы получили в классическом труде Пьера С. Лапласа (Р~егге 9, 1ар1асе) ТЛеопе Апа1убдие г(еэ РгоЬаЬййеэ (Раг!э, 1812). Очень важен вопрос о сходимости бесконечного ряда (1). В любом учебнике по теории бесконечных рядов доказываются следующие утверждения.
а) Если ряд (1) сходится для некоторого г = го, то он сходится для всех г, таких, что (г( < (го(. Ь) Этот ряд сходится для некоторого г ф 0 тогда и только тогда, когда последовательность ("/(а„О ограничена. (Если зто условие не выполняется, то можно получить сходящийся ряд для последовательности (а„~п!) или другой последовательности, связанной с исходной.) С другой счороны, во время работы с производищими функциями не всегда стоит беспокоиться о сходимости приведенного ряда, так как часто мы только исследуем возможные подходы к решению конкретной задачи.
Найдя решение некоторым способом, каким бы нестрогим оно ни было, мы сможем обосновать его независимым образом. Например, в предыдущем разделе для вывода формулы (14) мы воспользовались производящей функцией. После того как данное равенство получено, уже не составляет труда доказать его по индукции и можно даже не упоминать, что оно было найдено с помощью производящей функции. Более того, можно показать, что большинство операций (если не все), выполняемых над производящими функциями„ можно строго обосновать, не затрагивая вопроса о сходимости ряда. Например, см. работу Е. Т. Ве11, Тгапэ. Атег.
Ма1Л. Яос. 25 (1923), 135-154; 1чап Нггеп, АММ 76 (1969), 871-889; Ресег Неппсс, Аррйег) влс( Сотрпсайопа1 Сотр!ех Апа)уиз 1 (1т'!1еу, 1974), С1сарсег 1. А теперь давайте рассмотрим основные методы работы с производящими функциями. А. Сложение. Если С(с) — производящая функция для (а„) = ао, ам, и Н(з)— производящая функция для (Ьп) = Ьо, Ьс,..., то аС(т) + 13Н(г) — производящая функция для (аап + 13Ь«) = аао + 13боь пас + 13бм .... а ~~~ а«в«+,3 ~~~ Ьпсп = ~~~ (пап + 6Ь„)г".
«>о п>о п>0 В. Сдвиг. Если С(з) — производящая функция для (ап) = ао, ам..., то с™С(з)— производящая функция для (ап „,) = О,...,О, ао,ам..... п>0 «»« -пь% и % и апв =,~ ап.~.«ьс >о В предыдущем разделе для решения задачи Фибоначчи мы комбинировали операции А и В: С(з) была производящей функцией для (Е„), лС(г) — для (Е„с), в~С(г) — для (Ь'„0), а (1 — г — з~) С(з) — для (ń— Р'„, — Р'„0).
Затем, так как разность ń— Е„с — Е„з равна нулю при п > 2, мы выяснили, что (1 — в — сз) С(г)— это многочлен. Аналогично производящая функция для любой линейной рехуррентной последовательности (т. е, такой последовательности, для которой ап = оса« с + .. + с«,ап ) ЯвлЯетсЯ многочленом, деленным на (1 — ссс — .
— с гт). Давайте рассмотрим простейший пример. Если С(в) — производящая функция для носгааянной последовательности 1, 1, 1,..., то зС(с) порождает последовательность О, 1, 1,..., поэтому (1 — г) С(с) = 1. В результате получаем простую, но очень важную формулу: 1 1+ + г+ (5) .1 — 0 С. Умножение. Если С(с) — производящая функция для ао,аы... и Н(в)— производящая функция для Ьо, Ьм..., то С(з)Н(с) = (но+асс+нов + ° ..)(Ьо+Ьсз+Ьоз + ) = (аобо) + (аоЬс + асбо)с+ (аоЬз + аъб| «- азбо)с + СЯН(х) — производящая функция для последовательности со, Следовательно, сы..., где сп = ~~~ аобп ы В«ье (6) В сумме справа суммирование можно распространить на все и > О, если считать, что ап = О для любого отрицательного и. Аналогично (С(г) — ао — а1 с — . — а 10 ') 1'в — производящая функция для (ап+«) = а а +с Соотношение (3) являетсн частным случаем (6).
Другой важный частный случай имеет место, когда все Ь„равны единице: 1 — С(«) = ао + (ао + а1)«+ (ао + о1 + аг)«+ ' ' '. (7) 1 †« Здесь мы получаем производящую функцию для частных сумм исходной последовательности. Из соотношения (6) следует правило для произведения трех функций; г'(«) С(«) Н(«) переиздает последовательность г(о, 4, дг,, где бо = ~~~ а,Ь,сы суд>о ы+>«=~ Общее правило для произведения любого числа функций (в тех случаях, когда это имеет смысл) выглядит следующим образом: П Е.'"=.'С " Е (О) 1>о «>о о>о ь.,ьо..хдо «о+о,+- =» Когда в рекуррентном соотношении для некоторой последовательности содержатся биномиальные коэффициенты, часто возникает необходимость в получении производящей функции для последовательности со,сы..., которая определяется формулой с„= ~~~ („)а«Ь„ы (10) (См, упр, 14.) Например, если т = 3 и г = 1, то ы = — -+ — 1 (комплексный оз.
кубический корень из единицы). Отсюда следует, что а1«+а4«+от«+ = г(С(«)+ы 'С(ы«)+ю С(ы «)). В этом случае, как правило, лучше воспользоваться производящими функциями последовательностей (а„/и!), (Ь„/и!), (с„/и!), поскольку (... -И.. ~м( .. -) ао аг аг г '1/Ьо 61 Ьг г ~ усе с1 сг г — + — «+ — «+ /( — + — «+ — «+ / = ( — + — «+ — «+ ), (11) О! 1! 2! / 1 О! 1! 2! / ~ О! П 2! где с„определяется формулой (10). Р.
Замена переменной х. Очевидно, что С(с«) — производящая функция для последовательности ао, саг, сгаг,.... В частности, производящей функцией для последовательности 1, с, сг, сг,... является 1/(1 — с«). Воспользуемся известным приемом для извлечения членов ряда через один: -(С(«) + С( — «)) = ао + аг«г + а4«4 + (12) г (С(«) — С(-«)) = а1«+ аэ«+ ао«+ Извлекая комплексные корни из единицы, можно развивать эту идею и выбирать каждый гп-й член.
Пусть ы = ег"у = сов(2х/т) + 1о!п(2х/т). Тогда а„«" = — ~ ы ьгС(ы««), 0 < г < т. 1 (13) о спой ю=г о<я<» Е. Дифференцирование и интегрирование. С помощью методов дифференциального и интегрального исчислений можно выполнять над производящими функциями дополнительные операции. Если С(2) определяется формулой (1), то ее производная равна С'(2) = а! + 2азе + Заззз + .
= ~~ (и + 1)азч.зз~. (14) ь>о Производящей функцией для последовательности (па„) является 2С'(2). Следовательно, выполняя операции нод производящей функцией, мы можем найти производящую функцию для последовательности, полученной из предыдущей умножением каждого члена а„ на многочлен от и. Обратный процесс, т. е. интегрирование, дает еще одну полезную операцию: 2 1 3 С(2) Й = аоз+ -а,з + -а22 + ..
= ~ — аь зз". (15) В качестве частных случаев возьмем производную и интеграл от функции (5): 1 (1 — 2)2 = 1 + 22 + 322 + = ~(к + 1)23; (16) 2 1 3 ч 1 3 )и — =2-~--2 +-2 + = ') -2. (!1 7) 1 — 2 2 3 /с ей! 1 1 32 11з — 1п — =2+ -2 + — 2 +. = ~Н32". 1 — 2 1 — 2 2 6 зйо Р. Известные производящие функции. В каждом случае, когда функция разлагается в степенной ряд, мы, по сути, получаем производящую функцию для некоторой последовательности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
