3. [25] Напишите программу, которая вычисляет и выдает на печать числа Фибоначчи от Fl до Fiooo в десятичном виде. (В предыдущем упражнении был определен порядок чисел, с которыми придется иметь дело.)

► 4. [Ц] Найдите все п, для которых Fn = п. 5. [20] Найдите все п, для которых F„ =п. в. [НМЮ] Докажите тождество (5).

► 7. [15] Если п не является простым числом, то и Fn не является простым числом (за одним исключением). Докажите это утверждение и найдите исключение.

8. [15] Во многих случаях удобно определить Fn для отрицательных п. Предположим, что Fn+2 = F„+i + Fn для всех целых п. Проанализируйте эту возможность и ответьте на следующие вопросы. Чему равны F i и F 2? Можно ли простым способом выразить F-„ через Fn?

9. [М20] Используя соглашения из упр. 8, определите, выполняются ли соотношения (4), (б), (14) и (15) при любых целых значениях нижних индексов.

10. [15] Выясните, будет ли значение больше или меньше Fn-

11. [М20] Покажите, что 0" = Рпф + Fn-i и " = Fn + Fn-i для всех целых п.

► 12. [М26] Последовательность Фибоначчи "второго порядка" определяется соотноше ниями

0 = 0, Я = 1, :Fn+2 = Тп+х +Тп + Fn. Выразите Тп через Fn и Fn+i- [Указание. Воспользуйтесь производящими функциями.]

► 13. [М22] Выразите следующие последовательности с помощью чисел Фибоначчи (г, s и с - заданные константы):

a) ао = г, ai = s; an+2 = On+i + On, n > 0;

b) bo = 0, bi = 1; bn+2 = bn+i + bn + c, n > 0.

14. [M28] Пусть m - фиксированное положительное целое число. НаДдите On, если

ас = О, 01 = 1; ап+2 = On+i + On + (,!) при n > О

15. [М22] Пусть /(п) и д(п) - произвольные функции и пусть для п > О

ас = О, ai = 1, an+2 = On+i+ап +/(п); Ьо = 0, bi = 1, Ьп+2 = Ьп+1 +Ьп + д{п); со = 0, Cl = 1, с„+2 = с„+1 + с„ + xf{n) + ур(п)

Выразите Сп через х, у, йп, Ьп и Fn.

► 16. [М20] Числа Фибоначчи неявно присутствуют в треугольнике Паскаля. Покажите, что сумма биномиальных коэффициентов

/с=0

является числом Фибоначчи.

17. [М24] Используя соглашения из упр. 8, докажите следующее обобщение равенства (4):

F„+kFm-k - FnFm = {-iTFm-n-kFk.

18. [20] Всегда ли Fn + F+i будет числом Фибоначчи? ► 19. [М27] Чему равен cos 36"?

20. [М7б] Выразите сумму 5Z=o-* помощью чисел Фибоначчи.

21. [М25] Чему равна сумма Y,l=o кх"1

► 22. [М20] Покажите, что Y.. ()Fm+k является числом Фибоначчи.

23. [М23] Обобщая предыдущее упражнение, покажите, что Yk il)Ft-iт+к всегда является числом Фибоначчи.

24. [НМ20] Вычислите определитель порядка п х п:

/1-1 О О 11-10 0 11-1

О \0

25. \М21] Покажите, что

