решения квадратных уравнений. (См., например, Н. Davenport, The Higher Arithmetic (London: Hutchinson, 1952); W. J. LeVeque, Topics in Number Theory (Reading, Mass.: Addison-Wesley, 1956); см. также раддел 4.5.4.) Согласно упр. 1.2.4-35 имеем An+i = + Un)/Vn+i\, где V„+i > О, и Ап+1 = [{[VD\ + 1 + Un)/V„+ii, где V„+i < 0. Следовательно, такой алгоритм выполняется только для положительных целых чисел [y/D}. Более того, тождество Vn+i = A„(Un-i - Un) + Vn-i позволяет при определении Vn+i исключить операцию деления.]

(Ь) Пусть Y = (-y/D - U)/V, Yn = i-y/D- J7„)/V„. Заменив в доказательстве (а) у/D на -y/D, видим, что сформулированное тождество вьшолняется. Имеем

Y = (pn/Yn + Pn-i)/(qn/Yn + qn-l),

где элементы рп и qn определены в п. (с) настоящего упражнения. Следовательно,

Yn = (-qn/qn-i){Y-pn/qn)/{Y-pn-i/qn-l).

Но согласно (12) Pn-i/qn-i и Pn/qn очень близки к X; учитывая, что X ф У, величины Y - Рп/Зп я Y - Pn-i/qn-i для всех больших значений п будут иметь тот же знак, что и У - А. Это доказывает, что Уп < О для всех больших значений п. Следовательно, О < An < Хп - Yn = l\fDlVn и Vn должно быть положительным. Так как Хп > О, то и г/п < VD. Значит, Vn < 2\/D, поскольку Vn <AnVn< y/D +Un-i-

Наконец покажем, что Un > 0. Поскольку А„ < 1, то Un > y/D-Vn, так что достаточно рассмотреть случай, когда V„ > \/D. Тогда Un = AnVn - Un-i >Vn - Un-i > VD - Un-i, a это, как уже устгшовлено, величина положительная.

