Книги по разным темам Pages:     | 1 |   ...   | 52 | 53 | 54 | 55 | 56 |   ...   | 65 |

Пусть y = [1; 1, 1, 1,...]. Тогда y - 1 =, т.е. y(y - 1) = 1. Ясно также, y что y > 0. Решая квадратное уравнение и отбрасывая отрицательный корень, 5 + 1 получаем y = =.

2 x m r1 r35.2. Рассмотрим последовательность чисел y0 =, y1 =, y2 =, n m rrs..., ys =. Каждое из этих чисел заключено между 0 и 1. Легко проrs-верить, что yk = при k s (полагаем ys+1 = 0). Действительно, ak + yk+это равенство эквивалентно равенству rk-1 = rkak + rk+1 (нужно положить m = r0 и n = r-). Следовательно, ys = [0; as], ys-1 = [0; as-a, as],..., y0 = = [0; a0,..., as], что и требовалось.

35.3. а) Применим индукцию по k. При k = 2 требуемые соотношения легко проверяются. Если a0, a1,... рассматривать как независимые переменные, то имеет место очевидное равенство [a0; a1,..., ak+1] = a0; a1,..., ak +.

ak+Поэтому согласно предположению индукции ak + pk-1 + pk-pk+1 ak+ = = qk+ak + qk-1 + qk-ak+ak+1(akpk-1 + pk-2) + pk-1 ak+1pk + pk-= =.

ak+1(akqk-1 + qk-2) + qk-1 ak+1qk + qk-б) и в) легко следуют из а).

35.4. По построению разложения в цепную дробь a0, a0 + и aвообще p2k/q2k и p2k+1/q2k+1. Кроме того, согласно задаче 35.3 в) pk-2 pk (-1)k-1ak - =.

qk-2 qk qkqk-Поэтому (для иррационального ) p0 p2 p3 p<... <... <.

q0 q2 q3 qТеперь сходимость последовательности pk/qk вытекает из того, что согласно задаче 35.3 б) pk pk-1 - = qk qk-1 qkqk-442 Глава 35. Цепные дроби и qk при k.

35.5. О т в е т: x1 = 1, x2 = 1, x3 = 3, x4 = 4,..., xn = n. Выражение в левой части больше, поэтому x1 < 2, а значит, x1 = 1. Пусть [0; 3, 4,..., n] = 1 1 = a и [0; x2,..., xn] = x. Тогда 1- =, т.е. = 1+a. Таким образом, 2 + a 1 + x x [1; 3, 4,..., n] = [x2; x3,..., xn]. Ясно, что целые части выражений в левой и правой части равны 1 и x2, поэтому x2 = 1. После этого получаем равенство [3; 4,..., n] = [x3; x4,..., xn]. Снова сравнивая целые части, получаем x3 = и т.д.

pk pk-35.6. Равенство из задачи 35.3 б) можно переписать в виде = + qk qk-(-1)k-1 pk-1 pk-2 (-1)k-2 p1 p0 +. Затем запишем = + и т.д. до = + = qk-1qk qk-1 qk-2 qk-2qk-1 q1 q0 q0q= a0 +.

q0q35.7. Применим индукцию по n. При n = 1 утверждение очевидно. Шаг индукции делается следующим образом. Мономы, которые получаются при вычёркивании нескольких пар xixi+1, можно разбить на две группы: те, в которых переменная xn не вычеркнута, и те, в которых переменная xn вычеркнута. Поскольку вместе с xn обязательно вычёркивается xn-1, это разбиение согласуется с рекуррентным соотношением.

35.8. Те же самые рассуждения, что и в задаче 35.7, лишь с заменой xn на x1, показывают, что новая последовательность многочленов характеризуется с помощью вычёркиваний точно так же, как и старая.

35.9. Пусть an = Kn(1, 1,..., 1). Тогда a0 = 1, a1 = 1 и an = an-1 + an-при n 2.

