<<

стр. 5
(всего 9)

СОДЕРЖАНИЕ

>>

=µ , .
?(a, b) ba
136 9. Уравнения и системы

9.75. Найдите все действительные решения системы
?
? 1 ? x2 = x 2 ,
?
? 1
?
? 1 ? x2 = x 3 ,
?
? 2

..........
?
?
? 1 ? x2 = x n ,
?
?
? n?1
?
1 ? x2 = x1 .
n

9.76. Найдите с точностью до 0,01 сотый член x100 последователь-
ности {xn }, если
а) x1 ? [0; 1], xn+1 = xn (1 ? xn ), (n > 1);
б) x1 ? [0,1; 0,9], xn+1 = 2xn (1 ? xn ), (n > 1).
9.77. Докажите, что касательная к графику функции f(x), постро-
енная в точке с координатами (x0 ; f(x0 )) пересекает ось Ox в точке с
координатой
f(x0 )
x0 ? .
f (x0 )

9.78. Метод Ньютона. Для приближенного нахождения корней
уравнения f(x) = 0 Ньютон предложил искать последовательные при-
ближения по формуле
f(xn )
xn+1 = xn ? ,
f (xn )

(начальное условие x0 следует выбирать поближе к искомому корню).
Докажите, что для функции f(x) = x2 ? k и начального условия
v
x0 > 0 итерационный процесс всегда будет сходиться к k, то есть
v
lim xn = k.
n>?
Как будет выражаться xn+1 через xn ? Сравните результат с форму-
лой из задачи 9.48.
9.79. Метод Ньютона и числа Фибоначчи. Применим метод
Ньютона для приближенного нахождения корней многочлена
f(x) = x2 ? x ? 1.
Какие последовательности чисел получатся, если
а) x0 = 1; б) x0 = 0?
К каким числам будут сходиться эти последовательности? Опишите
разложения чисел xn в цепные дроби.
9.80. Пусть p и q — отличные от нуля действительные числа и
2
p ? 4q > 0. Докажите, что следующие последовательности сходятся:
3. Итерации 137

q
а) y0 = 0, (n
yn+1 = 0);
p ? yn
q
б) z0 = 0, zn+1 (n 0).
=p?
zn
Установите связь между предельными значениями этих последова-
тельностей y? , z? и корнями уравнения x2 ? px + q = 0.
9.81. Метод Ньютона и цепные дроби. Предположим, что цеп-
ные дроби
q q
и
?=p? ?=
q q
p? p?
q q
p? p?
... ...
сходятся. Согласно задаче 9.80, они будут сходиться к корням многочле-
на x2 ? px + q = 0. С другой стороны к тем же корням будут сходиться
и последовательности, построенные по методу Ньютона:
x2 ? pxn + q x2 ? q
n
=n
xn+1 = xn ? .
2xn ? p 2xn ? p
Докажите, что если x0 совпадает с нулевой подходящей дробью цепной
дроби ? или ?, то числа x1 , x2 , . . . также будут совпадать с подходя-
щими дробями к ? или ?. (См. также 9.65.)
9.82. Метод Ньютона не всегда позволяет приблизиться к корню
уравнения f(x) = 0. Для многочлена f(x) = x(x ? 1)(x + 1) найдите
начальное условие x0 такое, что f(x0 ) = x0 и x2 = x0 .
9.83. Метод Лобачевского. Пусть многочлен

P(x) = xn + an?1 xn?1 + . . . + a1 x + a0

имеет корни x1 , x2 , . . . , xn , причем |x1 | > |x2 | > . . . > |xn |. В задаче 6.42
был предъявлен способ построения многочлена Q(x) степени n, корнями
которого являются числа x2 , x2 , . . . , x2 . На основе этого рассужде-
1 2 n
ния Лобачевский придумал метод для приближенного поиска корней
многочлена P(x). Он заключается в следующем. Строится последова-
тельность многочленов P0 (x), P1 (x), P2 (x), . . . такая, что P0 (x) = P(x) и
k k
многочлен Pk (x) имеет корни x2 , . . . , x2 . Пусть
1 n

Pk (x) = xn + a(k) xn?1 + . . . + a1 x + a0 .
(k) (k)
n?1

Докажите, что
1/2k
(k)
an?l
(k) 1/2k
а) lim (?a = x1 ; б) lim (1
) ? = xl l n).
n?1 (k)
an?l+1
k>? k>?
138 9. Уравнения и системы

9.84. Метод Лобачевского и числа Люка. Постройте последо-
вательность полиномов, которая получается, если метод Лобачевского
применить для приближенного нахождения корней многочлена x2 ?x?1.
Какие последовательности будут сходиться к корням x1 и x2 , если
|x1 | > |x2 |?
9.85. Метод Архимеда. Для приближенного нахождения числа ?
рассмотрим окружность радиуса 1/2. Опишем около нее и впишем в
нее правильные n-угольники. Обозначим их периметры через Pn (для
описанного) и pn (для вписанного).
а) Найдите P4 , p4 , P6 и p6 .
б) Докажите, что справедливы следующие рекуррентные соотноше-
ния:
2Pn pn
P2n = , p2n = pn P2n (n 3).
Pn + pn
в) Найдите P96 и p96 . Докажите неравенства
10 1
3 <?<3 .
71 3
9.86. Формула Ферма. Докажите равенство

2 1 1 1 1 1 1 1 1 1
· ·
= + + + ...
? 2 2 2 2 2 2 2 2 2

9.87. Последовательность чисел x0 , x1 , x2 , . . . задается условиями
xn+1 = axn (n
x0 = 1, 0).
Найдите наибольшее число a, для которого эта последовательность име-
ет предел. Чему равен этот предел для такого a?
9.88. Последовательность чисел a1 , a2 , a3 , . . . задается условиями
1
(n
a1 = 1, an+1 = an + 0).
a2
n

Докажите, что
а) эта последовательность неограничена;
б) a9000 > 30;
a
в) найдите предел lim vn .
3
n
n>?
*
9.89 . Тройки чисел (xn , yn , zn ) (n 1) строятся по правилу:
6
x1 = 2, y1 = 4, z1 = ,
7
2xn 2yn 2zn
(n
xn+1 = , yn+1 = , zn+1 = 1).
x2 y2 z2
?1 ?1 ?1
n n n
4. Системы линейных уравнений 139

а) Докажите, что указанный процесс построения троек может быть
неограниченно продолжен.
б) Может ли на некотором шаге получится тройка чисел (xn , yn , zn ),
для которой xn + yn + zn = 0?

