Цепная дробь

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

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

Цепная дробь — это выражение вида [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]