35.10. Предположим сначала, что x/y наилучшее приближение числа = [a0; a1, a2,...], которое не совпадает ни с одной подходящей дробью pn/qn.

Покажем, что тогда p0/q0 < x/y < p1/q1. Действительно, если x/y < p0/q0 = = a0, то x x 0 - a0 < - y - = y - x.

y y Поэтому |x - y| > | - a0|, чего не может быть. А если x/y > p1/q1, то x p1 x 0 - -, y q1 y поэтому x x p1 - -, y y q1 yqа значит, 1 |x - y| = |a0 - |, q1 aчего тоже не может быть.

Глава 35. Цепные дроби Из того, что точка x/y лежит внутри отрезка [p0/q0, p1/q1], следует, что она лежит между точками pn-1/qn-1 и pn+1/qn+1 (по предположению она не совпадает ни с одной из них). Таким образом, при нечётном n pn-1 x pn+1 pn < qn-1 y qn+1 qn (при чётном n все неравенства заменяются на противоположные). Поэтому получаем неравенства 1 x pn-1 pn pn-1 - < - =, yqn-1 y qn-1 qn qn-1 qnqn- 1 pn+1 x x - -, yqn+1 qn+1 y y pn pn pn+1 - pn pn+1 - + - = - =.

qn qn qn+1 qn qn+1 qnqn+Значит, qn < y и |x - y| |pn - qn|. Это противоречит тому, что qn+x/y наилучшее приближение числа.

Предположим теперь, что x/y = pn/qn. Требуется доказать, что если a/b = pn/qn и 1 b < qn, то |pn - qn| |a - b|. (35.1) Из равенств pn pn-1 pn pn-1 - + - = - = qn qn-1 qn qn-1 qnqn-и pn-1 pn+1 pn-1 pn+1 an+ - - - = - = qn-1 qn+1 qn-1 qn+1 qn-1qn+следуют неравенства 1 |pn-1 - qn-1| (35.2) qn+1 qn и равенство qn|pn-1 - qn-1| + qn-1|pn - qn| = 1. (35.3) Если a = pn-1 и b = qn-1, то согласно (35.2) |pn - qn| |pn-1 - qn-1| = |a - b|.

qn+Поэтому будем считать, что |aqn-1 - bpn-1| 1. Тогда a pn-1 a pn-1 - + - - - -, b qn-1 qn-1 bqn-т.е.

qn-1|a - b| + b|pn-1 - qn-1| 1. (35.4) 444 Глава 35. Цепные дроби Поскольку b < qn, из равенства (35.3) следует неравенство b|pn-1 - qn-1| + qn-1|pn - qn| 1. (35.5) Из неравенств (35.5) и (35.4) получаем |pn -qn| |a-b|, что и требовалось.

35.11. Согласно задаче 35.10 достаточно проверить, что если x2 - dy2 = = 1, где x и y натуральные числа, то x/y наилучшее приближение числа d (случай y = 1 легко разбирается отдельно). Для начала заметим, что x 1 x2 - y2d - d = =.

y y x + y d y(x + y d) Кроме того, x2 = dy2 1 (d - 1)y2, поэтому x + y d ( d - 1 + d)y > 2y при d 2. Следовательно, |x - y d| <.

2y Пусть a/b = x/y и |a-b d| |x-y d| (a целое число, b натуральное число). Тогда a 1 a x x 1 1 y + b - d - - < + =.

+ d by b y b y 2by 2y2 2byПоэтому 2y < y+b, т.е. b > y. Это означает, что x/y наилучшее приближение числа d.

35.12. Число является корнем квадратного уравнения ax2 + bx + c = 0, -b b2 - 4ac P D где a, b, c целые числа, поэтому = =. Изменив при 2a Q P + D необходимости знак числа Q = 2a, можно считать, что =.

