Цепная дробь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (тестирование)
Строка 12: Строка 12:
 
Отсюда видим, что <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> \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>.
 
Следовательно <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>.
{{Лемма
+
{{Лемма{{void}}
 
|statement=
 
|statement=
 
В <tex>[a_0,\cdots, a_n]</tex> <tex>F_{n+1}</tex> слагаемых.
 
В <tex>[a_0,\cdots, a_n]</tex> <tex>F_{n+1}</tex> слагаемых.

Версия 12:31, 28 июня 2010

Эта статья находится в разработке!


Определение:
Цепная дробь — это выражение вида

[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]\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] \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][a_0,\cdots, a_n][/math] [math]F_{n+1}[/math] слагаемых.
Доказательство:
[math]\triangleright[/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]
Теорема:
[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]