221
правка
Изменения
Новая страница: «Числитель и знаменатель цепной дроби можно записать в виде полиномов от пе…»
Числитель и знаменатель [[цепная дробь|цепной дроби]] можно записать в виде полиномов от переменных <tex>a_0, a_1, a_2,\cdots, a_n</tex>. При этом, поскольку числитель каждой дроби является знаменателем следующей, полиномы для числителей и знаменателей имеют одинаковый вид.
Таким образом, цепная дробь <tex>\langle a_0, a_1, a_2,\cdots, a_n \rangle </tex> представима в виде <tex> \frac{[a_0, a_1, a_2,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]}</tex>, где <tex>[a_0, a_1, a_2,\cdots, a_n]</tex> {{---}} некоторый полином от
<tex>n+1</tex> переменной.
== Свойства ==
* <tex>[a_0,\cdots, a_n]</tex> {{---}} полином от <tex>n+1</tex> переменной, состоящий из <tex>F_{n+1}</tex> мономов.
* <tex>[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]</tex>.
* <tex>[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}]</tex>.
* <tex>[a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] </tex>
* Для числителей и знаменателей <tex>n</tex>-ой подходящей дроби <tex>\frac{P_n}{Q_n}</tex> верны следующие формулы:
** <tex>P_n = P_{n-1}a_n + P_{n-2}</tex>
** <tex>Q_n = Q_{n-1}a_n + Q_{n-2}</tex>
* <tex>P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}</tex>
== Доказательства свойств ==
{{Лемма
|id=lemma1
|about=1
|statement=
<tex>[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]</tex>.
|proof=
<tex> \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]} </tex>.
Следовательно <tex> [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]</tex>.
}}
{{Лемма
|id=lemma2
|about=2
|statement=
<tex>[a_0,\cdots, a_n]</tex> {{---}} полином от <tex>n+1</tex> переменной, состоящий из <tex>F_{n+1}</tex> мономов.
|proof=
'''База'''. При <tex>n=0</tex>: <tex>[a_0] = a_0</tex> {{---}} полином от одной переменной с одним мономом. <tex>[a_0, a_1] = a_0 a_1 + 1</tex> {{---}} два монома.
'''Переход'''. Пусть верно, что в <tex>[a_0,\cdots, a_n]</tex> <tex>F_{n+1}</tex> монома. Докажем, что в <tex>[a_0,\cdots, a_{n+1}]</tex> <tex>F_{n+2}</tex> монома.
<tex>[a_0,\cdots, a_{n+1}] = a_0[a_1,\cdots, a_{n+1}] + [a_2,\cdots, a_{n+1}]</tex> В <tex>[a_2,\cdots, a_{n+1}]</tex> нет мономов, содержащих <tex> a_0 </tex>. Значит в <tex>[a_0,\cdots, a_{n+1}]</tex> <tex>F_{n+1}+F_n = F_{n+2}</tex> слагаемых.
}}
{{Теорема
|id=theorem1
|about=1
|statement=
<tex>[a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] </tex>
|proof=
База: <tex>[a_0] = a_0 = [a_0]</tex>
Пусть верно для всех <tex>m < n </tex>. Докажем для <tex>n</tex>.
<tex>[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]</tex>
Обобщим последнюю формулу и докажем по индукции. Пусть верно :
<tex>[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]</tex>.
Докажем для больших <tex> k </tex> :
<tex> [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]</tex>.
Используя условие теоремы для <tex>k < n-1</tex> получаем :
<tex> 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}]</tex>
Следовательно получаем :
<tex>[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]</tex>.
}}
{{Лемма
|id=lemma3
|about=3
|statement=
<tex>[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}]</tex>.
|proof=
Эта формула аналогична формуле из [[#lemma1|Леммы 1]], за исключением того, что <tex>a_n</tex> "отщепляются" с другого конца.
Для получения формулы достаточно скомбинировать результаты [[#lemma1|Леммы 1]] и [[#theorem1|Теоремы 1]].
}}
{{Лемма
|id=lemma4
|about=4
|statement=
<tex>P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}</tex>.
|proof=
<tex>\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)</tex> по рекуррентным соотношениям для числителей и знаменателей подходящих дробей.
Возьмём детерминант левой и правой части. Получим : <tex>(P_nQ_{n-1}-P_{n-1}Q_n)(-1)=P_{n+1}Q_n-P_nQ_{n+1}</tex>. Так как при <tex>n=1:P_1Q_0-P_0Q_1=1</tex> то получаем, что лемма доказана.
}}
Таким образом, цепная дробь <tex>\langle a_0, a_1, a_2,\cdots, a_n \rangle </tex> представима в виде <tex> \frac{[a_0, a_1, a_2,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]}</tex>, где <tex>[a_0, a_1, a_2,\cdots, a_n]</tex> {{---}} некоторый полином от
<tex>n+1</tex> переменной.
== Свойства ==
* <tex>[a_0,\cdots, a_n]</tex> {{---}} полином от <tex>n+1</tex> переменной, состоящий из <tex>F_{n+1}</tex> мономов.
* <tex>[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]</tex>.
* <tex>[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}]</tex>.
* <tex>[a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] </tex>
* Для числителей и знаменателей <tex>n</tex>-ой подходящей дроби <tex>\frac{P_n}{Q_n}</tex> верны следующие формулы:
** <tex>P_n = P_{n-1}a_n + P_{n-2}</tex>
** <tex>Q_n = Q_{n-1}a_n + Q_{n-2}</tex>
* <tex>P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}</tex>
== Доказательства свойств ==
{{Лемма
|id=lemma1
|about=1
|statement=
<tex>[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]</tex>.
|proof=
<tex> \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]} </tex>.
Следовательно <tex> [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]</tex>.
}}
{{Лемма
|id=lemma2
|about=2
|statement=
<tex>[a_0,\cdots, a_n]</tex> {{---}} полином от <tex>n+1</tex> переменной, состоящий из <tex>F_{n+1}</tex> мономов.
|proof=
'''База'''. При <tex>n=0</tex>: <tex>[a_0] = a_0</tex> {{---}} полином от одной переменной с одним мономом. <tex>[a_0, a_1] = a_0 a_1 + 1</tex> {{---}} два монома.
'''Переход'''. Пусть верно, что в <tex>[a_0,\cdots, a_n]</tex> <tex>F_{n+1}</tex> монома. Докажем, что в <tex>[a_0,\cdots, a_{n+1}]</tex> <tex>F_{n+2}</tex> монома.
<tex>[a_0,\cdots, a_{n+1}] = a_0[a_1,\cdots, a_{n+1}] + [a_2,\cdots, a_{n+1}]</tex> В <tex>[a_2,\cdots, a_{n+1}]</tex> нет мономов, содержащих <tex> a_0 </tex>. Значит в <tex>[a_0,\cdots, a_{n+1}]</tex> <tex>F_{n+1}+F_n = F_{n+2}</tex> слагаемых.
}}
{{Теорема
|id=theorem1
|about=1
|statement=
<tex>[a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] </tex>
|proof=
База: <tex>[a_0] = a_0 = [a_0]</tex>
Пусть верно для всех <tex>m < n </tex>. Докажем для <tex>n</tex>.
<tex>[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]</tex>
Обобщим последнюю формулу и докажем по индукции. Пусть верно :
<tex>[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]</tex>.
Докажем для больших <tex> k </tex> :
<tex> [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]</tex>.
Используя условие теоремы для <tex>k < n-1</tex> получаем :
<tex> 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}]</tex>
Следовательно получаем :
<tex>[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]</tex>.
}}
{{Лемма
|id=lemma3
|about=3
|statement=
<tex>[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}]</tex>.
|proof=
Эта формула аналогична формуле из [[#lemma1|Леммы 1]], за исключением того, что <tex>a_n</tex> "отщепляются" с другого конца.
Для получения формулы достаточно скомбинировать результаты [[#lemma1|Леммы 1]] и [[#theorem1|Теоремы 1]].
}}
{{Лемма
|id=lemma4
|about=4
|statement=
<tex>P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}</tex>.
|proof=
<tex>\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)</tex> по рекуррентным соотношениям для числителей и знаменателей подходящих дробей.
Возьмём детерминант левой и правой части. Получим : <tex>(P_nQ_{n-1}-P_{n-1}Q_n)(-1)=P_{n+1}Q_n-P_nQ_{n+1}</tex>. Так как при <tex>n=1:P_1Q_0-P_0Q_1=1</tex> то получаем, что лемма доказана.
}}