Q Пусть = [a0; a1, a2,...]. Рассмотрим остаточный член k = = [ak; ak+1, ak+2,...]; при этом = [a0; a1,,..., ak-1, k ].

Шаг 1. Остаточные члены k принимают лишь конечное число различных значений. В частности, k l = для некоторых различных k и l.

P + D P - D Из равенства = следует, что =. Поэтому Q Q 2 D 2P = - > > 0 и = + > 0.

Q Q Значит, Q > 0 и P > 0. По условию < 0 и > 1, поэтому P < D и Q < P + D < 2 D. Таким образом, при фиксированном D существует лишь конечное число приведённых квадратичных иррациональностей вида P + D.

Q Покажем, что приведённая квадратичная иррациональность вида P1 + D. Неравенство > 1 следует непосредственно из определения. Из соQ1 1 отношения = a0 + следует, что - = a0 -; поэтому - = a0 - > 1.

Глава 35. Цепные дроби Далее, 1 P + D -P1 + D = - a0 = - a0 =, Q Q где P1 = a0Q - P. Напомним, что P = -b, Q = 2a и D = b2 - 4ac. Поэтому число P1 - D = a2Q2 + 2a0Q + 4ac делится на Q. Следовательно, Q Q(P1 + D) P1 + D = - =.

= P1 - D Q-P1 + D Индукция по k показывает, что k приведённая квадратичная иррацио Pk + D нальность вида, где Pk, Qk целые числа, поскольку k = ak+.

Qk k+Мы уже показали, что количество приведённых квадратичных иррациональностей такого вида конечно.

Шаг 2. Если k l = и k, l 1, то k-1 l-=.

Достаточно проверить, что если и приведённые квадратичные иррациональности, связанные соотношением вида = a0 + -1, где aнатуральное число, то число однозначно восстанавливается по. Ясно, -1 что = a0 - и 0 < - < 1. Поэтому a0 = -. Число a0 однозначно 1 восстанавливается по, поэтому число тоже восстанавливается.

35.13. Рассмотрим число pk-1 + pk- = [ d] + d = [2a0; a1,..., ak-1, ] =, qk-1 + qk- pk-1 pk- где = + a0. Это число удовлетворяет квадратному уравнению qk-1 qk- qk-12 + (qk-2 - pk-1) - pk-2 = 0.

С другой стороны, = a0 + d, поэтому 2 - 2a0 + (a2 - d) = 0.

Следовательно, pk-1 - qk-2 = 2a0qk-1 и pk-2 = (d - a2)qk-1.

Соотношение pk-2qk-1 - qk-2pk-1 = (-1)k-1 можно переписать в виде (-1)k-1 = (d - a2)qk-1 - pk-1(pk-1 - 2a0qk-1) = = (d - a2)qk-1 - (pk-1 + a0qk-1)(pk-1 - a0qk-1) = = dqk-1 - p2.

k-Глава 36.

Формальные ряды и производящие функции 36.1. Формальные ряды Формальным рядом называют выражение вида a0 + a1x + a2x2 + + a3x3 +.... При этом ряд может расходиться при всех x = 0; нас интересуют только коэффициенты a0, a1,.... Тем не менее, мы будем использовать обозначение f(x) = a0 + a1x + a2x2 + a3x3 +...; при этом функция f может быть не определена для всех x = 0.

Для формальных рядов f(x) = a0 +a1x+a2x2 +... и g(x) = b0 +b1x+ +b2x2+... можно определить их сумму и произведение как формальные ряды f(x) + g(x) = (a0 + b0) + (a1 + b1)x + (a2 + b2)x2 +..., f(x)g(x) = a0b0 + (a1b0 + a0b1)x + (a2b0 + a1b1 + a0b2)x2 +....

Формальный ряд, для которого a0 = 1 и ak = 0 при k 1, мы будем обозначать 1.

Будем считать, что f(x) = g(x), если f(x) = a0 + a1x + a2x2 +... и g(x) = b0 + b1x + b2x2 +..., где bk = kak.

