WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 20 | 21 || 23 | 24 |   ...   | 65 |

15.17. Докажите, что любое натуральное число n единственным образом можно представить в виде n = Fk +Fk +...+Fk, где k1 > k2+1, 1 2 m k2 > k3 + 1,..., km-1 > km + 1, km > 1.

15.18. Докажите, что число Фибоначчи с нечётным номером не может делиться на простое число вида 4k + 3.

15.3. Числа Фибоначчи и алгоритм Евклида 15.19. Пусть a и b натуральные числа, причём a > b и НОД(a, b) = = d. Докажите, что если алгоритм Евклида, применённый к a и b, останавливается после n шагов, то a dFn+2 и b dFn+1.

15.20. а) Докажите, что Fn+5 > 10Fn при n 2.

б) Докажите, что если Fn+1 < 10k, то n 5k.

15.21. Докажите, что количество шагов алгоритма Евклида, применённого к паре натуральных чисел a > b, не превосходит количества цифр десятичной записи числа b, умноженного на 5.

15.4. Числа Фибоначчи в комбинаторике 15.22. Чему равно количество подмножеств множества {1, 2, 3,..., n}, не содержащих двух последовательных чисел 15.23. Сколькими способами можно представить число n в виде суммы нескольких слагаемых, равных 1 или 2 (Представления, различающиеся порядком слагаемых, считаются различными.) 15.24. Сколькими способами можно представить число n в виде суммы нескольких целых слагаемых ai 2 (Представления, различающиеся порядком слагаемых, считаются различными.) 15.25. Сколькими способами можно представить число n в виде суммы положительных нечётных слагаемых (Представления, различающиеся порядком слагаемых, считаются различными.) 184 Глава 15. Рекуррентные последовательности 15.5. Специальные рекуррентные последовательности 15.26. Пусть a1 = 1, a2 = 0, a3 = 1 и (n2 + n + 1)(n + 1) n + an+3 = an+2 + (n2 + n + 1)an+1 - an n n при n 1. Докажите, что an квадрат целого числа для любого n 1.

15.27. Пусть u1 = 1, u2 = 0, u3 = 1 и un = un-2 + un-3 при n 4.

Докажите, что u2n - u2 и u2n+1 - u2 делятся на un.

n-1 n+Решения 15.1. В произведении (u1+u2x+u3x2+u4x3+...)(1-a1x-a2x2-...-akxk) коэффициент при xn+k-1, n 1, равен un+k - a1un+k-1 -... - akun = 0.

Значит, это произведение представляет собой многочлен Pk-1(x) степени не выше k - 1.

15.2. Согласно задаче 10.35 можно выбрать числа c1,..., ck так, что u1 = c1 +... + ck, u2 = c1x1 +... + ckxk,......

uk = c1xk-1 +... + ckxk-1.

1 k Тогда c1xk +... + ckxk = c1(a1xk-1 +... + ak) +... + ck(a1xk-1 +... + ak) = 1 k 1 k = a1uk +... + aku1 = uk+1.

Аналогично c1xk+1 +... + ckxk+1 = uk+2 и т.д.

1 k 15.3. Применим индукцию по k. При k = 1 получаем Fn+1 = Fn-1 + Fn, а при k = 2 получаем Fn+2 = Fn-1 + 2Fn = Fn-1 + Fn + Fn = Fn+1 + Fn. База индукции доказана. Предположим теперь, что Fn+k-2 = Fn-1Fk-2 + FnFk-и Fn+k-1 = Fn-1Fk-1 + FnFk. Тогда Fn+k = Fn-1(Fk-2 + Fk-1) + Fn(Fk-1 + + Fk) = Fn-1Fk + FnFk+1.

15.4. а) Предположим, что числа Fn и Fn+1 делятся на целое число d > 1.

Тогда Fn-1 = Fn+1 - Fn тоже делится на d и т.д. В итоге получим, что F2 = делится на d.