Замечание. В повторяющемся цикле имеем у/D + Un = А„V„ + {\/D - Un-i) > Vn; отсюда [{V+Un+i)/Vn+i\ = [An+i + Vn/(VD+Un)\ = An+i = [(\/D + Un)/Vn+i\. Другими словами, An+i определено значениями Un + ; и V„+i; величину (U„,V„) можно определить через ее преемника (Un+i, Vn+i) в периоде. Фактически из приведенных выше рассуждений следует, что когда О < Vn < y/D + Un я О < Un < \/D, to О < V„+i < y/D + Un+i и 0 < Un+i < VD . Более того, если пара (Un+i,Vn+i) следует за парой {U, V), для которой О < V < y/D + и я О < и < y/D, то и = Un я V = Vn. Таким образом, (Un, V„) будет частью цикла тогда и только тогда, когда О < Vn < у/D + Un и О < Un < VD.

( \ V V - {.qnX - pn){qnY - Рп)

ic; (g„ iA-p„ i)(g„-iy-p„ i)-

Для доказанного тождества имеется сопряженное тождество

VpnPn-i + г7(р„д„-1 + p„ ign) + ((Г/ - D)/V)g„9„-i = (-1)"J7„.

(d) Если Хп = Хт для некоторого п пг, то X - иррациональное число, удовлетворяющее квадратному уравнению (gnA-p„)/(g„ iA-p„ i) = (qmX-pm)/iqm-iX-pm-i).

История идеи, изложенной в этом упражнении, восходит к Джайадеву из Индии (не позднее 1073 г.). (См. К. S. Shukla, Ganita 5 (1954), 1-20; С.-О. Selenius, Historia Math. 2 (1975), 167-184.) Некоторые из аспектов этих идей обнаружены также в Японии и датируются не позднее 1750 года. (См. Y. Mikami, The Development of Mathematics in China and Japan (1913), 223-229.) Однако основные принципы теории цепных дробей применительно к квадратным уравнениям разработаны Эйлером [JVovi Comment. Acad. Sci. Petrop. 11 (1765), 28-66] и Лагранжем [Hist. Acad. Sci. 24 (BerUn, 1768), 111-180]. 14. Как и в упр. 9, достаточно проверить указанные тождества для случая, когда с есть последнее частичное отношение, а эта проверка выполняется просто. Применив правило Гурвица, получаем 2/е = 1, 2,1, 2,0,1,1,1,1,1,0, 2, 3, 2,0,1,1, 3,1,1,0, 2, 5,... . Перейдя к обратной величине и отбросив нули, как в упр. 9, получаем

е/2 = 1 + 2, 2т + 1, 3, 1, 2т + 1, 1, 3 , m > О

(см. упр. 16). Обратите внимание на некоторую закономерность в полученном выражении. {Schriften der phys.-oicon. Gesellschedt zu Konigsberg 32 (1891), 59-62.) Гурвиц также изложил в Vierteljahrsschrift der Naturforschenden Gesellschaft in Zurich 41 (1896), Jubelband II, 34-64, §2, способ умножения на произвольное положительное целое число. 15. (Эта процедура обрабатывает значения четырех целых чисел {A,B,C,D), которые имеют инвариантный смысл: "все, что осталось выполнить, - вывести цепную дробь вида {Ау + В)/{Су + D), где у - число, которое будет введено".) Сначала присвоим j А; О, {A,B,C,D) {a,b,c,d); затем введем Xj и будем присваивать {A,B,C,D) (Axj + В, А, Cxj -Ь D, С), j <- j + 1 один или более раз, пока знак числа С + D не станет равным знаку числа С. (Когда J > 1 и ввод не закончен, выполняется неравенство 1 < г/ < оо, а когда знак числа С + D равен знаку числа С, то известно, что {Ау + В)/{Су + D) лежит между {А + В)/{С + jD) и AjC.) Теперь приступаем к выполнению основного шага. Если точно между числами {А + В)/{С + D) м А/С нет ни одного целого числа, то выводим Хк min([A/CJ, [(А + В)/{С + D)\) и присваиваем {A,B,C,D) (С D, А - ХкС, В - XkD), к к + 1; в противном случае вводим Xj и присваиваем {A,B,C,D) <- {Axj -Ь В, А, Cxj -Ь D, С), j j -Ь 1. Основной шаг может повторяться бесконечно. Однако, если в некоторый момент окажется, что введено последнее число Xj, алгоритм немедленно переключится на вывод цепной дроби для (Axj + B)/{Cxj + D), используя алгоритм Евклида, и остановит работу.

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

М. Мендес Франс (М. Mendes Prance) показал, что количество выводимых частных на одно вводимое частное асимптотически ограничено значениями 1/г и г, где г = 2[L(od-bc)/2J+l и L - функция, определенная в упр. 38; эта граница-наилучшая из возможных. [Topics in Number Theory, edited by P. Turan, Coiioquia Math. Soc. Janos Bolyai 13 (1976), 183-194.] Госпер (Gosper) покгьзал также, что вышеприведенный алгоритм вычисления цепных дробей для X и у может быть обобщен на случай вычисления цепных дробей для (аху + Вх + Су + d)/{Axy + Вх + Су + D) (в частности, для вычисления цепных дробей для сумм и произведений) [MIT AI Laboratory Memo 239 (February, 29, 1972), Hack 101]. 16. По индукции нетрудно доказать, что fn{z) = z/{2n + I) + 0{z) -нечетная функция, представимая в некоторой окрестности начала координат в виде сходящегося степенного ряда, и что она удовлетворяет указанному дифференциальному уравнению. Поэтому

--+fn+l{z) .

Остается доказать, что limn-,oo z~, Зг",..., {2п + 1)г" = fo{z)- [Фактически Эйлер в возрасте 24 лет получил разложения в цепные дроби для гораздо более общих диффе-

fo{z) = Z- + Mz) = = z-\ 3z-\ ...,{2n + l)z-

ренциальных уравнений вида fn{z) = az + bf„{z)z"~ + cfniz), но он не потрудился доказать сходимость, поскольку в 18 веке было вполне достаточно формальных выкладок и интуиции.]

Для доказательства этого предельного уравнения имеется несколько способов. Прежде всего, полагая fn(z) = Ек nkz, можно доказать из уравнения

(2n + 1)а„1 + {2п + 3)о„з2 + (2п + b)a„bz + •.. = 1 - (o„i2 + 032 + Опвг + • • )

что {-1)*а„(2ц-1) есть сумма членов вида Ckj{ln + 1)*"*"(2п + Ьк\)-.-(2п + bkk), где Cfc и Ькт, - положительные целые числа, не зависящие от п. Например, имеем -Оп7 = 4/(2n + l)*(2n + 3){2n + 5)(2n + 7) + l/(2rj+l)»(2n + 3){2n + 7). Поэтому а(„+1)», < a„fc и 1/п (г)! < tan 11 для 11 < 7г/2. Такая равномерная оценка для /71(2) делает доказательство сходимости очень простым. При внимательном анализе этого доказательства обнаруживается, что степенной ряд для /71(2) фактически сходится при 11 < ж\/2п + 1/2; поэтому вместе с ростом п особые точки функции /„ (2) все больше и больше удаляются от начала координат и цепная дробь фактически представляет разложение функции tanh 2 на всей комплексной плоскости.

Другое доказательство дает дополнительную информацию иного плана. Если положить

, , , /2n-fc\ 2* (n-l-A:)!2""* , п г. , , , / ч

*:=0 «!>0

(п + fc - 1)! ((4п + 2)fc + (п + 1 - к)(п - к))

"+(") Е-fc!(n + l-fc)!-

к>о

= {An+2)An{z) + zAn-i{z). По индукции получаем, что

„/13 2п-1\ An{2z) + An{-2z) Чгг- 2 )~ 2"+i2"

3 2п-\\ An(2z) - An{-2z)

Следовательно,

и требуется показать, что это отношение стремится к tanh 2. В силу уравнений 1.2.9-{11) и 1.2.6-{24) имеем

....<-.)=».е"(Ё(:)(":)(-))-е("г)"й

т>0 N*;=0 m>0

Поэтому

еМ.(-2) - А„(2) = Я„(2) = (-1)"2- Х: (Tfcfw-

Далее, имеем (е" - 1)(А„(22) + Л„(-22)) - {е=" + 1)(Ап(22) - А„{-22)) = 2Дп(22); отсюда

2Дп(22)

tanh2 - llz-\Zz-\..., {2n - 1)2-7/ =

(А„(22) + А„(-22))(е2 + 1)