Цепная дробь

Определение:

Цепная дробь — это выражение вида [math]\langle a_0, a_1, a_2, a_3,\cdots \rangle = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\ldots}}}\;[/math] где [math]a_0[/math] есть целое число и все остальные [math]a_n[/math] натуральные числа. Различают конечные и бесконечные цепные дроби. Любая конечная дробь [math]\langle a_0, a_1, a_2, a_3,\ldots, a_n \rangle[/math] представима в виде некоторой рациональной дроби [math]\frac{P_n}{Q_n}[/math], которую называют n-ой подходящей дробью.

Примеры:

[math] \frac{7}{5}=1+\frac{1}{2+\frac{1}{2}}=\langle 1, 2, 2 \rangle[/math]

[math] \sqrt{2} = 1+\frac{1}{\sqrt{2}+1}=1+\frac{1}{2+\frac{1}{\sqrt{2}+1}}=\langle 1, 2, 2, \cdots \rangle[/math]

Числитель и знаменатель цепной дроби можно записать в виде полиномов от переменных [math]a_0, a_1, a_2,\cdots, a_n[/math]. При этом, поскольку числитель каждой дроби является знаменателем следующей, полиномы для числителей и знаменателей имеют одинаковый вид. Таким образом, цепная дробь [math]\langle a_0, a_1, a_2,\cdots, a_n \rangle [/math] представима в виде [math] \frac{[a_0, a_1, a_2,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]}[/math], где [math][a_0, a_1, a_2,\cdots, a_n][/math] — некоторый полином от [math]n+1[/math] переменной.

Свойства цепных дробей

• [math][a_0,\cdots, a_n][/math] — полином от [math]n+1[/math] переменной, состоящий из [math]F_{n+1}[/math] мономов.
• [math][a_0, a_1, a_2,\cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n][/math].
• [math][a_0, a_1, a_2,\cdots, a_n] = [a_0, a_1,\cdots, a_{n - 1}]a_n + [a_0, a_1,\cdots, a_{n-2}][/math].
• Для числителей и знаменателей [math]n[/math]-ой подходящей дроби верны следующие формулы:
  • [math]P_n = P_{n-1}a_n + P_{n-2}[/math]
  • [math]Q_n = Q_{n-1}a_n + Q_{n-2}[/math]
• [math][a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] [/math]

Доказательства свойств

Лемма (1):

[math][a_0, a_1, a_2,\cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n][/math].

Доказательство:

[math]\triangleright[/math]

[math] \frac{[a_0, a_1, a_2,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]} = a_0 + \frac{[a_2, a_3, a_4,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]} [/math]. Следовательно [math] [a_0, a_1, a_2,\cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n][/math].

[math]\triangleleft[/math]

Лемма (2):

[math][a_0,\cdots, a_n][/math] — полином от [math]n+1[/math] переменной, состоящий из [math]F_{n+1}[/math] мономов.

Доказательство:

[math]\triangleright[/math]

База. При [math]n=0[/math]: [math][a_0] = a_0[/math] — полином от одной переменной с одним мономом. [math][a_0, a_1] = a_0 a_1 + 1[/math] — два монома. Переход. Пусть верно, что в [math][a_0,\cdots, a_n][/math] [math]F_{n+1}[/math] монома. Докажем, что в [math][a_0,\cdots, a_{n+1}][/math] [math]F_{n+2}[/math] монома. [math][a_0,\cdots, a_{n+1}] = a_0[a_1,\cdots, a_{n+1}] + [a_2,\cdots, a_{n+1}][/math] В [math][a_2,\cdots, a_{n+1}][/math] нет мономов, содержащих [math] a_0 [/math]. Значит в [math][a_0,\cdots, a_{n+1}][/math] [math]F_{n+1}+F_n = F_{n+2}[/math] слагаемых.

[math]\triangleleft[/math]

Теорема (1):

[math][a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] [/math]

Доказательство:

[math]\triangleright[/math]

База: [math][a_0] = a_0 = [a_0][/math] Пусть верно для всех [math]m \lt n [/math]. Докажем для [math]n[/math]. [math][a_0, a_1, a_2, \cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n] = a_0(a_1[a_2, a_3, a_4,\cdots, a_n]+[a_3, a_4, a_5\cdots, a_n])+[a_2, a_3, a_4,\cdots, a_n]=(a_0a_1+1)[a_2, a_3, a_4,\cdots, a_n] + a_0[a_3, a_4, a_5\cdots, a_n] = [a_0, a_1][a_2, a_3, a_4,\cdots, a_n] + [a_0][a_3, a_4, a_5\cdots, a_n][/math] Обобщим последнюю формулу и докажем по индукции. Пусть верно : [math][a_0, a_1, a_2, \cdots, a_n] = [a_0, \cdots, a_k][a_{k+1},\cdots, a_n]+[a_0,\cdots, a_{k-1}][a_{k+2}, \cdots, a_n][/math]. Докажем для больших [math] k [/math] : [math] [a_0, \cdots, a_k][a_{k+1},\cdots, a_n]+[a_0,\cdots, a_{k-1}][a_{k+2}, \cdots, a_n] = [a_0, \cdots, a_k](a_{k+1}[a_{k+2}, \cdots, a_n]+[a_{k+3}, \cdots, a_n])+[a_0,\cdots, a_{k-1}][a_{k+2}, \cdots, a_n] = (a_{k+1}[a_0, \cdots, a_k] + [a_0,\cdots, a_{k-1}])[a_{k+2}, \cdots, a_n]+[a_0, \cdots, a_k][a_{k+3}, \cdots, a_n][/math]. Используя условие теоремы для [math]k \lt n-1[/math] получаем : [math] a_{k+1}[a_0, \cdots, a_k] + [a_0,\cdots, a_{k-1}] = a_{k+1}[a_k, \cdots, a_0] + [a_{k-1}, \cdots, a_0] = [a_{k+1},\cdots, a_0] = [a_0, \cdots, a_{k+1}][/math] Следовательно получаем : [math][a_0, a_1, a_2, \cdots, a_n] = [a_0, \cdots, a_{n-2}][a_{n-1}, a_n]+[a_0,\cdots, a_{n-3}][a_n] = [a_{n-2}, \cdots, a_0](a_{n-1}a_n + 1) + a_n[a_{n-3}, \cdots, a_0]=a_n[a_{n-1},\cdots, a_0] + [a_{n-2}, \cdots, a_0] = [a_n, \cdots, a_0][/math].

[math]\triangleleft[/math]

Лемма (3):

[math][a_0, a_1, a_2,\cdots, a_n] = [a_0, a_1,\cdots, a_{n - 1}]a_n + [a_0, a_1,\cdots, a_{n-2}, a_{n-1}][/math].

Доказательство:

[math]\triangleright[/math]

Эта формула аналогична формуле из Леммы 1, за исключением того, что [math]a_n[/math] "отщепляются" с другого конца. Для получения формулы достаточно скомбинировать результаты Леммы 1 и Теоремы 1.

[math]\triangleleft[/math]