36.1. Пусть f(x) = 1 + x + x2 + x3 +... и g(x) = 1 - x + x2 - x3 +....

Вычислите произведения: а) f(x)f(x); б) f(x)g(x).

36.2. Пусть f(x) = 1 + x + x2 + x3 +.... Вычислите формальный ряд g(x), для которого f(x)g(x) = 1.

Глава 36. Формальные ряды и производящие функции 36.3. Пусть f(x) = a0 + a1x + a2x2 +... формальный ряд, причём a0 = 0. Докажите, что существует единственный формальный ряд g(x) = b0 + b1x + b2x2 +..., для которого f(x)g(x) = 1.

36.2. Формальная производная Формальной производной формального ряда f(x) = akxk наk= зывают формальный ряд D f(x) = kakxk-1.

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

а) D + g(x) = D f(x) + D g(x) f(x) ;

б) D f(x)g(x) = f(x)D g(x) + g(x)D f(x) ;

в) D f(x)n = nf(x)n-1D f(x) для любого натурального n;

г) если существует формальный ряд f(x)-1, D f(x)-1 = то = -f(x)-2D f(x) и D f(x)-n = -nf(x)n-1D f(x) для любого натурального n.

д) D(fr) = rfr-1D(f) для любого рационального числа r и любого формального ряда f = 1 + a1x + a2x2 +....

36.5. Для формального ряда f = a0 + a1x + a2x2 +... положим xn S(f) = a0. Докажите, что f = S Dn(f).

n=n! 36.3. Корень из формального ряда 36.6. Докажите, что для любого натурального n и любого формального ряда f(x) = 1 + a1x + a2x2 +... существует единственный формальный ряд g(x) = 1 + b1x + b2x2 +..., для которого g(x)n = f(x).

1/n n Ряд g(x) мы будем обозначать f(x) или f(x).

36.7. Докажите, что для любого рационального числа r r(r - 1) r(r - 1)(r - 2)... (r - n + 1) (1 + x)r = 1 + rx + x2 +... + xn +...

2! n! 36.4. Экспонента и логарифм Назовём формальной экспонентой формальный ряд x2 x3 xn Exp(x) = 1 + x + + +... + +...

2! 3! n! 448 Глава 36. Формальные ряды и производящие функции 36.8. Докажите, что: а) Exp (a + b)x = Exp(ax) Exp(bx); б) k Exp(kx) = Exp(x) для любого натурального числа k.

36.9. Докажите, что n 0 при 0 < m < n, n (-1)n-kkm = k n! при m = n.

k=Пусть f = 1 + a1x + a2x2 +... формальный ряд. Формальным логарифмом f называют формальный ряд 1 1 gk Ln(f) = g - g2 + g3 -... = (-1)k+1, 2 3 k k=где g = f - 1 = a1x + a2x2 +.... Отметим, что формальный ряд Ln(f) корректно определён, поскольку коэффициент при xn полностью опре1 1 деляется конечной суммой g - g2 + g3 -... + (-1)n+1 gn.

2 3 n 36.10. Докажите, что D Ln(f) = f-1D(f).

36.11. Докажите, что если f = 1 + a1x + a2x2 +... и h = 1 + b1x + + b2x2 +..., то Ln(fh) = Ln(f) + Ln(h).

36.12. Докажите, что Ln(fr) = r Ln(f) для любого рационального числа r.

36.13. Докажите, что если Ln(f) = Ln(h), то f = h.

36.14. Докажите, что если g = a1x + a2x2 +... и r любое рациональное число, то r(r - 1) r(r - 1)(r - 2)... (r - n + 1) (1 + g)r = 1 + rg + g2 +... + gn +...

2! n! 36.15. Бесконечные последовательности a0, a1,... и b0, b1, n n... таковы, что bn = ai для всех n 0. Докажите, что тогда i=i n n an = (-1)n-i bi для всех n 0.

