Книги по разным темам Pages:     | 1 |   ...   | 16 | 17 | 18 | 19 | 20 |   ...   | 30 |

Определение. Пусть {an} = a0, a1,... Ч произвольная числовая последовательность. Формальный степенной ряд F(x) = a0 + a1x +... + anxn +...

3. Производящие функции будем называть производящей функцией этой последовательности.

11.63. Пусть F(x) Ч производящая функция последовательности {an}.

F(n)(x) Докажите равенство an =.

n! x=11.63. Докажите, что для нечётных p выполняется равенство 5 Fnp Fn(Up-1( )) =, 2 Fp например, F3n Fn(4) = (p = 3);

FF5n Fn(11) = (p = 5);

FF7n Fn(29) = (p = 7).

F11.64. Вычислите производящие функции следующих последовательностей:

а) an = n; б) an = n2; в) an = Cn.

m 11.65. Вычислите суммы:

а) C1 + 2C2 + 3C3 +... + nCn; б) C1 + 22C2 + 32C3 +... + n2Cn.

n n n n n n n n 11.66. Пусть an Ч число решений уравнения x1 +... + xk = n (11.6) в целых неотрицательных числах и F(x) Ч производящая функция последовательности an. Докажите равенства:

а) F(x) = (1 + x + x2 +... )k; б) F(x) = (1 - x)-k.

11.67. Пусть, как и раньше, an Ч число решений уравнения (11.6) в целых неотрицательных числах. Найдите формулу для an, пользуясь задачей 11.63. (См. также 2.70.) 11.68. Докажите тождество:

(1 + x + x2 +... + x9)(1 + x10 + x20 +... + x90) (1 + x100 + x200 +... + x900)... =.

1 - x (См. также 1.2.) 11.69. Бином Ньютона для отрицательных показателей.

Докажите, что для всех неотрицательных n выполняются равенства а) Ck = (-1)kCk ; б) (1 + x)-n = Ck xk.

-n n+k-1 -n k=162 11. Последовательности и ряды 11.70. Вычислите производящие функции следующих последовательностей:

а) an = Cm ; б) an = Cm.

m+n n 11.71. Счастливые билеты. Предположим, что у нас имеется 1 000 000 автобусных билетов с номерами от 000 000 до 999 999. Будем называть билет счастливым, если сумма первых трех цифр его номера равна сумме трех последних. Пусть N Ч количество счастливых билетов. Докажите равенства:

а) (1 + x +... + x9)3(1 + x-1 +... + x-9)3 = x27 +... + a1x + N + + a-1x-1 +... + x-27;

б) (1 + x +... + x9)6 = 1 +... + Nx27 +... + x54.

11.72. Найдите число счастливых билетов.

Определение. Назовем экспонентой степенной ряд z2 zn zk Exp(z) = 1 + z + +... + +... =.

2! n! k! k=11.73. Докажите следующие свойства экспоненты:

а) Exp (z) = Exp(z); б) Exp(( + )z) = Exp(z) Exp(z).

(См. также 7.52.) 11.74. Функции a, b и c заданы рядами a = 1 + C3 x3 + C6 x6 +..., n n b = C1 x + C4 x4 + C7 x7 +..., n n n c = C2 x2 + C5 x5 + C8 x8 +....

n n n Докажите, что a3 + b3 + c3 - 3abc = (1 + x3)n.

(См. также 9.8.) 11.75. Докажите, что производящая функцияпоследовательности чисел Фибоначчи F(z) = F0 + F1z + F2z2 +... + Fnzn +...

может быть записана в виде z 1 1 F(z) = = -, 1 - z 1 - z 1 - z - z2 1 + 5 1 - где =, =. Пользуясь результатом задачи 11.63, 2 получите формулу Бине. (См. также 3.126 и 11.43.) 3. Производящие функции 11.76. Докажите, что бесконечная сумма 0,1 + 0,01 + 0,002 + 0,0003 + 0,00005 + 0,000008 + 0,0000013 +...

сходится к рациональному числу.

11.77. Найдите производящую функцию последовательности чисел Люка L(z) = L0 + L1z + L2z2 +... + Lnzn +....

Пользуясь этой функцией, выразите Ln в замкнутой форме через и. (См. также 3.135.) 11.78. Вычислите суммы Fn Ln а) ; б).

2n 2n n=0 n=11.79. Производящие функции многочленов Фибоначчи и Люка. Найдите производящие функции последовательности многочленов Фибоначчи F(x, z) = F0(x) + F1(x)z + F2(x)z2 +... + Fn(x)zn +...