4. Системы линейных уравнений
9.90. Коля Васин гулял после школы пять часов. Сначала он шел
по горизонтальной дороге, затем поднялся в гору и, наконец, по старо-
му маршруту возвратился назад в исходный пункт. Его скорость бы-
ла 4 км/ч на горизонтальном участке пути, 3 км/ч при подъеме в
гору и 6 км/ч — при спуске с горы. Какое расстояние прошел Коля
Васин?
Метод Гаусса. Предположим, что имеется система из n линейных
уравнений от переменных x1 , . . . , xn . Одним из возможных методов ре-
шения такой системы является метод Гаусса. Он заключается в том, что
с помощью первого уравнения переменная x1 исключается из остальных
уравнений. Затем с помощью нового второго уравнения переменная
x2 исключается из всех следующих уравнений. И так далее, пока из
последнего уравнения не получится значение последней переменной.
После чего остальные переменные находятся в обратном порядке.
9.91. Решите системы
? ?
? x ? 3y + 2z ? t = 3, ? x + 2y + 3z = 2,
? ?
? ?
2x + 4y ? 3z + t = 5, x ? y + z = 0,
а) в)
? 4x ? 2y + z + t = 3, ? x + 3y ? z = ?2,
? ?
? ?
3x + y + z ? 2t = 10; 3x + 4y + 3z = 0;
? ?
? x + 2y + 3z ? t = 0, ? x + 2y + 3z ? t = 0,
? ?
? ?
x ? y + z + 2t = 4, x ? y + z + 2t = 4,
б) г)
? x + 5y + 5z ? 4t = ?4, ? x + 5y + 5z ? 4t = ?4,
? ?
? ?
x + 8y + 7z ? 7t = ?8; x + 8y + 7z ? 7t = 6.
9.92. На рисунках изображены разбиения прямоугольников на квад-
раты. Найдите стороны этих квадратов, если в первом случае сторона
наименьшего квадрата равна 1, а во втором — 2.




а) б)
140 9. Уравнения и системы

9.93. За круглым столом сидят 4 гнома. Перед каждым стоит круж-
ка с молоком. Один из гномов переливает 1/4 своего молока соседу
справа. Затем сосед справа делает то же самое. Затем то же самое
делает следующий сосед справа и, наконец, четвертый гном 1/4 ока-
завшегося у него молока наливает первому. Во всех кружках вместе
молока 2л. Сколько молока было первоначально в кружках, если
а) в конце у всех гномов молока оказалось поровну? б) в конце у
всех гномов оказалось молока столько, сколько было в начале?

9.94. Решите системы уравнений. Для каждой из них выясните, при
каких значениях параметров система не имеет решений, а при каких
имеет бесконечно много решений.
ax + y = a2 , ax + y = a3 ,
а) д)
x + ay = 1; x + ay = 1;
ax + ay = a2 , ax ? ay = ab,
б) е)
x + ay = 2; 2ax ? y = a;
(a + 1)x + 8y = 4a, ax + by = a,
в) ж)
ax + (a + 3)y = 3a ? 1; bx + ay = b;
|a|x ? y = 1,
a2 x + (2 ? a)y = 4 + a2 ,
г) з)
x + |a|y = a.
ax + (2a ? 1)y = a5 ? 2;

9.95. Может ли система линейных уравнений с действительными
коэффициентами иметь в точности два различных решения?

9.96. Составьте систему, состоящую из двух линейных уравнений,
для которой строки (1, 1, 1, 1) и (1, 2, 2, 1) служат решениями.

9.97. Имеется система уравнений

?
? ?x + ?y + ?z = 0,
?x + ?y + ?z = 0,
?
?x + ?y + ?z = 0.


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

9.98. Исследуйте системы уравнений:
4. Системы линейных уравнений 141
? ? 2 3
? 2x + 3y = 5, ? x + ay + a z = a ,
г) x + by + b2 z = b3 ,
а) x ? y = 2,
? ?
x + cy + c2 z = c3 ;
x + 4y = a;
? ?
? x + ay = 1, ? x + y + z = 1,
б) 2x + 4y = 2, д) ax + by + cz = d,
? ?2
a x + b2 y + c2 z = d2 ;
bx + 4y = 2;
? ?
? ax + by = a, ? ax + by + cz = a + b + c,
в) (a ? 2)x + y = 3, е) bx + cy + az = a + b + c,
? ?
x + y = 1; cx + ay + bz = a + b + c.
9.99. Решите системы уравнений:
?
?
? x1 + x2 + x3 = 0,
?
? ? x1 + x2 + x3 + x4 = 2a1 ,
? x2 + x3 + x4 = 0, ?
? ? x + x ? x ? x = 2a ,
1 2 3 4 2
.............
а) в)
? x + x + x = 0, ? x1 ? x2 + x3 ? x4 = 2a3 ,
? 99 ?
? ?
? 100 1
? x1 ? x2 ? x3 + x4 = 2a4 ;
x + x1 + x2 = 0;
? 100 ?
? x + y + z = a, ? x1 + 2x2 + 3x3 + . . . + nxn = a1 ,
? ?
? x + y + t = b, ?
nx1 + x2 + 2x3 + . . . + (n ? 1)xn = a2 ,
б) г)
? x + z + t = c, ?........................
? ?
? ?
2x1 + 3x2 + 4x3 + . . . + xn = an .
y + z + t = d;
9.100. Имеются 13 гирь. Известно, что любые 12 из них можно так
разложить на две чашки весов, по шесть на каждую, что наступит
равновесие. Докажите, что все гири имеют одну и ту же массу, если из-
вестно, что: а) масса каждой гири равна целому числу граммов; б) масса
каждой гири равна рациональному числу граммов; в)? масса каждой
гири может быть равна любому действительному (неотрицательному)
числу.
9.101. Известно, что
?
? a1 ? 4a2 + 3a3 0,
?
? a ? 4a + 3a
?2
? 0,
3 4
..............
?
? a99 ? 4a100 + 3a1 0,
?
?
?
a100 ? 4a1 + 3a2 0.
Пусть a1 = 1; чему равны тогда числа a2 , . . . , a100 ?
Глава 10
Неравенства

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

1. Различные неравенства
В задачах 10.1 – 10.37 докажите неравенства.
10.1. x + 1/x 2.
10.2. Неравенство между средним квадратическим и сред-
ним арифметическим.

a2 + b2 a+b
.
2 2

10.3. (a + b + c + d)2 4(a2 + b2 + c2 + d2 ).
v v
10.4. (a + c)(b + d) ab + cd.
v a + 3b
4
ab3
10.5. .
4
10
a + 2b + 3c + 4d
10.6. ab2 c3 d4 .
10
10.7. x2 + y2 + z2 xy + yz + xz.
10.8. x2 + y2 + 1 xy + x + y.
10.9. x2 + x2 + x2 + x2 + x2 x1 (x2 + x3 + x4 + x5 ).
1 2 3 4 5

