3] ПРАВИЛО ЭЙЛЕРА 83

111 [2,1,4,2] 31

Таким образом, 2 +

1+4+2 [1,4,2] 11

Сделаем одно замечание. Мы видели, что общую непрерывную дробь можно выразить в виде (3), где две квадратные скобки представляют собой некоторые суммы произведений переменных до, 9ь • • Яп- Мы не доказали, что в этом представлении числитель и знаменатель нельзя ни на что сократить. В первом случае, если числитель и знаменатель - полиномы от переменных до, 9i, 9п, можно доказать, что эти полиномы неприводимы, т. е. не разлагаются на множители, являющиеся полиномами. Во втором случае, если до, gi, • • •, Qn - целые числа, то числитель и знаменатель также целые числа и можно доказать, что эти числа всегда взаимно просты. Второе из этих утверждений будет доказано в п. 4. Первый факт доказывается еще проще, но с точки зрения теории чисел не представляет интереса.

3. Правило Эйлера. Мы видели, что [до, gi, • • •, gn] является суммой некоторых произведений, образованных из элементов до, gi, ..., gn. Каковы же эти произведения? Эйлер впервые ответил на этот вопрос, указав общее правило для вычисления значения непрерывной дроби. Сначала берется произведение всех элементов, затем всевозможные произведения, которые можно получить, опустив какуюнибудь пару последовательных элементов. Затем берутся произведения, получающиеся отбрасыванием любых двух пар последовательных элементов, и так далее. Сумма этих произведений равна [до, gi, • • •, gn]- Ясно, что если п + 1 четно, то на последнем шаге отбрасыванием всех элементов мы получим пустое произведение. Его значение принимается по определению равным 1.

Пример применения правила Эйлера:

до, gi, д2, дз] = gogig2g3 + д2дз + додз + gogi +1.

Мы взяли сначала произведение всех элементов, затем произведение, получающееся, если опустить пару до, gi, затем произведение, получающееся, если опустить пару gi, g2, затем то, что получится, если опустить пару д2, дз, и, наконец, пустое произ-

ведение, которое получается, если опустить обе пары до, 9i и

Другой пример, в котором на один элемент больше:

9о, 91, 92, 9з, 94] = 9о91929з94 +

+ 929394 + 9о9з94 + 9o9i94 + 9o9i92 + 90 + 92 + 94-

Во второй строке мы написали все произведения, получаюш;ие-ся, если опустить одну пару, а затем - то, что получается, если опустить две различные пары, например, опуская 9о, 9i и 2, 9з, получаем q.

Замечая, что правило верно для нескольких первых квадратно-скобочных функций, докажем его в обш;ем случае по индукции, применив рекуррентное соотношение (4). В предположении, что правило имеет место для квадратных скобок в правой части (4), мы должны доказать его для квадратной скобки в левой части (4). Выражение [2, • • •, 9п] равно сумме произведений, получаюш;ихся из до, 9i, • • •, 9п, в которых опускается пара до, 9i- В то же время go[9i, • • •, 9п] равно в точности сумме тех произведений, в которых не опускается пара до, 9i; действительно, все произведения должны содержать множитель до; с другой стороны, если из всех этих произведений удалить до, останутся всевозможные произведения, получаюш;иеся из gi, ..., д отбрасыванием каких-либо пар последовательных элементов. Таким образом, мы получим сумму предписываемых произведений из элементов до, gi, gn, так что доказываемое правило имеет место для [go,gi, ... ,gn

Тем самым правило доказано индукцией по числу переменных.

Из правила Эйлера сразу же следует, что величина 9o,9i, •••,9п] изменится, если записать все элементы в обратном порядке [до, gi, ..., gn] = [gn, 9n-i, • • •, 9o]- Например, 2,4,1, 2] = [2,1,4, 2]. Отсюда следует, что, кроме рекуррентного соотношения (4), имеется аналогичное соотношение, выражаю-ш;ее квадратную скобку [до, gi, • • •, gn] через квадратные скобки, в которых опугцены последний элемент и два последних элемента. Это соотношение имеет вид

9o,9i, ... ,9п] = 9п[9о, ... ,gn-i] + [9o,9i, ...,9п-2]. (5)

4] ПОДХОДЯЩИЕ ДАННОЙ НЕПРЕРЫВНОЙ ДРОБИ 85

Последнее соотношение эквивалентно (4), ибо, если написать элементы в противоположном порядке, оно принимает вид

• • • 5 9о] = 9п[9п-Ь • • • ? 9о] + [9п-2? •••?9о]?

а это - соотношение (4), переписанное в новых обозначениях.

Рекуррентное соотношение (5) в большинстве случаев более удобно, чем (4). Для нас привычнее добавлять элементы, на которые оканчивается непрерывная дробь, чем те элементы, с которых она начинается; соотношение (5) дает возможность исследовать, что происходит в этом случае.

4. Подходящие данной непрерывной дроби. Пусть

90 + - ... - 6

91+ 9п

- какая-нибудь непрерывная дробь. В этом пункте мы будем предполагать, что элементы до? 9ь ...? 9п являются натуральными числами. Различные непрерывные дроби, получающиеся, если оборвать дробь (6) ранее, чем на 9о? 9оН-? 9оН---? ...

91 91+92

называются подходящими дробями к данной непрерывной дроби. Причина, по которой принято это название, выяснится позднее. Значение подходящей дроби, которая получится, если обо-

1 1

рвать исходную дробь на д, равно до +

9о?9т

91+ 9т [9ь...,9г Для упрощения обозначений положим

Am = [9О5 ... 5 9m]5 m = [9Ь . . . ? 9m], (7)

так что записанная выше подходящая дробь равна -. Первая

0 9о т-г An

подходящая дробь равна = Последняя равна --, т. е.

Во 1 Вп

значению самой непрерывной дроби. Числа Aq, Бо? • • •?

будучи суммами произведений, образованных из Qi по правилу Эйлера, являются натуральными числами.

Рекуррентное соотношение (5) в новых обозначениях принимает простую форму

Am = 9mm-l +m-2. (8)