б) Воспользуемся формулой Fn+k = Fn-1Fk + FnFk+1 (задача 15.3). Положим m = n + k. При m > k получаем НОД(Fm, Fk) = НОД(Fm-k-1Fk + + Fm-kFk+1, Fk) = НОД(Fm-kFk+1, Fk) = НОД(Fm-k, Fk), поскольку числа Глава 15. Рекуррентные последовательности Fk и Fk+1 взаимно простые. Теперь можно воспользоваться результатом задачи 4.11.

15.5. Число Fn делится на Fm тогда и только тогда, когда НОД(Fn, Fm) = = Fm. С другой стороны, согласно задаче 15.4 НОД(Fn, Fm) = FНОД(n,m). Таким образом, получаем следующее условие: НОД(n, m) = m (здесь мы пользуемся тем, что m > 2). Полученное равенство, в свою очередь, эквивалентно тому, что n делится на m.

15.6. Согласно задаче 15.2 Fn = c1xn + c2xn, где x1 и x2 корни уравне1 ния x2 = x+1, а c1 и c2 некоторые константы. Решая квадратное уравнение, 1 ± получаем x1,2 =. Константы c1 и c2 мы находим, воспользовавшись тем, что F1 = 1 и F2 = 1.

15.7. Формула Бине (задача 15.6) показывает, что n n n n 2n-1Fn = + 5 + 25 + 125 +...

1 3 5 15.8. а) Многочлены f1(x) и f2(x) имеют указанный вид. Поэтому достаточно проверить, что многочлены указанного вида удовлетворяют указанному рекуррентному соотношению. Но если посмотреть на коэффициенты при степенях x по отдельности, то это рекуррентное соотношение сводит n - k ся к основному тождеству для биномиальных коэффициентов: = k n - k - 1 n - k - = +.

k k - б) Непосредственно следует из а), поскольку Fn = fn(1).

15.9. Ясно, что (1-x-x2)(F1 +F2x+F3x2 +F4x3 +...) = F1 +(F2 -F1)x+ + (F3 - F2 - F1)x2 + (F4 - F3 - F2)x3 +... При этом F1 = 1, F2 - F1 = 0, F3 - F2 - F1 = 0, F4 - F3 - F2 = 0,...

15.10. Рассмотрим пары остатков от деления на n соседних чисел Фибоначчи Fk и Fk+1 для k = 1, 2,..., n2 + 1. Количество различных пар остатков равно n2, поэтому среди рассматриваемых пар остатков найдутся две одинаковые пары, т.е. числа Fk - Fl и Fk+1 - Fl+1 делятся на n для некоторых чисел 1 k < l n2 + 1. Тогда число Fk-1 - Fl-1 = Fk+1 - Fl+1 - (Fk - Fl) тоже делится на n и т.д. В конце концов получаем, что числа F2 - Fl-k+2 и F1 - Fl-k+1 делятся на n. Поэтому Fl-k = Fl-k+2 - Fl-k+1 F2 - F1 (mod n).

15.11. Пусть S = Fk+1 + Fk+2 +... + Fk+8 сумма восьми последовательных чисел Фибоначчи. Достаточно доказать, что Fk+9 < S < Fk+10. Первое неравенство очевидно: S > Fk+7 + Fk+8 = Fk+9. Докажем теперь второе нера186 Глава 15. Рекуррентные последовательности венство. Ясно, что Fk+10 = Fk+8 + Fk+9 = = Fk+8 + Fk+7 + Fk+8 = = Fk+6 + Fk+7 + Fk+7 + Fk+8 = = Fk+5 + Fk+6 + Fk+6 + Fk+7 + Fk+8 =......

= Fk+1 + 2Fk+2 + Fk+3 +... + Fk+8.

Последнее выражение, очевидно, больше S.

15.12. Равенство a2 = b2 + ab ± 1 показывает, что a b, причём a = b лишь в том случае, когда оба эти числа равны 1. Поэтому будем считать, что a > b. Для пары b, a - b тоже выполняется требуемое равенство, поскольку b2 - (a - b)b - (a - b)2 = -(a2 - ab - b2). Поэтому после нескольких таких замен мы дойдём до пары (1, 1). Обратное преобразование имеет вид (x, y) (x + y, x), поэтому из пары (1, 1) мы будем последовательно получать пары (Fn+1, Fn) для n = 2, 3,...