10.10. x4 + y4 + 8 8xy.
3 a+b+c
10.11. .
1/a + 1/b + 1/c 3
10.12. (ab + bc + ac)2 3abc(a + b + c).
v v v
1x
2 4 6x
x
2·2
10.13. 2 .
+2
10.14. ab + bc + ac 0 при a + b + c = 0.
x+y
< 1, при |x|, |y| < 1.
10.15.
1 + xy
1. Различные неравенства 143

10.16. x? y? ?x + ?y, при условии, что ? + ? = 1 (?, ? > 0).
10.17. a2 b2 + b2 c2 + a2 c2 abc(a + b + c).
10.18. (a + 1)(b + 1)(a + c)(b + c) 16abc.
10.19. (a + b + c + d + 1)2 4(a2 + b2 + c2 + d2 ), при a, b, c, d ? [0; 1].
10.20. x4 + y4 + z2 + 1 2x(xy2 ? x + z + 1).
v v
10.21. ( x + y)8 64xy(x + y)2 (x, y 0).
10.22. (a + b)(b + c)(a + c) 8abc.
10.23. (a + b + c)(a2 + b2 + c2 ) 9abc.
10.24. a2 (1 + b4 ) + b2 (1 + a4 ) (1 + a4 )(1 + b4 ).
10.25. a4 + b4 + c4 abc(a + b + c).
10.26. a3 b + b3 c + c3 a abc(a + b + c).
10.27. 2(a3 + b3 + c3 ) ab(a + b) + ac(a + c) + bc(b + c).
ak a1 + . . . + an a
max k .
10.28. min
1 k n bk b1 + . . . + bn 1 k n bk

x y z
10.29. 1+ 1+ 1+ 8.
y z x
a b c
10.30. ++ 3.
b c a
a b c 3
10.31. .
+ +
b+c a+c a+b 2
1 1 1 9
10.32. .
+ +
b+c a+c a+b 2(a + b + c)
10.33. 3(a1 b1 + a2 b2 + a3 b3 ) (a1 + a2 + a3 )(b1 + b2 + b3 ) при
a1 a2 a3 , b1 b2 b3 .
10.34. Докажите, что если

a1 a2 ... an , b1 b2 ... bn ,
то наибольшая из сумм вида
a1 bk1 + a2 bk2 + . . . + an bkn
(k1 , k2 , . . . , kn — перестановка чисел 1, 2, . . . , n), это сумма
a1 b1 + a2 b2 + . . . + an bn ,

а наименьшая — сумма
a1 bn + a2 bn?1 + . . . + an b1 .
144 10. Неравенства

10.35. Неравенство Чебышёва. Докажите, что
a1 b1 + a2 b2 + . . . + an bn a1 + a2 + . . . + an b1 + b2 + . . . + bn
· .
n n n
10.36. Докажите неравенства:
a2 + b2 a2 + c 2 b2 + c2 a3 b3 c3
a+b+c + + + + .
2c 2b 2a bc ac ab
10.37. Неравенство Коробова. Докажите, что при
a1 a2 ... an 0
выполняется неравенство
2
a a an
v 1v + v 2v + . . . + v
2 2 2
v
a + a + ... + a .
1 2 n
n+ n?1
1+ 0 2+ 1

2n , где x1 . . . xn = 1.
10.38. Докажите неравенство (1+x1 ) . . . (1+xn )
10.39. Докажите, что для любого натурального n справедливо нера-
венство
1 1 1
+ + ... + > 1.
n+1 n+2 3n + 1
10.40. Докажите, что для любого натурального n сумма
1 1 1
+ + ... +
n+1 n+2 2n
лежит в пределах от 1/2 до 3/4.
11
10.41* . Даны рациональные положительные p, q, причем + = 1.
pq
Докажите, что для положительных a и b выполняется неравенство
ap bq
ab + .
p q
10.42. Найдите наименьшую величину выражения
x2 + (1 ? x2 )2 + x2 + (1 ? x3 )2 + . . . + x2 + (1 ? x1 )2 .
1 2 2n

10.43. Для натурального n докажите неравенства:
v
v n+1
n
а) n ;
n!
2
n
nn
n
б) ;
< n! <
3 2
n
nn
n
в) .
< n! < n
e e
2. Суммы и минимумы 145

?
10.44. Докажите, что при x ? 0; выполняется неравенство
2
1 1
0< ? 2 < 1.
2
sin x x
(См. также 7.81.)
10.45. v v
Докажите, что для любых натуральных m и n хотя бы одно
v
n, n m не больше 3 3.
m
из чисел
2
..
2.
10.46. Как расставить скобки в выражении 2 , чтобы оно было
максимальным?
10.47. Докажите справедливость оценок:
1 1 1 1
а) (n
+ + ... + 1);
n+1 n+2 2n 2
n 1 1
б) (n
1 + + ... + n n 1);
2 2 2 ?1
1 13 99 1
< · · ... ·
в) <;
15 24 100 10
13 99 1
г) · · . . . · <.
24 100 12
x y z
10.48. Докажите, что уравнение = 1 неразрешимо в
++
y z x
натуральных числах.

2. Суммы и минимумы
10.49. Сумма минимумов и минимум суммы. Предположим,
что имеется набор функций f1 (x), . . . , fn (x), определенных на отрезке
[a; b]. Докажите неравенство:
min f1 (x) + . . . + min fn (x) min (f1 (x) + . . . + fn (x)).
x?[a;b] x?[a;b] x?[a;b]

10.50. Докажите неравенство:
(b1 + . . . + bn )2
b2 b2
+ ... + n
1
.
a1 an a1 + . . . + an
10.51. Выведите из неравенства предыдущей задачи
а) неравенство Коши – Буняковского:
(c1 d1 + . . . + cn dn )2 (c2 + . . . + c2 )(d2 + . . . + d2 );
1 n 1 n

б) неравенство между средним арифметическим и средним квадра-
тическим:
a2 + . . . + a2
a1 + . . . + an n
1
;
n n
146 10. Неравенства

в) неравенство между средним арифметическим и средним гармо-
ническим:
n b1 + . . . + bn
.
1/b1 + . . . + 1/bn n
10.52. Докажите неравенство:
b1 +...+bn b1 bn
b1 + . . . + bn b1 bn
... .
a1 + . . . + an a1 an
10.53. Используя результат предыдущей задачи, докажите неравен-
ства:
v a1 + . . . + an
а) n a1 . . . an ;
n
b1 +...+bn
b1 + . . . + bn
b b1 . . . b b n ;
б) 1 n
n
в) cb1 . . . cbn c1 b1 + . . . + cn bn , где b1 + . . . + bn = 1.
1 n

10.54. Спортпрогноз. Предположим, что ожидается баскетболь-
ный матч между двумя командами A и B, в котором возможно только
два исхода: одна из команд выигрывает. Две букмекерские конторы
принимают ставки с разными коэффициентами k(1) , k(1) , k(2) , k(2) . На-
A B A B
пример, если игрок сделал ставку N в первой конторе на команду A, и
эта команда выиграла, то игрок получает сумму k(1) · N. Пусть
A