i=i 36.5. Тождества для формальных рядов 36.16. Докажите, что бесконечному произведению (1 + xm) m=соответствует корректно определённый формальный ряд.

Глава 36. Формальные ряды и производящие функции 36.17. Докажите следующие тождества:

а) (1 - x2m-1)2 = (1 - x2m)-1 (-1)kxk ;

m=1 m=1 k= б) (1 - xm) = (1 + xm) (-1)kxk (Гаусс).

m=1 m=1 k=36.18. Пусть s(n) сумма тех делителей d числа n, для которых n/d нечётно (s(n) = 0 при n 0).

1 - xn а) Пусть f = и g = s(n)xn-1. Докажите, что n=1 n=1 + xn D(f) = -2fg.

б) Докажите, что s(n) - 2s(n - 1) + 2s(n - 22) - 2s(n - 32) +... = = (-1)n+1n, если n полный квадрат; в противном случае эта альтернированная сумма равна нулю.

36.19. а) Используя результат задачи 36.18 б), докажите, что любое простое число p вида 4k + 1 можно представить в виде суммы двух квадратов.

б) Докажите, что любое простое число p вида 8k + 3 можно представить в виде суммы трёх квадратов.

36.6. Производящие функции Производящей функцией последовательности a0, a1, a2,... называют формальный ряд f(x) = a0+a1x+a2x2+.... Наибольший интерес производящие функции представляют в том случае, когда им соответствуют ряды, сходящиеся хотя бы на каком-то интервале.

36.20. Докажите, что производящая функция последовательности n ak =, k = 0, 1,..., n, равна (1 + x)n.

k 36.21. Пусть f(x) = ckxk производящая функция для поk=следовательности чисел Каталана, т.е. c1 = 1, c2 = c1c1 и ck = c1ck-1 + + c2ck-2 +... + ck-1c1 при k 3.

а) Докажите, что f(x) = f(x) - x.

(2n - 2)! б) Докажите, что cn =.

n!(n - 1)! 450 Глава 36. Формальные ряды и производящие функции 36.7. Числа и многочлены Бернулли -Exp(x) - Согласно задаче 36.3 формальный ряд определён x Bn однозначно. Запишем этот формальный ряд в виде xn. Чисn=n! ла Bn называют числами Бернулли. Непосредственно из определения видно, что B0 = 1.

Многочлены Бернулли определяются равенством Bn(z) = n n = Bn-kzk. Это равенство можно формально записать в k=k виде Bn(z) = (B + z)n, где подразумевается, что вместо Bk мы пишем Bk.

36.22. Докажите, что при k > 1 для чисел Бернулли выполняется k k k-1 k равенство Bp = Bk, т.е. Bp = 0.

p=0 p=p p Равенство из задачи 36.22 формально можно записать в виде (B + + 1)k = Bk, где подразумевается, что вместо Bp мы пишем Bp.

36.23. Докажите, что Bn(0) = Bn(1) = Bn.

36.24. С помощью тождества из задачи 36.22 вычислите B1, B2, B3, B4 и B5.

36.25. Докажите, что B2k+1 = 0 для всех натуральных k.

36.26. а) Докажите, что Bn(z + 1) - Bn(z) = nzn-1 при n 2.

б) Докажите, что при n 1n + 2n + 3n +... + kn = Bn+1(k + 1) - Bn+1(0).

n + 36.27. Докажите, что Bn(z) = nBn-1(z).

36.8. Число разбиений Пусть p(n) количество способов, которыми можно представить число n в виде суммы натуральных слагаемых (слагаемые могут быть одинаковыми; два представления, которые отличаются лишь порядком слагаемых, считаются одинаковыми). Число p(n) называют числом разбиений.

Pages:     | 1 |   ...   | 52 | 53 | 54 | 55 | 56 |   ...   | 65 |    Книги по разным темам