15.13. Рассматриваемое уравнение эквивалентно уравнению mn = = (n - m)(n - m + 1). Пусть d = НОД(m, n), n = da и m = После db.

сокращения на d получаем уравнение abd = (a - b) (a - b)d + 1. Число d взаимно просто с (a - b)d + 1, а число ab взаимно просто с a - b, поэтому ab = = (a-b)d+1 и d = a-b. Подставим в первое уравнение выражение a = b+d и заменим a - b на d. В результате получим b2 + bd = d2 + 1, т.е. b2 + bd - d2 = 1.

В задаче 15.12 приведено решение уравнения чуть более общего вида, когда в правой части стоит ±1. Отбросив те решения, которые соответствуют -1, получим d = F2k, b = F2k-1 и a = b + d = F2k+1. Таким образом, n = F2kF2k+и m = F2kF2k-1.

n n - Замечание. Равенство = эквивалентно равенству m - 1 m n - 1 n - 1 n - + =.

m - 1 m - 2 m 15.14. а) Применим индукцию по n. При n = 1 равенство очевидно. Предположим, что доказано равенство F2n+1F2n-1 = F2n + 1 для некоторого n.

2 2 2 Тогда F2n+2 + 1 = (F2n+1 + F2n)2 + 1 = F2n+1 + 2F2n+1F2n + F2n + 1 = F2n+1 + + 2F2n+1F2n + F2n+1F2n-1 = F2n+1(F2n+1 + 2F2n + F2n-1). Остаётся заметить, что F2n+1 + 2F2n + F2n-1 = F2n+2 + F2n+1 = F2n+3.

2 б) Воспользовавшись задачей а), получаем F2n+1 + F2n-1 - 2F2n+1F2n-1 = 2 2 = (F2n+1 - F2n-1)2 = F2n = F2n+1F2n-1 - 1, а значит, F2n+1 + F2n-1 + 1 = = 3F2n+1F2n-1.

15.15. Можно считать, что a b. Согласно задаче 15.14 б) пара чисел (a, b) = (F2n+1, F2n-1), n 1, обладает требуемым свойством; пара чисел (a, b) = (1, 1) тоже. Покажем, что никакие другие пары натуральных чисел Глава 15. Рекуррентные последовательности (a, b), где a b, этим свойством не обладают. Применим индукцию по a.

Прежде всего отметим, что если a = b, то число 2a2 +1 делится на a2, поэтому a = 1. Предположим, что a2 +b2 +1 = kab, где k натуральное число и a > 1.

b2 + Положим a1 = b и b1 = kb - a =. Тогда a2 + b2 + 1 = b2 + k2b2 - 2kab + 1 a + a2 + 1 = k2b2 - kab = kb(kb - a) = ka1b1, поэтому числа (a1, b1) обладают требуемым свойством. Проверим, что 1 b1 a1 < a. Действительно, b1 = b2 + 1 b2 + = < < b + 1. Число b1 целое, поэтому b1 b = a1. Кроме того, a b a1 = b < a по условию. Значит, по предположению индукции b = a1 = F2n+и kb - a = b1 = F2n-1 для некоторого n 0 (мы считаем, что F-= 1). Но в таком случае из равенства a2 + b2 + 1 = kab следует, что k = 3, поэтому a = kb - b1 = 3F2n+1 - F2n-1 = 2F2n+1 + F2n+1 - F2n-1 = F2n+1 + F2n+1 + + F2n = F2n+1 + F2n+2 = F2n+3.