3 4
k(1) = 2, k(1) = , k(2) = , k(2) = 3.
A B A B
2 3
Как, имея капитал N, распорядиться им оптимальным образом, то есть
как сделать ставки в двух конторах, чтобы получить максимальный
гарантированный выигрыш?
Проанализируйте случай произвольных коэффициентов k(1) , kB ,
(1)
A
k(2) , kB и найдите связь между максимальным гарантированным вы-
(2)
A
игрышем и средним гармоническим наибольших коэффициентов.

3. Выпуклость
Определение. Пусть ? — график дифференцируемой функции f(x),
заданной на отрезке [a; b]:
? = {(x, y) : x ? [a; b], y = f(x)}.
Функция f(x) называется выпуклой вверх, если для любой точки T ? ?
кривая ? лежит ниже касательной к ? , проведенной в точке T . Анало-
гично определяется выпуклость вниз.
Достаточным условием выпуклости функции вниз (вверх) является
положительность (отрицательность) второй производной.
3. Выпуклость 147

10.55. Докажите, что если функция f(x) выпукла вверх на отрезке
[a; b], то для любых различных точек x1 , x2 из [a; b] и любых положи-
тельных ?1 , ?2 таких, что ?1 + ?2 = 1 выполняется неравенство:

f (?1 x1 + ?2 x2 ) > ?1 f(x1 ) + ?2 f(x2 ).
10.56. Неравенство Иенсена. Докажите, что если функция
f(x) выпукла вверх на отрезке [a; b], то для любых различных точек
x1 , x2 , . . . , xn (n 2) из [a; b] и любых положительных ?1 , ?2 , . . . , ?n
таких, что ?1 + ?2 + . . . + ?n = 1, выполняется неравенство:
f(?1 x1 + . . . + ?n xn ) > ?1 f(x1 ) + . . . + ?n f(xn ).
10.57. Докажите, что для любых x1 , . . . , xn ? [0; ?] справедливо
неравенство:
sin x1 + . . . + sin xn
x1 + . . . + xn
sin .
n n
10.58. Докажите неравенства:
v v
а) n(x1 + . . . + xn ) ( x1 + . . . + xn )2 ;
n3 1 1
б) + ... + 2 ;
(x1 + . . . + xn )2 2
x1 xn
xn + . . . + x n ;
в) nx1 . . . xn 1 n

г) Неравенство Минковского.
1 1
n2 .
(x1 + . . . + xn ) + ... +
x1 xn
10.59. Докажите, что если x + y + z = 6, то x2 + y2 + z2 12.
10.60. Неравенство Гёльдера. Пусть p и q — положительные чис-
ла, причем 1/p + 1/q = 1. Докажите, что
(ap + ap + . . . + ap )1/p (aq + aq + . . . + aq )1/q .
a1 b1 + a2 b2 + . . . + an bn 1 2 1 2
n n

Определение. Для любого действительного ? = 0 средним степен-
ным чисел x1 , . . . , xn порядка ? называется число
1/?
x? + . . . + x?
n
1
S? (x) = .
n
Частными случаями средних степенных являются: среднее гармониче-
ское (? = ?1), среднее арифметическое (? = 1), среднее квадратическое
(? = 2). Средним степенным порядка 0 будем считать среднее геомет-
v
рическое S0 (x) = n x1 . . . xn .
148 10. Неравенства

10.61. Докажите, что выполняются классические неравенства меж-
ду средними степенными:

S?1 (x) S0 (x) S1 (x) S2 (x).

10.62. Докажите, что если ? < ? и ?? = 0, то S? (x) S? (x).
10.63* . Докажите, что если ? < 0 < ?, то

S? (x) S0 (x) S? (x),

причем
lim S? (x) = lim S? (x) = S0 (x).
?>?0 ?>+0


10.64. Докажите, что если ? < ?, то S? S? , причем равенство
возможно только когда x1 = x2 = . . . = xn .

4. Симметрические неравенства
10.65. Докажите неравенства:
а) x4 + y4 + z4 x2 yz + xy2 z + xyz2 ;
б) x3 + y3 + z3 3xyz;
в) x4 + y4 + z4 + t4 4xyzt;
г) x5 + y5 x3 y2 + x2 y3 .
Определение. Пусть имеется несколько неотрицательных перемен-
ных — для определенности, три переменные x, y и z. Наборы из такого
же количества целых неотрицательных чисел, ? = (k, j, i), где k j i,
будем называть показателями. Через T? (x, y, z) = T(k,j,i) (x, y, z) будем
обозначать симметрический многочлен

xa yb zc
T? (x, y, z) =
{a,b,c}={k,j,i}


(суммирование ведется по всем наборам {a, b, c} в количестве 3! явля-
ющимися перестановками чисел {k, j, i}).
Например неравенства из задачи 10.65 можно переписать в виде:
а) T(4,0,0) (x, y, z) T(2,1,1) (x, y, z);
б) T(3,0,0) (x, y, z) T(1,1,1) (x, y, z);
в) T(4,0,0,0) (x, y, z, t) T(1,1,1,1) (x, y, z, t);
г) T(5,0) (x, y) T(3,2) (x, y).
10.66. Запишите через многочлены вида T? неравенства
а) x4 y + y4 x x3 y2 + x2 y3 ;
б) x3 yz + y3 xz + z3 xy x2 y2 z + y2 z2 x + z2 x2 y.
4. Симметрические неравенства 149

Определение. Диаграммой Юнга, соответствующей показате-
лям ? = (?1 , . . . , ?n ) называется «лестница» из n ступенек, у которой
высота k-й ступеньки равна ?k , а ширина — единице. Например


¦? ¤ ? ? ? ? ?  ?§ ¦ ? ? ¤ ? ? ? ? 




