30. Доказательство проводим индукцией по ш; при ш = 1 утверждение очевидно.

= (-irF„. Е("; )(-l)"--*E.V = 0.

(c) Так как {-l)>Fm-.k = Fk-iF - FkFm-i и Fm ф О, из (а) и (Ь) следует, что

i7U-iy"-F-Fk-, = o.

(d) Поскольку Fn+k = Fk-iFn + FkFn+i, результат следует из (а) и (с). Этот результат можно также доказать в более общем виде, если воспользоваться д-номиальной теоремой из упр. 1.2.6-58. [См. Dov Jarden, Recurring- Sequences, 2nd ed. (Jerusalem, 1966), 30-33; J. Riordan, Dute Math. J. 29 (1962), 5-12.]

31. Используйте упр. 8 и 11.

32. По модулю Fn последовательность Фибоначчи выглядит так: 0,1,..., F„ i, О,

- F„ 2, •. • •

33. Заметим, что cos г = (е + е~) = -г/2 для этого конкретного г, и воспользуемся тем, что sin(n + l)z +sin(n - l)z - 2 sinnz cos 2 для всех z.

34. Сначала докажем, что единственно возможным значением Fjt, является наибольшее число Фибоначчи, которое меньше или равно п. Отсюда п - Fk меньше, чем Fk-i, и по индукции получаем, что существует единственное представление п - Fk Это доказательство во многом аналогично доказательству теоремы о единственности разложения целого числа на простые множители. Система чисел Фибоначчи была предложена Э. Зекендорфом (Е. Zeckendorf) [см. Simon Stevin 29 (1952), 190-195; Bull. Soc. Royale des Sciences de Liege 41 (1972), 179-182]; более общие результаты приведены в упр. 5.4.2-10.

35. См. G. М. Bergman, Mathematics Magazine 31 (1957), 98-110. Чтобы представить х > О, найдите наибольшее к, для которого < х, и представьте х как 0* плюс представление X - 0*.

Представление для неотрицательных целых чисел можно получить также с помощью следующих рекуррентных соотношений, которые справедливы для всех целых чисел, начиная с О и 1 (представление которых тривиально). Пусть Ьп = ф" + = Fn+i Тогда представлением L2„ + m для О < m < L2n-i и n > 1 будет ф" + ф~" плюс представление т. Представлением Lin+i +т для О < m < L2„ и n > О будет 0"+ +0~2""2 плюс представление т - Последний результат получен с помощью соотношения

= 0*-1 + ---- 0*~2j+\ Оказывается, что все строки а, состоящие из

нулей и единиц (такие, что а начинается с 1 и не имеет соседней единицы), встречаются слева от разделяющей точки в представлении ровно одного положительного целого числа. Исключение составляют строки, которые заканчиваются 10*1, но они никогда не встречаются в подобных представлениях.

36. Рассмотрим бесконечную строку Soo, первые F„ букв которой для любого п > 1 образуют строку S„. В этой строке нет ни удвоения буквы о, ни утроения буквы Ь. В строке Sn содержится F„ 2 букв о и F„ i букв Ь. Если выразить m - 1 с помощью системы чисел Фибоначчи (как в упр. 34), то о будет т-й буквой строки Soo тогда и только тогда, когда кг = 2. С другой стороны, Ь будет к-й буквой строки Soo тогда и только тогда, когда 1(к -f 1)<?I>~J - 1кф~\ = 1. Поэтому количество букв Ь среди первых к букв равно [{к -Ь 1)ф~\. Кроме того, Ь будет к-й буквой тогда и только тогда, когда к = [тф\ для некоторого целого положительного т. Эту последовательность изучали Жан Бернулли III

(Jean Bernoulli III) в 18 веке, A. A. Марков - в 19 веке, a впоследствии - многие другие математики; см. К. В. Stolarsky, Canadian Math. Bull. 19 (1976), 473-482

37. [Fibonacci Quart. 1 (December, 1963), 9-12.] Рассмотрим систему чисел Фибоначчи из упр. 34. Если в ней п = Fk + + Fk > О, то положим р(п) = Fj,. Пусть р(0) = оо. Докажем следующие свойства. (А) Если п > О, то ц{п - fi(n)) > 2ц{п). Доказательство. fi{n - fi{n)) = Fk > Fk+2 > 2Ft, так как кг > 2. (В) Если О < m < Fj,, то p(m) <

2{Fk - т). Доказательство. Пусть ц{т) = Fy, т < Fk-i + Fk-з Н-----h Fj+k-i-,) mod2 =

-F,„i+(t i j)n,od2 + Fk < -F, + Fk. (C) Если 0 < m < p(n), то p(n - /j(n) + m) < 2{fi{n) - m). Доказательство. Следует из (В). (D) Если О < ш < р{п), то /j,{n - т) < 2т. Доказательство. В (С) положим т = ц{п) - то.

Теперь докажем, что если имеется п фишек и на следующйи ходе можно взять максимум q фишек, то данный ход будет выигрышным тогда и только тогда, когда /j,(n) < q. Доказательство, (а) Если (п) > q, то после каждого хода получается положение п, q, где р(п) < q. [Это следует из (D); см выше.] (Ь) Если ц{п) < q, мы можем либо выиграть на этом ходу (если q > п), либо сделать ход, который приведет к положению п, q, где р(п) > q. [Это следует из (А); см. выше. Делая ход, мы должны взять /j,{n) фишек.] Можно легко показать, что если п = Fj +••-(- Fk,., то выигрышные ходы состоят в том, чтобы брать Fkj + + Fk,. фишек для некоторого j, 1 < J < г, при условии, что j = 1 либо Fk, , > 2{Fk, + • • • + Fk,.).

Для числа 1 ООО имеем следующее представление Фибоначчи: 987 -(- 13. Существует единственный удачный ход, позволяющий добиться победы, - взять 13 фишек. Заметим, что первый игрок всегда имеет шансы выиграть; исключение составляет случай, когда п не является числом Фибоначчи.

Решение для более общих игр подобного типа было получено А. Швенком (А. Schwenk) [Fibonacci Quarterly 8 (1970), 225-234].

39. (3" - (-2)")/5.

40. Индукцией по то докажем, что /(п) = то для Fm < п < Fm+\. Во-первых, /(п) < max(l + f{Fm), 2 + f{n - Fm)) = то. Во-вторых, если f{n) < то, существует некоторое к <п, такое, что l + f{k) < то (отсюда к < Fm-i) и 2 + f{n - k) < то (отсюда п~к < Fm-2). Следовательно, п < Fm-i + Fm-2. [Таким образом, деревья Фибоначчи, которые будут определены в разделе 6.2.1, минимизируют максимальную стоимость внутреннего пути от корня до листа, если правая ветвь стоит вдвое дороже, чем левая.]

41. Fki+i + + Ffc,+i = фп + (* + • • -Ь *") -это целое число, а величина в скобках лежит между $ + $, + - = ф~-1и + * + ... = ф-\ Аналогично Fk-i + • • + Fb, i =

ф~п+($ Н-----h $") = /{ф~п). [Такое смещение чисел Фибоначчи представляет собой

удобный способ перевода в уме миль в километры и наоборот; см CMath, §6.6.]

42. [Fibonacci Quarterly 6 (1968), 235-244.] Если существует такое представление, то имеем

mFN~i + nFN = Fk,+n + Fk+n + + Fk,.+n (*)

для всех целых N. Следовательно, существование двух различных представлений противоречило бы упр. 34.

Обратно, существование таких совместных представлений для всех неотрицательных то и п можно доказать по индукции. Но гораздо интереснее воспользоваться предыдущим упражнением и доказать, что такие совместные представления существуют, возможно, и для отрицательных целых то и п тогда и только тогда, когда т+фп > 0. Пусть N достаточно велико для того, чтобы выполнялось неравенство [то" +п$\ < ф~, и представим toFat-i + rtFjv с помощью соотношения (*). Тогда toFv -Ь nFv+i = ф{тЕ-1 + hFn) + {т$~ + пф) = /(0(toFv-i + hFn)) - Fki+n+i + + Fkr.+n+i- Отсюда следует, что (*) выполняется для всех N. Теперь положим N - О и N - 1.

РАЗДЕЛ 1.2.9

1. 1/(1-2z) +1/(1-Зг)

2. Она следует из (6), так как () = п</кЧп - ку

3. G{z) = 1п(1/(1 - г))/(1 - + 1/(1 - г)2 Отсюда и из формулы для G{z)/{1 - z) следует, что J2kZl = пНп - п, это согласуется с 1 2 7-(8)

4. Положим ( = О

5. Согласно (11) и (22) коэффициент при г* равен

Теперь применим 1 2 6-(46) и 1 2 6-(52) (или продифференцируем и используем 1 2 6-(46))

6. (1п(1/(1 - г))) Производная равна удвоенной производящей функции для гармонических чисел, поэтому сумма равна 2Нп-\1п

8. 1/((1 - г)(1 - zyi - z) ) [Исторически это один из первых случаев применения производящих функций Интересный рассказ об исследовании этой производящей функции, которое проводил Л Эйлер в 18 веке, можно найти в книге G Polya, Induction and AmJogy in Mathematics (Prmceton Prmceton University Press, 1954), Chapter 6 (Пойа Д Математика и правдоподобные рассуждения, т 1 Индукция и аналогия в математике (М Изд-во иностр лит , 1957) ]

9. iS? + iS?S2 + iS? + SiS3 + iS4

10. G{z) = (1 + xiz) (1 + Xnz) Логарифмируя, как при выводе соотношения (38), получим те же формулы, но соотношение (24) заменит (17) Ответ будет точно таким же, только S2,S4,Se, заменятся -Sa, -S4, -Se, Имеем oi = Si, аг = S? - 5г, аз = 5?-515г+5з,04 = iS?-iS?S2 + iS + SiS3-iS4 (см упр 9) Аналогичное (39) рекуррентное соотношение выглядит следующим образом ппп = SiOn-i - 5зОп-г +

Замечание Формулы, которые дает это рекуррентное соотношение, называются тождествами Ньютона, так как впервые они были опубликованы Исгьаком Ньютоном в работе Arithmetica [/niversahs (1707), см D J Struik Source Boot m Mathematics (Harvard University Press, 1969), 94-95

11. Так как J2m>i Sn.z/m = InG(z) = Et>i(-l)*"4»i + hiz"" + f/k, нужный коэффициент равен (-l)*i+*2+ +"-тn{kl +k2 + +km -iyikik2 fcm [Умножаем на (-1)"*" чтобы получить коэффициент при aJOj в формуле, где Sm выражено через От из упр 10 Альбер Жирар (Albert Girard) сформулировал соотношения для Si, S2, S3 и S4, выразив их через oi, 03, 03 и а4 Эти формулы приводятся почти в самом конце его работы Invention Nouvelle en Algebre (Amsterdam, 1629), так родилась теория симметричных функций ]

12. Е «".п"""- Е {ll)wz = Ya+wrzi/{i-z-wz}

т п>0 m п>0 п>0

13. J2 e~f{t)dt = {ао+ +о„)(е~-"-e~"")/s Сложив эти выражения для всех п, получим L/(s) = G{e")/s

14. См упр 1 2 6-38

15. G„(z) = G„ i(z) + zGn-2{z) + Sno, поэтому H{w) = 1/(1 -w - zw) Отсюда окончательно находим

G„(z)=n--j --j j U/l+Az, еслигф-\,

Gn(-) - (n + l)/2" прип>0