2 15.16. Формула F2n+1 + F2n-1 + 1 = 3F2n+1F2n-1 из задачи 15.14 б) показывает, что пара (F2n-1, F2n+1) обладает требуемым свойством. Покажем, что никакая другая пара натуральных чисел (a, b), где a b, этим свойством не обладает. Применим индукцию по b. Прежде всего заметим, что если a = b, то a2 +1 делится на a, поэтому a = b = 1. Пусть b > 1, a b, a2 +1 = b и b2+ +1 = µa, где и µ целые числа. Тогда (a2+1)2 = 2b2 = 2(µa-1), поэтому 1 -2 (mod a), т.е. 2 + 1 делится на a. Кроме того, ab a(a + 1) a2 + 1, поэтому a < b. Воспользовавшись предположением индукции, получим 2 F2n+1 + 1 3F2n+1F2n-1 - F2n- = F2n-1 и a = F2n-1. Значит, b = = = F2n-1 F2n-= 3F2n+1 - F2n-1 = F2n+1.

15.17. В качестве Fk1 выберем наибольшее число Фибоначчи, не превосходящее n, т.е. Fk1 n < Fk1+1. Тогда 0 n - Fk1 < Fk1+1 - Fk1 = Fk1-.

Поэтому если в качестве Fk2 мы выберем наибольшее число Фибоначчи, не превосходящее n - Fk1, то Fk2 < Fk1-, т.е. k2 + 1 < k1. Затем выбираем наибольшее число Фибоначчи, не превосходящее n - Fk1 - Fk2, и т.д.

Единственность представления следует из того, что Fk1 n < Fk1+1.

Действительно, Fk1 + Fk2 +... + Fkm Fk1 + Fk1-+ Fk2-+...; последнее слагаемое в этой сумме равно F3 при нечётном k1 и F2 при чётном k1. Заменим F3 на F4 - 1, а F2 на F3 - 1. После этой замены сумма легко сворачивается и получается Fk1+1 - 1.

15.18. Положим в задаче 15.3 k = n - 1. В результате получим F2n-1 = 2 = Fn-1 + Fn. Поэтому если F2n-1 делится на простое число p вида 4k + 3, то оба числа Fn-1 и Fn делятся на p (задача 31.2). В таком случае число Fn-2 = = Fn - Fn-1 тоже делится на p и т.д. Приходим к противоречию, поскольку F1 = 1 не делится на p.

15.19. Применим индукцию по n. Если n = 1, то b = d = dF2 и a 2d = = dF3. Предположим, что требуемое утверждение доказано для некоторого n 1. Рассмотрим числа a > b, для которых алгоритм Евклида останавливается после n + 1 шагов. На первом шаге пара (a, b) заменяется на пару 188 Глава 15. Рекуррентные последовательности (b, c), где c = a - qb a - b. Для пары (b, c) алгоритм Евклида останавливается после n шагов, причём НОД(b, c) = НОД(a, b) = d. Поэтому согласно предположению индукции b dFn+2 и c dFn+1. Следовательно, a b + + c d(Fn+2 + Fn+1) = dFn+3.

15.20. а) При n = 2 и 3 требуемое неравенство легко проверяется, поэтому будем считать, что n > 3. Воспользуемся тождеством из задачи 15.3: Fn+5 = = F(n-2)+7 = Fn-3F7 + Fn-2F8 = 13Fn-3 + 21Fn-2 > 10Fn-3 + 20Fn-2 = 10Fn.

б) Применим индукцию по k. При k = 1 достаточно заметить, что F7 = = 13 > 10. Предположим, что для данного k 1 мы уже доказали, что из неравенства Fn+1 < 10k следует неравенство n 5k. Пусть Fm+1 < 10k+1.

Тогда согласно задаче а) 10Fm-4 < Fm+1 < 10k+1, поэтому F(m-5)+1 < 10k.

Следовательно, согласно предположению индукции m-5 5k, т.е. m 5(k + + 1), что и требовалось.

15.21. Пусть алгоритм Евклида, применённый к паре (a, b), останавливается после n шагов. Тогда согласно задаче 15.19 b Fn+1.

Если количество цифр в десятичной записи числа b равно k, то b < 10k, поэтому Fn+1 < 10k. Остаётся воспользоваться результатом задачи 15.20.