и последовательности многочленов Люка L(x, z) = L0(x) + L1(x)z + L2(x)z2 +... + Ln(x)zn +...

11.80. Производящие функции многочленов Чебышёва. Найдите производящие функции последовательностей многочленов Чебышёва первого и второго рода (см. 7.38):

FT (x, z) = Tn(x)zn, FU(x, z) = Un(x)zn.

n=0 n=11.81. Вычислите, используя производящие функции, следующие суммы:

n-1 n- а) 2kxk; в) k22k;

k=0 k=n-1 n- б) k 2k; г) k sin kx.

k=0 k=11.81. Найдите произвольную функцию линейной рекуррентной последовательности второго порядка (11.2) с начальными членами a0 и a1.

Определение. Разбиением называется представление натурального числа в виде суммы натуральных слагаемых. Порядок слагаемых 164 11. Последовательности и ряды считается несущественным. Например, разбиения 3 = 1 + 2 и 3 = 2 + не различаются.

11.82. Пусть p(n) Ч количество разбиений числа n. Докажите равенства:

p(0) + p(1)x + p(2)x2... = (1 + x + x2 +... )... (1 + xk + x2k +... )... = = (1 - x)-1(1 - x2)-1(1 - x3)-1...

(По определению считается, что p(0) = 1.) 11.83. На доске написано n натуральных чисел. Пусть ak Ч количество тех из них, которые больше k. Исходные числа стерли и вместо них написали все положительные ak. Докажите, что если с новыми числами сделать то же самое, то на доске окажется исходный набор чисел. Например, для чисел 5, 3, 3, 2, получается следующая цепочка (5, 3, 3, 2) (4, 4, 3, 1, 1) (5, 3, 3, 2).

11.84. Докажите, что каждое целое положительное число n может быть 2n-1 - 1 различными способами представлено в виде суммы меньших целых положительных слагаемых, если два представления, отличающихся хотя бы порядком слагаемых, считать различными. Например, лишь 24-1 - 1 = 7 следующих сумм имеют значение 4:

1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2, 1 + 3, 3 + 1.

11.85. Каждое положительное число n можно представить в виде суммы различных слагаемых, причем это можно сделать столькими же способами, сколькими способами это же число представимо в виде суммы различных слагаемых. Например, все возможные представления числа 6 посредством различных слагаемых будут:

6, 1 + 5, 2 + 4, 1 + 2 + 3, посредством нечетных:

1 + 5, 3 + 3, 1 + 1 + 1 + 3, 1 + 1 + 1 + 1 + 1 + 1.

Для доказательства этого факта обозначим через d(n) количество разбиений числа n на различные слагаемые, а через l(n) Ч на нечетные.

Установите равенства:

а) d(0) + d(1)x + d(2)x2 +... = (1 + x)(1 + x2)(1 + x3)... ;

б) l(0) + l(1)x + l(2)x2 +... = (1 - x)-1(1 - x3)-1(1 - x5)-1... ;

в) d(n) = l(n) (n = 0, 1, 2,... ).

(Считается по определению, что d(0) = l(0) = 1.) 3. Производящие функции 11.86*. Придумайте какое-либо взаимно однозначное соответствие между разбиениями натурального числа на различные и на нечетные слагаемые. В этом могут помочь диаграммы Юнга, уже упоминавшиеся в разделе 4, с. 148.

11.87. Определите коэффициент an в разложении (1+qx)(1+qx2)(1+qx4)(1+qx8)(1+qx16)... = a0+a1x+a2x2+a3x3+...

(См. также 5.64.) 11.88. Каков знак n-го члена в разложении произведения (1 - a)(1 - b)(1 - c)(1 - d)... = = 1 - a - b + ab - c + ac + bc - abc - d +... (n = 0, 1, 2,... ) (См. также 5.73.) 11.89. Найдите общую формулу для коэффициентов ряда (1 - 4x)- = 1 + 2x + 6x2 + 20x3 +... + anxn +...

11.90. Переменные x и y связаны равенством x = y + y2 + y3 +... + yn +...

Разложите y по степеням x.

11.91. Переменные x и y связаны равенством y2 y3 yn x = y + + +... + +...

2! 3! n! Разложите y по степеням x.

11.92. Пусть C(z) = Cnzn Ч производящая функция последоn=вательности чисел Каталана {Cn}. Докажите, что она удовлетворяет равенству C(z) = zC2(z) + 1, и получите явный вид функции C(z). (См. также 2.116.) 11.93. Выведите формулы для чисел Каталана из задачи 2.115, воспользовавшись результатом предыдущей задачи и равенством (1 - z)1/2 = Cn (-z)n, 1/n=где (1/2)(1/2 - 1)... (1/2 - n + 1) Cn = 1/n! Ч обобщенные биномиальные коэффициенты (смотрите определение на с. 154).