Число s = ?1 + ?2 + . . . + ?n называется весом диаграммы Юнга.
10.67. Напишите многочлены T? и нарисуйте соответствующие им
диаграммы Юнга для следующих наборов ?:
а) (3, 2); б) (3, 2, 1); в) (3, 3, 0, 0); г) (4, 1, 1, 0).
10.68. Найдите число всех диаграмм Юнга с весом s, если
а) s = 4; б) s = 5; в) s = 6; г) s = 7.
Определение. Пусть ? = (?1 , . . . , ?n ) и ? = (?1 , . . . , ?n ) — два
набора показателей с равной суммой s = ?1 + . . . + ?n = ?1 + . . . + ?n .
Будем говорить, что ? мажорирует ? (? ?), если справедлива си-
стема неравенств:
?
? ?1 ?1 ,
?
?
?
? ?1 + ?2 ?1 + ?2 ,
?
?
.....................
?
?
? ?1 + . . . + ?n?1 ?1 + . . . + ?n?1 ,
?
?
?
?
?1 + . . . + ?n = ?1 + . . . + ?n .
В этом случае будем также говорить, что диаграмма Юнга, соответ-
ствующая набору ?, мажорирует диаграмму Юнга, соответствующую
набору ?.
Например, (4, 2, 1) (3, 2, 2), так как 4 3, 4 + 2 3 + 2, 4 + 2 + 1 =
= 3 + 2 + 2.
10.69. Докажите, что ? = (?1 , ?2 , ?3 ) ? = (?1 , ?2 , ?3 ) тогда и
только тогда, когда ? можно получить из ? проделав несколько (может
быть один раз или ни одного) операцию
?
? (k ? 1, j + 1, i)
?
(k, j, i) ?> (k ? 1, j, i + 1)
?
?
(k, j ? 1, i + 1)
Эту операцию можно представлять себе как сбрасывание одного
кирпича вниз на диаграмме Юнга.
150 10. Неравенства

10.70. Нарисуйте все лестницы из s = 4 кирпичей в порядке убы-
вания, начиная с самой крутой (4, 0, 0, 0), и заканчивая самой пологой
(1, 1, 1, 1).
10.71. а) Проверьте, что диаграммы Юнга (4, 1, 1) и (3, 3, 0) не
сравнимы, — ни одна из них не мажорирует другую. Есть ли еще такие
несравнимые наборы с суммой 6?
б) Найдите все несравнимые пары наборов для s = 7.
10.72. Пусть T? (x, y, z) T? (x, y, z) для всех неотрицательных x,
y, z. Докажите, что ? ?.
10.73* . Неравенство Мюрхеда. Пусть
и
? = (?1 , . . . , ?n ) ? = (?1 , . . . , ?n )
— два набора показателей с равной суммой. Докажите, что, если ? ?,
то при всех неотрицательных x1 , . . . , xn выполняется неравенство
T? (x1 , . . . , xn ) T? (x1 , . . . , xn ).

10.74. Выведите из неравенства Мюрхеда неравенство между сред-
ним арифметическим и средним геометрическим.
Сколько «кирпичей» нужно свалить, чтобы от набора (n, 0, . . . , 0)
из n чисел перейти к набору (1, 1, . . . , 1)?
10.75. Докажите следующие неравенства непосредственно и при по-
мощи неравенства Мюрхеда:
а) x4 y2 z + y4 x2 z + y4 z2 x + z4 y2 x + x4 z2 y + z4 x2 y 2(x3 y2 z2 + x2 y3 z2 +
+ x2 y2 z3 );
б) x5 + y5 + z5 x2 y2 z + x2 yz2 + xy2 z2 ;
в) x3 + y3 + z3 + t3 xyz + xyt + xzt + yxt.
10.76. Докажите неравенства из задачи 10.36 при помощи неравен-
ства Мюрхеда. Как будут выглядеть диаграммы Юнга для соответству-
ющих функций?
Глава 11
Последовательности и ряды

1. Конечные разности
Определение. Пусть задана последовательность чисел
{bn } = b1 , b2 , . . . , bn , . . .
Будем обозначать {?bn } последовательность, состоящую из разностей
соседних членов последовательности {bn }:
(n = 1, 2, . . . ).
?bn = bn+1 ? bn
(Считается, что b0 = 0.) ? называется разностным оператором ?) или
оператором конечной разности.
11.1. Найдите
а) ?n2 ; б) ?n(n ? 1); в) ?nk ; г) ?Ck .
n

11.2. Пусть даны последовательности чисел {an } и {bn }, связанные
соотношением ?bn = an , (n = 1, 2, . . . ). Как связаны частичные сум-
мы Sn последовательности {an }
Sn = a1 + a2 + . . . + an
с последовательностью {bn }?
11.3. Найдите последовательность {an } такую, что ?an = n2 . Ис-
пользуя результат предыдущей задачи, получите формулу для суммы
12 + 22 + 32 + . . . + n2 .
11.4. Выведите формулу для суммы 13 + 23 + 33 + . . . + n3 .
11.5. Докажите тождество
n
1 F2n ?1
(n
=3? 1).
F2 k F2 n
k=0


?) Оператор — это отображение, действующее на множестве функций, последова-
тельностей или других отображений.
152 11. Последовательности и ряды

Определение. Для функции f(x) выражение f(x + 1) ? f(x) будем
обозначать ?f(x) и называть конечной разностью первого порядка. Ко-
нечные разности более высокого порядка определяются индуктивно:
?n f(x) = ?(?n?1 f(x)) (n > 1)
(считается, что ?0 f(x) = f(x)).
11.6. Докажите, что если Q(x) — многочлен степени m + 1, то
P(x) = ?Q(x) — многочлен степени m.
11.7. Докажите, что для любого многочлена P(n) степени m суще-
ствует единственный многочлен Q(n) степени m + 1 такой, что выпол-
нены два условия: ?Q(n) = P(n) и Q(0) = 0.
11.8. Докажите формулу
n
n
Ck (?1)n?k f(x + k).
? f(x) = n
k=0

11.9. Докажите равенство
n

Ck ?k f(x).
f(x + n) = n
k=0

11.10. Пусть f(x) — многочлен степени m. Докажите, что если
m < n, то ?n f(x) = 0. Чему равна величина ?m f(x) = 0?
11.11. Вычислите сумму
n n
k
Ck (?1)k 1 ? .
n
n
k=0

11.12. Докажите, что для всех m в промежутке 1 m < n выпол-
няется равенство:
n

(?1)k km Ck = 0.
n
k=1

(См. также 6.105.)
11.13* . Пусть числа y0 , y1 , . . . , yn таковы, что для любого много-
члена f(x) степени m < n справедливо равенство:
n

(11.1)
f(k)yk = 0.
k=0

Докажите, что yk = ?(?1)k Ck , где ? — некоторое фиксированное число.
n
1. Конечные разности 153

11.14. Докажите следующие свойства оператора конечной разности,
подобные свойствам оператора дифференцирования:
1 ?bn an bn ?an ? an ?bn
а) ? ; б) ? .
=? =
bn bn bn+1 bn bn bn+1
11.15. Найдите представление для ?(an ·bn ) через ?an и ?bn . Срав-
ните полученную формулу с формулой для производной произведения
двух функций.
11.15 . Разностный аналог формулы Лейбница. Для n-ой про-
изводной произведения двух функций существует формула Лейбница

n
(n)
Ck f(k) (x)g(n?k) (x).
f(x)g(x) = n
k=0


Докажите её разностный аналог

n
n
Ck ?k f(x)?(n?k) g(x).
? f(x)g(x) = (?)
n
k=0