15.22. О т в е т: Fn+2. Пусть искомое число равно xn. При n = 1 есть подмножества и {1}, поэтому x1 = 2. При n = 2 есть подмножества, {1} и {2}, поэтому x2 = 3. Легко проверить, что xn = xn-1 + xn-2 при n 3.

Действительно, если рассматриваемое подмножество содержит n, то оно не содержит n - 1, и никаких других ограничений на него не накладывается.

Количество таких подмножеств равно xn-2. Ясно также, что количество рассматриваемых подмножеств, не содержащих n, равно xn-1.

15.23. О т в е т: Fn+1. Пусть искомое число равно xn. Ясно, что x1 = 1 и x2 = 2. Докажем, что xn = xn-1 + xn-2 при n 3. Действительно, количество представлений числа n с первым слагаемым 1 равно xn-1, а с первым слагаемым 2 xn-2.

15.24. О т в е т: Fn-1. Пусть искомое число равно xn. Ясно, что x1 = 0, x2 = 1 и x3 = 1. Докажем, что xn = xn-1 + xn-2 при n 3. Первое слагаемое может быть равно 2; количество таких представлений равно xn-2. Первое слагаемое может быть больше 2. Тогда из него можно вычесть 1 и получить представление числа n - 1. Поэтому количество таких представлений равно xn-1.

15.25. О т в е т: Fn. Пусть искомое число равно xn. Ясно, что x1 = 1 и x2 = = 1. Докажем, что xn = xn-1 + xn-2 при n 3. Действительно, количество представлений с первым слагаемым 1 равно xn-1. Если же первое слагаемое не меньше 3, то из него можно вычесть 2 и получить представление числа n - 2.

15.26. Рассмотрим последовательность bn, для которой b1 = 1, b2 = 0 и bn+2 = nbn+1+bn при n 1. Возведём в квадрат равенства bn = bn+2-nbn+1 и bn+3 = (n + 1)bn+2 + bn+1. Затем, чтобы уничтожить член bn+2bn+1, умножим Глава 15. Рекуррентные последовательности первое из полученных равенств на n+1, второе на n и сложим их. В результате получим (n2 + n + 1)(n + 1) n + b2 = b2 + (n2 + n + 1)b2 - b2.

n+3 n+2 n+1 n n n Кроме того, b3 = 1. Значит, an = b2.

n 15.27. Проверим, что при 0 < k < m - 2 имеет место равенство um = uk+1um-k + uk+2um-k-1 + ukum-k-2. (1) При k = 1 это равенство очевидно. Поэтому достаточно доказать, что uk+1um-k + uk+2um-k-1 + ukum-k-2 = uk+2um-k-1 + uk+3um-k-2 + + uk+1um-k-3. Сократим члены uk+2um-k-1 в обеих частях этого равенства и воспользуемся тем, что uk+1um-k = uk+1um-k-2 + uk+1um-k-3. После сокращения членов uk+1um-k-3, приходим к очевидному равенству (uk+1 + + uk)um-k-2 = uk+3um-k-2.

Положив в равенстве (1) m = 2n и k = n - 1, получим u2n - u2 = n-= 2unun+1. Положив в равенстве (1) m = 2n + 1 и k = n - 1, получим u2n+1 - u2 = un(un-1 + un+2).

n+Глава 16.

Примеры и конструкции 16.1. Наборы чисел 16.1. Можно ли выбрать 10 натуральных чисел так, чтобы ни одно из них не делилось ни на какое другое, но квадрат любого числа делился бы на каждое из чисел 16.2. а) Докажите, что существует бесконечно много пар натуральных чисел k, l 2, для которых k!l! = n! для некоторого натурального n.

б) Докажите, что для каждого натурального числа m существует бесконечно много наборов натуральных чисел a1,..., am 2, для которых a1!a2!... am! = n! для некоторого n.

16.3. Докажите, что для любого натурального n существуют n различных натуральных чисел, сумма любых двух из которых делится на их разность.

Pages:     | 1 |   ...   | 20 | 21 || 23 | 24 |   ...   | 65 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.