166 11. Последовательности и ряды 4. Многочлены Гаусса Определение. Для целых неотрицательных k и l определим функции gk,l(x) равенством (1 - xl+1)(1 - xl+2)... (1 - xl+k) gk,l(x) =.

(1 - x)(1 - x2)... (1 - xk) 11.94. Вычислите функции gk,l(x) при 0 k + l 4 и покажите, что все они являются многочленами.

11.95. Докажите следующие свойства функций gk,l(x):

hk+l(x) а) gk,l(x) =, hk(x) hl(x) где hm(x) = (1 - x)(1 - x2)... (1 - xm) (h0(x) = 1);

б) gk,l(x) = gl,k(x);

в) gk,l(x) = gk-1,l(x) + xkgk,l-1(x) = gk,l-1(x) + xlgk-1,l(x);

г) gk,l+1(x) = g0,l(x) + xg1,l(x) +... + xkgk,l(x);

д) gk,l(x) Ч многочлен относительно x степени kl.

Многочлены gk,l(x) называются многочленами Гаусса. Их свойства во многом аналогичны свойствам биномиальных коэффициентов.

В частности, среди многочленов они играют ту же роль, что и биномиальные коэффициенты среди чисел.

11.96. Определение функций gk,l(x) не позволяет вычислять их значения при x = 1. Но, поскольку функции gk,l(x) являются многочленами, они определены и при x = 1. Докажите равенство gk,l(1) = Ck. Каk+l кие свойства биномиальных коэффициентов получаются, если в свойства б) - г) из задачи 11.95 подставить значение x = 1 11.97. Найдите сумму Sl(x) = g0,l(x) - g1,l-1(x) + g2,l-2(x) -... + (-1)lgl,0(x).

11.98. Обозначим через Pk,l(n) количество разбиений числа n на не более чем k слагаемых, каждое из которых не превосходит l. Докажите равенства:

а) Pk,l(n) - Pk,l-1(n) = Pk-1,l(n - l);

б) Pk,l(n) - Pk-1,l(n) = Pk,l-1(n - k);

в) Pk,l(n) = Pl,k(n);

г) Pk,l(n) = Pl,k(kl - n).

11.99. Пусть fk,l(x) Ч производящая функция последовательности Pk,l(n):

fk,l(x) = Pk,l(0) + xPk,l(1) +... + xklPk,l(kl).

4. Многочлены Гаусса а) Докажите равенства:

fk,l(x) = fk-1,l(x) + xkfk,l-1(x) = fk,l-1(x) + xlfk-1,l(x).

б) Докажите, что функции fk,l(x) совпадают с многочленами Гаусса gk,l(x).

11.100. Докажите, что при любых k и l многочлен gk,l(x) является возвратным, то есть xklgk,l(1/x) = gk,l(x). Решите задачу двумя способами: пользуясь определением многочленов Гаусса и при помощи свойств чисел Pk,l(n) из задачи 11.98.

11.101. Докажите, что Pkl(0) + Pkl(1) + Pkl(2) +... + Pkl(kl) = Ck, k+l не используя свойства многочленов Гаусса.

Глава Шутки и ошибки 12.1. Ученик Коля Васин при помощи метода математической индукции смог доказать, что в любом табуне все лошади одной масти.

Если есть только одна лошадь, то она своей масти, так что база индукции верна. Для индуктивного перехода предположим, что есть n лошадей (с номерами от 1 до n). По индуктивному предположению лошади с номерами от 1 до n-1 одинаковой масти. Аналогично лошади с номерами от 2 до n также имеют одинаковую масть. Но лошади с номерами от 2 до n - 1 не могут менять свою масть в зависимости от того как они сгруппированы Ч это лошади, а не хамелеоны. Поэтому все n лошадей должны быть одинаковой масти.

Есть ли ошибка в этом рассуждении, и если есть, то какая (См.

также 1.4.) 12.2. Иногда вычитая дроби можно вычитать их числители и складывать знаменатели. Например:

9 - 25 9 25 8 - 50 8 = - ; = -.

6 + 10 6 10 2 + 5 2 Для каких дробей это возможно 12.3. Найдите все дроби с числителем и знаменателем не превосходящими 100, в которых можно проводить сокращение на равные цифры.