11.16. Экспонентой y = ex называется такая функция, для которой
выполнены условия y (x) = y(x) и y(0) = 1. Какая последователь-
ность {an } будет обладать аналогичными свойствами, если производную
заменить на разностный оператор ??
11.17. Преобразование Абеля. Для подсчета интегралов исполь-
зуется формула интегрирования по частям. Докажите следующие две
формулы, которые являются дискретным аналогом интегрирования по
частям и называются преобразованием Абеля:

n?1 n?1 n?1 x

f(x)g(x) = f(n) g(x) ? ?f(x) g(z),
x=0 x=0 x=0 z=0
n?1 n?1

f(x)?g(x) = f(n)g(n) ? f(0)g(0) ? g(x + 1)?f(x).
x=0 x=0



11.18. Найдите последовательность {an } такую, что ?an = n2n .
xex dx.)
(Вспомните как вычисляют
11.19. Найдите:
154 11. Последовательности и ряды
n n
1 4k + 1
а) ; д) ;
2
k(k + 1) k=1 k(k + 1)(4k ? 1)
k=1
n n
1 k?1
б) ; е) ;
2 k!
k ?1
k=2 k=1
n n
1
в) ; ж) k! k.
k(k + 1)(k + 2)
k=1 k=1
(k ? 1) 2k
n
г) ;
k(k + 1)
k=1

11.20. При помощи преобразования Абеля вычислите следующие
суммы:
n n n
k2 qk?1 ; б) k2 cos kx.
а) k sin kx; в)
k=1 k=1 k=1

Определение. В дальнейшем под символом Cn будем понимать
x
многочлен
x(x ? 1) . . . (x ? n + 1)
Cn = ,
x
n!
определенный для всех действительных x. При целых x n его значе-
ния будут совпадать с обычными биномиальными коэффициентами.
11.21. Интерполяционная формула Ньютона. а) Докажите,
что для любого многочлена f(x) степени n существует единственное
представление его в виде
f(x) = d0 C0 + d1 C1 + . . . + dn Cn .
x x x

Здесь и далее биномиальный коэффициент Ck интерпретируется как
x
многочлен от переменной x. В частности, нижний индекс у биномиаль-
ного коэффициента может быть любым действительным числом. (См.
также 6.79.)
б) Докажите, что коэффициенты d0 , d1 , . . . , dn в этом представле-
нии вычисляются по формуле dk = ?k f(0) (0 k n).
11.22. Целозначные многочлены. Пусть многочлен f(x) степени
n принимает целые значения в точках x = 0, 1, . . . , n. Докажите, что
f(x) = d0 C0 + d1 C1 + . . . + dn Cn ,
x x x

где d0 , d1 , . . . , dn — некоторые целые числа.
11.23. Для многочлена f(x) = x3 ? x найдите ?2 f(x). Объясните, не
применяя соображения делимости, почему f(x) . 6 при всех целых x.
.
.
11.24. Докажите, что многочлен f(x) степени n принимает целые
значения в точках x = 0, 1, . . . , n, то он принимает целые значения для
любого целого x.
2. Рекуррентные последовательности 155

11.25. а) Пусть q — натуральное число и функция
f(x) = cqx + an xn + . . . + a1 x + a0
принимает целые значения при x = 0, 1, 2, . . . , n + 1. Докажите, что
при любом целом x 0 число f(x) также будет целым.
б) Пусть выполняются условия пункта а) и f(x) делится на некоторое
m 1 при x = 0, 1, 2, . . . , n + 1. Докажите, что f(x) делится на m при
всех целых x 0.
11.26. Докажите, что при всех натуральных n число f(n) = 22n?1 ?
? 9n2 + 21n ? 14 делится на 27.
11.27* . Для каких натуральных n в выражении
±12 ± 22 ± 32 ± . . . ± n2
можно так расставить знаки + и ?, что в результате получится 0?
Определение. Пусть функция f(x, y) задана во всех точках плоско-
сти с целыми координатами. Назовем функцию f(x, y) гармонической,
если ее значение в каждой точке равно среднему арифметическому
значений функции в четырех соседних точках, то есть
1
f(x, y) = (f(x + 1, y) + f(x ? 1, y) + f(x, y + 1) + f(x, y ? 1)).
4
11.28. Пусть f(x, y) и g(x, y) — гармонические функции. Докажите,
что для любых a и b функция af(x, y) + bg(x, y) также будет гармони-
ческой.
11.29. Пусть f(x, y) — гармоническая функция. Докажите, что
функции ?x f(x, y) = f(x+1, y)?f(x, y) и ?y f(x, y) = f(x, y+1)?f(x, y)
также будут гармоническими.
11.30* . Дискретная теорема Лиувилля. Пусть f(x, y) — огра-
ниченная гармоническая функция, то есть существует положительная
константа M такая, что
|f(x, y)|
?(x, y) ? Z2 M.
Докажите, что функция f(x, y) равна константе.

2. Рекуррентные последовательности
Определение. Последовательность чисел a0 , a1 , . . . , an , . . . , кото-
рая удовлетворяет с заданными p и q соотношению
(n = 0, 1, 2, . . . ) (11.2)
an+2 = pan+1 + qan
156 11. Последовательности и ряды

называется линейной рекуррентной (возвратной) последовательно-
стью второго порядка.
Уравнение
x2 ? px ? q = 0 (11.3)

называется характеристическим уравнением последовательности {an }.
11.31. Докажите, что если числа a0 , a1 фиксированы, то все осталь-
ные члены последовательности {an } определяются однозначно.
11.32. Докажите, что геометрическая прогрессия {an } = bxn удо-
0
влетворяет соотношению (11.2) тогда и только тогда, когда x0 — корень
характеристического уравнения (11.3) последовательности {an }.
11.33. Пусть характеристическое уравнение (11.3) последователь-
ности {an } имеет два различных корня x1 и x2 . Докажите, что при
фиксированных a0 , a1 существует ровно одна пара чисел c1 , c2 такая,
что
an = c1 xn + c2 xn (n 0).
1 2

11.34. Пусть характеристическое уравнение (11.3) последовательно-
сти {an } имеет корень x0 кратности 2. Докажите, что при фиксирован-
ных a0 , a1 существует ровно одна пара чисел c1 , c2 такая, что

an = (c1 + c2 n)xn (n 0).
0