2-=2 j: (ЧУ

к odd

> 26. [М20] Используя предыдущее упражнение, покажите, что Fd = 5 (по модулю р), если р-нечетное простое число.

27. [М20] Используя предыдущее упражнение, покажите, что если р-простое число, не равное 5, то либо Fp-i, либо Fp+i (но не оба) кратно р.

28. [М21] Чему равно F„+i - фЕп?

► 29. [М23] (Фибономиальные коэффициенты.) Эдуард Люка определил величины

/п\ FnFn-i . Fn-fc+i T-r (Fn-k+j \ \kU FkFk-i...Fi уд Fj J

no аналогии с биномиальными коэффициентами, (а) Составьте таблицу значений (2) для О < к < п < 6. (Ь) Покажите, что () всегда является целым числом, поскольку

> 30. [М38] (Д. Джарден (D. Jarden) и Т. Моцкин (Т. Motzkin).) Последовательность т-х степеней чисел Фибоначчи удовлетворяет рекуррентному соотношению, в котором каждый член зависит от предыдущих m + l членов. Покажите, что

Е(Г1(-1)""""-.=0, еслит>в

Например, при m = 3 получаем тождество Fn - 2Fn+i - 2F+2 + Fn+з = 0.

31. [М20] Покажите, что Е2пф mod 1 = 1- 0"" и F2„+i0 mod 1 = ф~"~\

32. [М24] Остаток от деления одного числа Фибоначчи на другое равен ± число Фибоначчи. Покажите, что по модулю Fn

Ft, если т mod 4 = 0;

(-ly+Fn-r, если m mod 4 = 1;

(-l)Fr, если m mod 4 = 2;

(-l)"++Fn-r, если m mod 4 = 3.

Fmn+r =

- LJ -Id ciijri /ft iinju « -

, (-l)"++Fn-r, если m mod 4 = 33. [HM24] Пусть z = 7г/2 + Ипф. Покажите, что sinnz/sinz = i"F„.

► 34. [М24] (Система чисел Фибоначчи.) Пусть запись к т означает, что к > т + 2. Покажите, что для любого положительного целого п существует единственное представление п = 4- + + F/c,, где fci » fc2 > • > fcr > 0.

35. [M24] (Система фи-чисел.) Рассмотрим действительные числа, записанные с помощью цифр О и 1 по основанию ф (например, (100.1), = ф + ф~). Покажите, что существует бесконечное множество способов такого представления числа 1, например 1 = (.11), = (.011111 ...)ф. Но если потребовать, чтобы две единицы подряд не встречалось и чтобы это представление не заканчивалось бесконечной последовательностью 01010101. .., то для каждого неотрицательного числа будет существовать единственное представление. Каким будет представление для целых чисел?

► 36. [М32] (Строки Фибоначчи.) Пусть Si = "а", S2 = "Ь" и S„+2 = 5n+iS„, n > 0. Другими словами, Sn+2 образуется путем помещения S„ справа от 5n+i. Имеем S3 = "Ьо", S4 = "ЬаЬ", Ss = "babba" и т. д. Очевидно, что в строке Sn содержится Fn букв. Исследуйте свойства Sn. (Где встречаются две буквы подряд? Можете ли вы предсказать, какой будет к-я буква Sn? Какова плотность буквы Ь? И т. д.)

► 37. [М35] (Р. Ю. Гаскел (R. Е. Gaskell) и М. Дж. Виниган (М. J. Whinihan).) Двое играют в следующую игру. Имеется п фишек; первый игрок берет любое количество фишек (но только не все сразу). После этого момента игроки ходят по очереди, причем каждый из них берет одну или несколько фишек, но не более чем двукратное количество фишек, взятых предыдущим игроком. Выигрывает тот, кто заберет последнюю фишку. (Рассмотрим эту игру на конкретном примере. Пусть п = 11. Игрок А взял 3 фишки; значит, игрок В может забрать до б фишек, но он берет 1. Остается 7 фишек. Игрок А может взять 1 или 2 фишки; он берет 2. Теперь игрок В может взять до 4 фишек; он берет 1. Остается 4 фишки. На этот раз игрок А берет 1 фишку; теперь игрок В должен взять по меньшей мере одну фишку, поэтому на следующем ходе игрок А выигрывает.)

Сколько фишек следует взять первому игроку в начале игры, если первоначально имеется 1 ООО фишек?

38. [35] Напишите такую компьютерную программу игры, описанной в предыдущем упражнении, чтобы она велась оптимальным образом.

39. [М24] Найдите выражение в замкнутой форме для Оп при условии, что оо = О, ai = 1 и ап+2 = fln+i + ба„ для п > 0.

40. [М25] Найдите решение рекуррентных соотношений

/(1) = 0; /(п) = min max(l--/(A:),2--/(n-A:)) для n >,1

0<fc<n

► 41. [М25] (Юрий Матиясевич (Yuri Matiyasevich), 1990.) Пусть f(x) = [х + ф~\. Докажите, что если п = Fki -!-• + Fk - это представление числа п в системе чисел Фибоначчи

(см. упр. 34), то Fki+i +----(- Ffc„+i = /(фп). Найдите аналогичную формулу для Fk-i +

+ Fk,-i.

42. [М26] (Д. А. Кларнер (D. А. Klarner).) Покажите, что если m и п - неотрицательные целые числа, то существует единственная последовательность индексов /ti > А;2 »•>• fcr, такая, что

m = Fk,+Fk:, + --- + Fk,., п = Fk,+i + n+i -1- • • Fkr+i-(Заметим, что к могут быть отрицательными, а г - нулем.)