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

Числитель и знаменатель цепной дроби можно записать в виде полиномов от переменных [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][a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] [/math]
• Для числителей и знаменателей [math]n[/math]-ой подходящей дроби [math]\frac{P_n}{Q_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]P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}[/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]

Лемма (4):

[math]P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}[/math].

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

[math]\triangleright[/math]

[math]\left(\begin{array}{cc} P_n & P_{n-1} \\ Q_n & Q_{n-1} \end{array}\right)\left(\begin{array}{cc} a_{n+1} & 1 \\ 1 & 0 \end{array}\right) = \left(\begin{array}{cc} P_{n+1} & P_n \\ Q_{n+1} & Q_n \end{array}\right)[/math] по рекуррентным соотношениям для числителей и знаменателей подходящих дробей. Возьмём детерминант левой и правой части. Получим : [math](P_nQ_{n-1}-P_{n-1}Q_n)(-1)=P_{n+1}Q_n-P_nQ_{n+1}[/math]. Так как при [math]n=1:P_1Q_0-P_0Q_1=1[/math] то получаем, что лемма доказана.

[math]\triangleleft[/math]