11.35. Найдите формулу n-го члена для последовательностей, за-
данных условиями (n 0):
a) a0 = 0, a1 = 1, an+2 = 5an+1 ? 6an ;
б) a0 = 1, a1 = 1, an+2 = 3an+1 ? 2an ;
в) a0 = 1, a1 = 1, an+2 = an+1 + an ;
г) a0 = 1, a1 = 2, an+2 = 2an+1 ? an ;
д) a0 = 0, a1 = 1, an+2 = 2an+1 + an .
v
11.36. При возведении числа 1 + 2 в различные степени, можно
обнаружить некоторые закономерности:
v v v v
(1 + 2)1 = 1 + 2 = 2 + 1,
v v v v
(1 + 2)2 = 3 + 2 2 = 9 + 8,
v v v v
(1 + 2)3 = 7 + 5 2 = 50 + 49,
v v v v
(1 + 2)4 = 17 + 12 2 = 289 + 288.
Для v изучения определим числа an и bn при помощи равенства
их v
(1 + 2)n = an + bn 2, (n 0). (См. также 11.59.)
2. Рекуррентные последовательности 157
v
а) Выразите через an и bn число (1 ? 2)n .
б) Докажите равенство a2 ? 2b2 = 1.
n n
в) Каким рекуррентным уравнениям удовлетворяют последователь-
ности {an } и {bn }?
г) Пользуясь пунктом а), найдите формулы n-го члена для последо-
вательностей {an } и {bn }.
д) Найдите связь между числами an , bn и подходящими дробями к
v
числу 2.
11.37. Рассмотрим равенства:
v v v
2 + 3 = 4 + 3,
v v v
(2 + 3)2 = 49 + 48,
v v v
(2 + 3)3 = 676 + 675,
v v v
(2 + 3)4 = 9409 + 9408.
Обобщите результат наблюдения и докажите возникшие у вас догадки.
11.38. Докажите, что уравнение
v v v
(x + y 5)4 + (z + t 5)4 = 2 + 5
не имеет решений в рациональных числах x, y, z, t.
11.39. Найдите все целочисленные решения уравнения a2 ?3b2 = 1.
n n

11.40. Докажите, что произвольная последовательность Qn , задан-
ная условиями
(n
Q0 = ?, Q1 = ?, Qn+2 = Qn+1 + Qn 0),
может быть выражена через числа Фибоначчи Fn и числа Люка Ln .
Определение. Многочлены Фибоначчи Fn (x) (n 0) задаются при
помощи начальных условий F0 (x) = 0, F1 (x) = 1 и рекуррентного соот-
ношения
Fn+1 (x) = x Fn (x) + Fn?1 (x) (n 1).
Аналогично, многочлены Люка Ln (x) определяются равенствами
Ln+1 (x) = x Ln (x) + Ln?1 (x) (n
L0 (x) = 2, L1 (x) = x, 1).
11.41. Многочлены Фибоначчи и Люка. Вычислите несколько
первых многочленов Фибоначчи и Люка. Какие значения эти многочле-
ны принимают при x = 1?
Докажите, что многочлены Люка связаны с многочлены Фибоначчи
соотношениями (см. также 3.133):
158 11. Последовательности и ряды

а) Ln (x) = Fn?1 (x) + Fn+1 (x) (n 1);
б) Fn (x) (x2 + 4) = Ln?1 (x) + Ln+1 (x) (n 1);
в) F2n (x) = Ln (x) · Fn (x) (n 0);
г) Ln (x)2 + Ln+1 (x)2 = F2n+1 (x)(x2 + 4) (n 0);
д) Fn+2 (x) + Fn?2 (x) = (x2 + 2)Fn (x) (n 2).
11.42. Разложите функции Fn+1 (x)/Fn (x) и Ln+1 (x)/Ln (x) (n 1) в
цепные дроби, (См. также 3.144.)
11.43. Получите формулу для многочленов Фибоначчи и Люка ана-
логичную формуле Бине. (См. также 3.126 и 11.75.)
11.44. Докажите, что многочлены Фибоначчи и Люка связаны с
многочленами Чебышёва равенствами
Fn+1 (ix) Ln (ix)
x x
Un = , 2Tn = .
in in
2 2
11.45. Укажите явный вид коэффициентов в многочленах Fn (x)
и Ln (x). Решите задачи 3.129 и 3.130 используя многочлены Фибоначчи.
11.46. Лягушка-путешественница. Лягушка прыгает по верши-
нам треугольника ABC, перемещаясь каждый раз в одну из соседних
вершин. Сколькими способами она может попасть из A в A за n прыж-
ков?
11.47. Лягушка прыгает по вершинам шестиугольника ABCDEF,
каждый раз перемещаясь в одну из соседних вершин.
а) Сколькими способами она может попасть из A в C за n прыжков?
б) Тот же вопрос, но при условии, что ей нельзя прыгать в D?
в)? Лягушка-сапер. Пусть путь лягушки начинается в вершине A,
а в вершине D находится мина. Каждую секунду она делает очередной
прыжок. Какова вероятность того, что она еще будет прыгать через
n секунд? Какова средняя продолжительность жизни таких лягушек?
11.48. Докажите, что для любого числа p>2 найдется такое число ?,
что
n n
2 + p = ?2 ? ??2 .
2+ 2 + ... + 2+

n радикалов

11.49. Садовник, привив черенок редкого растения, оставляет его
расти два года, а затем ежегодно берет от него по 6 черенков. С каждым
новым черенком он поступает аналогично. Сколько будет растений и
черенков на n-м году роста первоначального растения?
11.50. Найдите у чисел
2. Рекуррентные последовательности 159
v v v
а) (6 + 35)1999 ; б) (6 + 37)1999 ; в) (6 + 37)2000
первые 1000 знаков после запятой.
11.51.vДокажите, что при всех натуральных n выполняется сравне-
ние [(1 + 2)n ] ? n (mod 2).
11.52. Докажите, что последовательность an = 1 + 17n2 (n 0)
содержит бесконечно много квадратов целых чисел.
11.53. Определим последовательности {xn } и {yn } при помощи усло-
вий:
xn = xn?1 + 2yn?1 sin2 ?, yn = yn?1 + 2xn?1 cos2 ?, x0 = 0, y0 = cos ?.

Найдите выражение для xn и yn через n и ?.
11.54. Пять моряков высадились на остров и к вечеру набрали кучу
кокосовых орехов. Дележ отложили на утро. Один из них, проснувшись
ночью, угостил одним орехом мартышку, а из остальных орехов взял
себе точно 1/5 часть, после чего лег спать и быстро уснул. За ночь так
же поступили один за другим и остальные моряки; при этом каждый не
знал о действиях предшественников. На утро они поделили оставшиеся
орехи поровну, но для мартышки в этот раз лишнего ореха не осталось.
Каким могло быть наименьшее число орехов в собранной куче?
Определение. Последовательность чисел a0 , a1 , . . . , an , . . . , кото-
рая при заданных b0 , . . . , bk?1 удовлетворяет соотношениям

(11.4)
an+k = bk?1 an+k?1 + . . . + b0 an (n = 0, 1, 2, . . . ),

называется линейной рекуррентной (возвратной) последовательно-
стью k-го порядка.
Уравнение
xk ? bk?1 xk?1 ? . . . ? b0 = 0