Примером может служить равенство 1 6 =.

64 12.4. Легко проверить равенства 16 16 64 log 16 + = log 16 + log ; log - 8 = log - log 8.

15 15 7 В каких еще случаях можно выносить логарифм за скобку 12.5. При каких значениях a и b возможно равенство sin a + sin b = sin(a + b) 12.6. Квадраты двух зеркальных чисел 12 и 21 также являются зеркальными числами (144 и 441). Какие двузначные числа обладают аналогичным свойством И дополнительный вопрос: в каких системах счисления число 441 будет полным квадратом 12.7. Черная пятница. Докажите, что тринадцатое число месяца с большей вероятностью приходится на пятницу, чем на другие дни недели. Предполагается, что мы живем по Григорианскому стилю (см.

3.153).

12.8. Коля Васин, решая задачу, получил в ответе шестизначное число. А потом он подумал, что это произведение двух трехзначных чисел и выполнил умножение. Каким был первоначальный ответ, если второй ответ оказался в три раза меньше 12.9. Восстановите алфавит племени Мумбо-Юмбо из задачи 2.6.

12.10. Найдите коэффициент при x у многочлена (x - a)(x - b)(x - c)... (x - z).

12.11. л1 = -1. Изучив комплексные числа, Коля Васин решил вывести формулу, которая носила бы его имя. После нескольких попыток ему это удалось:

1 -1 1 - = = 1 1 = -1 -1 1 = -1.

-1 1 -1 После некоторых размышлений, Коля придумал более короткое доказательство своего тождества:

-1 = i2 = -1 -1 = (-1)(-1) = 1 = 1.

Не ошибся ли где-нибудь Коля Васин (См. также 7.24.) 12.12. После экспериментов с мнимой единицей, Коля Васин занялся комплексной экспонентой. Пользуясь формулами задачи 7.51, он смог доказать, что sin x всегда равен нулю, а cos x Ч единице:

eix - e-ix (e2i)x/(2) - (e-2i)x/(2) - sin x = = = = 0;

2i 2i 2i eix + e-ix (e2i)x/(2) + (e-2i)x/(2) 1 + cos x = = = = 1.

2 2 Где ошибка в приведенных равенствах (См. также 7.55.) 12.13. л65 = 64 = 63. Тождество Кассини лежит в основе одного геометрического парадокса. Он заключается в том, что можно взять 170 12. Шутки и ошибки шахматную доску, разрезать ее на четыре части, как показано ниже, а затем составить из этих же частей прямоугольник:

Как расположить те же четыре части шахматной доски, чтобы доказать равенство л64 = 63 (См. также 3.112.) 12.14. Из километров Ч в мили. В задаче 3.125 была введена фибоначчиева система счисления. Она оказывается удобной, когда нужно сделать перевод расстояния из километров в мили или наоборот.

Предположим, что мы хотим узнать, сколько миль в 30 километрах.

Для этого представляем число 30 в фибоначчиевой системе счисления:

30 = 21 + 8 + 1 = F8 + F6 + F2 = (1010001)F.

Теперь нужно сдвинуть каждое число на одну позицию вправо, получая F7 + F5 + F1 = 13 + 5 + 1 = 19 = (101001)F.

Поэтому предполагаемый результат Ч 19 миль. (Правильный ответ Ч около 18,46 миль.) Аналогично делается перевод из миль в километры.

Объясните, почему работает такой алгоритм. Проверьте, что он дает округленное число миль в n километрах при всех n 100, отличающееся от правильного ответа меньше чем на 2/3 мили.

12.15. Обозначим через S сумму следующего ряда:

S = 1 - 1 + 1 - 1 + 1 -... (12.1) Преобразовав равенство (12.1), можно получить уравнение, из которого находится S:

S = 1 - (1 - 1 + 1 - 1 +... ) = 1 - S S =.

Сумму S можно также найти объединяя слагаемые ряда (12.1) в пары:

S = (1 - 1) + (1 - 1) +... = 0 + 0 +... = 0;

S = 1 - (1 - 1) - (1 - 1) -... = 1 - 0 - 0 -... = 1.

Наконец, переставив местами соседние слагаемые, получаем еще одно значение S:

S = -1 + 1 - 1 + 1 - 1 +... = -1 + (1 - 1) + (1 - 1) +... = -1.

Итак, действуя четырьмя разными способами, мы нашли четыре значения суммы S:

S = = 0 = 1 = -1.

Pages:     | 1 |   ...   | 16 | 17 | 18 | 19 | 20 |   ...   | 30 |    Книги по разным темам