называется характеристическим уравнением последовательности {an }.
11.55* . Как будет выглядеть формула n-го члена для рекуррентной
последовательности k-го порядка, если
a) характеристическое уравнение имеет простые корни x1 , . . . , xk ;
б) характеристическое уравнение имеет корни x1 , . . . , xm с кратно-
стями ?1 , . . . , ?m соответственно?
11.56. Пусть характеристическое уравнение (11.3) последовательно-
сти (11.2) имеет комплексные корни x1,2 = a ± ib = re±i? . Докажите,
что для некоторой пары чисел c1 , c2 будет выполняться равенство

an = rn (c1 cos n? + c2 sin n?).
160 11. Последовательности и ряды

11.57. Найдите формулу n-го члена для последовательностей, за-
данных условиями (n 0):
a) a0 = 0, a1 = 1, an+2 = 4an+1 ? 5an ;
б) a0 = 1, a1 = 2, an+2 = 2an+1 ? 2an ;
в) a0 = 1, a1 = 2, an+2 + an+1 + an = 0;
г) a0 = 1, a1 = 8, an+2 = 6an+1 + 25an .
11.58. Каким рекуррентным соотношениям вида (11.4) удовлетво-
ряют последовательности
a) an = n2 ; б) an = n3 ?
v v v v v
11.59. Пусть (1 + 2 + 3)n = pn + qn 2 + rn 3 + sn 6 (n 0).
Найдите:
p p p
а) lim n ; б) lim n ; в) lim n . (См. также 11.36.)
qn rn sn
n>? n>? n>?


3. Производящие функции
Определение. Выражения вида
F(x) = a0 + a1 x + a2 x2 + . . . + an xn + . . . (11.5)
называются формальными степенными рядами.
Формальные степенные ряды можно складывать, вычитать, умно-
жать, делить, дифференцировать и устраивать их композицию, не бес-
покоясь о сходимости.
Определение. Производной формального степенного ряда (11.5)
называется ряд
F (x) = a1 + 2a2 x . . . + nan xn?1 + . . .
11.60. Найдите произведения следующих формальных степенных
рядов:
а) (1 + x + x2 + x3 + . . . )(1 ? x + x2 ? x3 + . . . );
б) (1 + x + x2 + x3 + . . . )2 ;
(?x)n
x2 xn x2
в) 1 + x + + ... .
+ ... + + ... 1?x+ ? ... +
2! n! 2! n!
11.61. Обращение степенного ряда. Докажите, что если a0 = 0,
то для ряда F(x) существует ряд F?1 (x) = b0 + b1 x + . . . + bn xn + . . .
такой, что F(x)F?1 (x) = 1.
11.62. Вычислите:
а) (1 + x)?1 ; б) (1 ? x)?1 ; в) (1 ? x)?2 .
Определение. Пусть {an } = a0 , a1 , . . . — произвольная числовая
последовательность. Формальный степенной ряд
F(x) = a0 + a1 x + . . . + an xn + . . .
3. Производящие функции 161

будем называть производящей функцией этой последовательности.
11.63. Пусть F(x) — производящая функция последовательности {an }.
F(n) (x)
Докажите равенство an = .
n! x=0
11.63 . Докажите, что для нечётных p выполняется равенство
v
Fnp
5
Fn (Up?1 ( )) = ,
2 Fp
например,
F3n
Fn (4) = (p = 3);
F3
F
Fn (11) = 5n (p = 5);
F5
F
Fn (29) = 7n (p = 7).
F7
11.64. Вычислите производящие функции следующих последова-
тельностей:
а) an = n; б) an = n2 ; в) an = Cn .
m

11.65. Вычислите суммы:
а) C1 + 2C2 + 3C3 + . . . + nCn ; б) C1 + 22 C2 + 32 C3 + . . . + n2 Cn .
n n n n n n n n

11.66. Пусть an — число решений уравнения
(11.6)
x1 + . . . + xk = n
в целых неотрицательных числах и 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
?(1 + x100 + x200 + . . . + x900 ) . . . = .
1?x
(См. также 1.2.)
11.69. Бином Ньютона для отрицательных показателей.
Докажите, что для всех неотрицательных n выполняются равенства
?
k k k ?n
Ck xk .
а) C б) (1 + x)
= (?1) C ; =
?n n+k?1 ?n
k=0
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 + . . . + a1 x + N +
+ a?1 x?1 + . . . + x?27 ;
б) (1 + x + . . . + x9 )6 = 1 + . . . + Nx27 + . . . + x54 .
11.72. Найдите число счастливых билетов.
Определение. Назовем экспонентой степенной ряд
?
z2 zn zk
Exp(z) = 1 + z + + ... + + ... = .
2! n! k!
k=0

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 = Cn x + Cn x + C7 x7 + . . . ,
1 44
n

c = Cn x + Cn x + C8 x8 + . . . .
22 55
n

Докажите, что
a3 + b3 + c3 ? 3abc = (1 + x3 )n .
(См. также 9.8.)
11.75. Докажите, что производящая функцияпоследовательности
чисел Фибоначчи
F(z) = F0 + F1 z + F2 z2 + . . . + Fn zn + . . .
может быть записана в виде
z 1 1 1
=v
F(z) = ? ,
2
5 1 ? ?z 1 ? ?z
1?z?z
v v
1+ 5 1? 5
где ? = ,?= . Пользуясь результатом задачи 11.63,
2 2
получите формулу Бине. (См. также 3.126 и 11.43.)
3. Производящие функции 163

11.76. Докажите, что бесконечная сумма
0,1 + 0,01 + 0,002 + 0,0003 + 0,00005 + 0,000008 + 0,0000013 + . . .
сходится к рациональному числу.
11.77. Найдите производящую функцию последовательности чисел
Люка
L(z) = L0 + L1 z + L2 z2 + . . . + Ln zn + . . . .
Пользуясь этой функцией, выразите Ln в замкнутой форме через ? и
?. (См. также 3.135.)
11.78. Вычислите суммы
? ?
Fn Ln
а) б)
; .
2n 2n
n=0 n=0

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):
? ?
n
Un (x)zn .
FT (x, z) = Tn (x)z , FU (x, z) =
n=0 n=0

11.81. Вычислите, используя производящие функции, следующие
суммы:
n?1 n?1
2k xk ; k2 2k ;
а) в)
k=0 k=0
n?1 n?1
k 2k ;
б) г) k sin kx.
k=0 k=0

11.81 . Найдите произвольную функцию линейной рекуррентной
последовательности второго порядка (11.2) с начальными членами a0 и
a1 .
Определение. Разбиением называется представление натурально-
го числа в виде суммы натуральных слагаемых. Порядок слагаемых
164 11. Последовательности и ряды

считается несущественным. Например, разбиения 3 = 1 + 2 и 3 = 2 + 1
не различаются.
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,

<<

стр. 5
(всего 9)

СОДЕРЖАНИЕ

>>