Простейшие сведения о непрерывных дробях и их свойствах

Пусть число $\usepackage{amsfonts} x \in \mathbb {R}$. Тогда обозначим через $q_1$ наибольшее целое число, меньшее $x$. Если $x$ не целое число, то мы получим равенство вида $\displaystyle x = q_1 + \frac{1}{x_1}$, так как дробь $\displaystyle \frac{1}{x_1} < 1$, то $ x_1>1 $, и тогда аналогично для $x_1$ находим такое целое $q_2 < x_1$, получаем $\displaystyle x_1 = q_2 + \frac{1}{x_2}$, возвращаясь к первому равенству $\displaystyle x = q_1 + \frac{1}{\displaystyle q_2 + \frac{1}{x_2}}$. Продолжая этот процесс будем получать представления последующих $\displaystyle x_k:$ $$x_2 = q_3 + \frac{1}{x_3}, $$ $$x_3 = q_4 + \frac{1}{x_4},$$ $$\ldots$$ $$x_i = q_{i+1} + \frac{1}{x_{i+1}},$$ $$\ldots$$

В итоге и получим непрерывную дробь: $$\usepackage{amsmath} \begin{multline*} \displaystyle x = q_1 + \frac{1}{\displaystyle q_2+ \frac{1}{q_3+\cdots}} \\ \ddots \\ \cdots + \frac{1}{\displaystyle q_{n-1} + \frac{1}{\displaystyle q_{n}+\frac{1}{x_n}}}.
\end{multline*}$$

Далее, нам стоит рассмотреть два случая: первый — $\usepackage{amsfonts} x \in \mathbb {Q}$, т. е. $x$ — рациональное число и второй — $\usepackage{amsfonts} x \in \mathbb {R} \setminus \mathbb {Q}$, т. е. $x$ — иррациональное число. Почему важны именно эти случаи?

По определению, рациональное число представимо в виде несократимой дроби $\displaystyle \frac{m}{n}$, где $\usepackage{amsfonts} m \in \mathbb {Z}, \; n \in \mathbb {N}$, а, значит, и разложение, представленное сверху, должно быть конечным и, более того, может быть получено благодаря алгоритму Евклида.

С иррациональным числом получим ситуацию обратную — процесс можно будет продолжать неограниченно долго т. к. на каждом этапе $x_i$ будет иррационально.

Пусть $x_i$ — иррационально, тогда $$\displaystyle x_i = q_{i+1} + \frac{1}{x_{i+1}},$$ сумма $\displaystyle q_{i+1} + \frac{1}{x_{i+1}}$ — иррациональна, однако $q_{i+1}$ является целым по определению, которое мы дали ему выше $\Rightarrow$ дробь $\displaystyle \frac{1}{x_{i+1}}$ должна быть иррациональной. А это означает, что и $x_{i+1}$ — иррациональное число.

Т. е. получаем, что иррациональность $x_i$ влечёт за собой иррациональность $x_{i+1}$, а т. к. изначальное число $x$ — иррационально, то и все $x_j,$ при $j = 1,2,3 \ldots$ — иррациональны.

Как было упомянуто ранее, если $\usepackage{amsfonts} x \in \mathbb {Q}$, то его разложение в непрерывную дробь можно получить с помощью алгоритма Евклида.

Перед описанием алгоритма стоит ввести понятие неполного частного — это целые числа вида $q_i, \; i = \overline{1,n}$.

Опишем сам алгоритм:

Суть алгоритма заключается в том, что на каждом шаге мы будем непосредственно получать одно из неполных частных — $q_i$, а также отношение $\displaystyle \frac{r_{i}}{r_{i-1}}$ (начиная со второго шага).

Пусть нам задано рациональное число, тогда его можно записать в виде несократимой дроби $\displaystyle \frac{m}{n}$, где $\usepackage{amsfonts} m \in \mathbb {Z}, \; n \in \mathbb {N}$. Тогда, первый шаг: $$m=nq_1 + r_1 \Rightarrow \displaystyle \frac{m}{n} = q_1 + \frac{1}{\displaystyle \frac{m}{r_1}},$$ узнали значение $q_1$, а так же получили возможность вычислить значение $r_1$. Второй шаг: $$n = r_1q_2+r_2 \Rightarrow \displaystyle \frac{n}{r_1} = q_2 + \frac{1}{\displaystyle \frac{r_1}{r_2}},$$ узнали значение $q_2$, а так же получили возможность вычислить значение $r_2$. Продолжая алгоритм далее: $$r_1 = r_2q_3+r_3 \Rightarrow \displaystyle \frac{r_1}{r_2} = q_3 + \frac{1}{\displaystyle \frac{r_2}{r_3}}, \\ r_2 = r_3q_4+r_4 \Rightarrow \frac{r_2}{r_3} = q_4 + \frac{1}{\displaystyle \frac{r_3}{r_4}},\\ \cdots \\r_{n-2} = r_{n-1}q_n+r_n \Rightarrow \frac{r_{n-2}}{r_{n-1}} = q_n + \frac{1}{\displaystyle \frac{r_{n-1}}{r_n}}, \\ r_{n-1} = r_nq_{n+1}, \frac{r_{n-1}}{r_n} = q_{n+1}.$$ Заканчиваем алгоритм тогда, когда получим, что очередная дробь $\displaystyle \frac{r_{i-1}}{r_{i}}$ будет целым числом и, соответственно, $q_{i+1}$ будет полным частным.

Так как найдены все неполные частные, то дробь $\displaystyle \frac{m}{n}$ можно представить в виде: $$\usepackage{amsmath} \begin{multline*} \displaystyle x = q_1 + \frac{1}{\displaystyle q_2+ \frac{1}{q_3+\cdots}} \\ \ddots \\ \cdots + \frac{1}{\displaystyle q_{n-1} + \frac{1}{\displaystyle q_{n}+\frac{1}{q_{n+1}}}}.
\end{multline*}$$

С помощью алгоритма Евклида есть возможность найти разложение в непрерывную дробь, однако, иногда промежуточные результаты важнее конечного, а именно: $$\displaystyle \delta_1 = q_1, \; \delta_2 = q_1 + \frac{1}{q_2}, \; \delta_3 = q1 + \frac{1}{q_2 + \displaystyle \frac{1}{q_3}}, \; \ldots$$ $\delta_i$ называются подходящими дробями. Несложно заметить зависимость $\delta_{i+1}$ от $\delta_i$ — если в записи $\delta_i $ число $ q_i$ заменить на сумму $\displaystyle q_i + \frac{1}{q_{i+1}}$, то мы получим $\delta_{i+1}.$

Подходящие дроби будут нас интересовать тем, что они образуют последовательность, которая приближается к изначальному числу. Понятно, что зная все неполные частные (после применения алгоритма Евклида) можно вычислить значения всех подходящих дробей, однако, это не очень удобно и долго.

Введем специальные обозначения для нахождения значений подходящих дробей: $\displaystyle \delta_i = \frac{P_i}{Q_i}$. При этом положим, что $P_0=1, \; P_1 = q_1$ и $Q_0=0, \; Q_1 = 1$. Так же стоит отметить, что в силу того, что для рационального числа $\displaystyle x = \frac{m}{n} $ непрерывная дробь конечна, то и количество подходящих дробей будет конечно, а это означает что существует равенство $\displaystyle \frac{m}{n} = \frac{P_i}{Q-i}$. А так как подходящие дроби так же являются несократимыми, то равенство можно упростить до $m = P_i$ и $n = Q_i$. Тогда получим, что: $$\displaystyle \delta_1 = \frac{q_1}{1} = \frac{P_1}{Q_1}, $$ $$ \delta_2 = q_1 + \frac{1}{q_2} = \frac{q_2 q_1+1}{q_2 \cdot 1 + 0} = \frac{q_2 P_1+P_0}{q_2 Q_1 + Q_0} = \frac{P_2}{Q_2}, $$ $$ \delta_3 = q1 + \frac{1}{q_2 + \displaystyle \frac{1}{q_3}} = \frac{q_1 \left( q_2 + \displaystyle \frac{1}{q_3} \right) +1}{q_2 + \displaystyle \frac{1}{q_3}} = \frac{q_1 \left( q_2 q_3 + 1\right)+q_3}{q_2 q_3 +1} = $$ $$ = \frac{q_1 q_2 q_3 + q_1 +q_3}{q_2 q_3} = \frac{q_3 \left( q_1 q_2 + 1 \right) + q_1}{q_3 q_2 + 1} = \frac {q_3 P_2 + P_1}{q_3 Q_2 + Q_1}.$$

Несложно заметить рекуррентное выражение для $\displaystyle \frac{P_i}{Q_i}$: $$P_i = q_i P_{i-1} + P_{i-2} \\ Q_i = q_i Q_{i-1} + Q_{i-2}. $$ Докажем это с помощью математической индукции.

База индукции: $\delta_3 = \displaystyle \frac{P_3}{Q_3} = \frac{q_3 P_2 + P_1}{q_3 Q_2 + Q_1}$.

Предположим, что $\delta_k = \displaystyle \frac{P_k}{Q_k} =\frac{q_k P_{k-1} + P_{k-2}}{q_k Q_{k-1} + Q_{k-2}}$.

Тогда: $$\delta_{k+1} = \frac{\displaystyle \left(q_k + \frac{1}{q_{k+1}} \right) P_{k-1} + P_{k-2} }{\displaystyle \left(q_k + \frac{1}{q_{k+1}} \right) Q_{k-1} + Q_{k-2}} = \frac {\displaystyle \frac{P_{k-1}}{q_{k+1}} + q_k P_{k-1} + P_{k-2}}{\displaystyle \frac{Q_{k-1}}{q_{k+1}} + q_k Q_{k-1} + Q_{k-2}} = $$ (выполним замену по предположению индукции) $$\displaystyle = \frac{\displaystyle \frac{P_{k-1}}{q_{k+1}} + P_k}{\displaystyle \frac{Q_{k-1}}{q_{k+1}} + Q_k} = \frac{P_{k-1} + P_k q_{k+1}}{Q_{k-1} + Q_k q_{k+1}} = \frac{P_{k+1}}{Q_{k+1}},$$ что и требовалось доказать.

Имеет место следующее свойство подходящих дробей:

Лемма. При $n > 0$ имеет место равенство $P_n Q_{n-1} — P_{n-1}Q_n = (-1)^n$.

Проверим значение левой части при $n = 1$, получим: $$P_1 Q_0 — P_0 Q_1 = -1,$$ далее вычислим значение левой части при увеличении индекса на 1, т. е. при $n+1,$ получим: $$ P_{n+1} Q_n — P_n Q_{n+1} = \left( q_{n+1} P_n + P_{n-1} \right) Q_n — P_n \left( q_{n+1} Q_n + Q_{n-1} \right) = \\ = P_{n-1} Q_n — P_{n} Q_{n-1}, $$ получили выражение противоположное заданному в условии. А, значит, при изменении индекса на единицу меняется и знак выражения, а т. к. первое значение $-1$, то и получаем требуемое.

Примеры решения задач

Рассмотрим примеры задач в которых могут быть использованы непрерывные дроби. Рекомендуется сначала решать примеры самому, а только затем сверить решение с представленным ниже.

  1. Разложить число $\displaystyle x = \frac{89}{13}$ в непрерывную дробь.
    Решение

    Применяя алгоритм Евклида получим: $$ 89 = 13 \cdot 6 + 11, \; q_1 = 6;$$ $$13 = 11 \cdot 1 + 2, \; q_2 = 1; $$ $$11 = 2 \cdot 5 + 1, \; q_3 = 5;$$ $$2 = 1 \cdot 2, \; q_4 = 2.$$ Нашли все $q_i \Rightarrow$ можем записать $x$ как непрерывную дробь: $$\displaystyle x = 6 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 5 + \frac{1}{2}}}$$

  2. Найти все подходящие дроби числа $\displaystyle x = \frac{127}{19}$.
    Решение

    Для этого используем рекуррентные формулы подходящих дробей. Воспользуемся алгоритмом Евклида для поиска всех $q_i$: $$ 127 = 19 \cdot 6 + 13, \; q_1 = 6;$$ $$19 = 13 \cdot 1 + 6, \; q_2 = 1; $$ $$13 = 6 \cdot 2 + 1, \; q_3 = 2;$$ $$6 = 1 \cdot 6, \; q_4 = 6.$$
    Далее будем выписывать подходящие дроби в порядке возрастания индекса: $$\displaystyle \delta_1 =\frac{q_1}{1} = \frac{6}{1}$$ $$\displaystyle \delta_2 =\frac{q_2 P_1 + P_0}{q_2 Q_1 + Q_0} = \frac{1 \cdot 6 + 1}{1 \cdot 1 + 0} = \frac{7}{1},$$ продолжая расчеты получим: $$\displaystyle \delta_3 = \frac{2 \cdot 7 + 6}{2 \cdot 1 + 1} = \frac{20}{3}$$ и, наконец, $$\displaystyle \delta_4 = \frac{6 \cdot 20 + 7}{6 \cdot 3 + 1} = \frac{127}{19} = x,$$как и ожидалось четвертая подходящая дробь равна заданному числу, т. к. максимальный индекс $q_i$ был равен четырём.

  3. Разложить в непрерывную дробь иррациональное число $\sqrt{7}$.
    Решение

    Для этого воспользуемся разложением, которое было представлено в теме первым. А именно
    $$\displaystyle x_0 = \sqrt{7} = q_1 + \frac{1}{x_1} = 2 + \left( \sqrt{7} — 2 \right)$$ $$\displaystyle \frac{1}{x_1} = \sqrt{7} — 2 \Rightarrow x_1 = \frac{1}{\sqrt{7}-2} = \frac{\sqrt{7}+2}{3} = 1 + \frac{\sqrt{7}-1}{3} = 1 + \frac{1}{x_2},$$ $$\displaystyle x_2 = \frac{3}{\sqrt{7}-1} = \frac{3 \left( \sqrt{7} + 1 \right) }{6} = \frac{\sqrt{7}+1}{2} = 1 + \frac{\sqrt{7} — 1}{2} = 1 + \frac{1}{x_3},$$ $$\displaystyle x_3 = \frac{2}{\sqrt{7}-1} = \frac{2 \left( \sqrt{7} + 1 \right) }{6} = \frac{\sqrt{7}+1}{3} = 1 + \frac{\sqrt{7} — 2}{3} = 1 + \frac{1}{x_4},$$ $$\displaystyle x_4 = \frac{3}{\sqrt{7} — 2} = \frac{3 \left(\sqrt{7} + 2 \right) }{3} = \sqrt{7} + 2 = 4 + \left( \sqrt{7} — 2 \right).$$
    Однако, слагаемое вида $\sqrt{7} — 2$ у нас уже было, а значит мы пришли к циклу. Выпишем все неполные частные, они же — целые части дробей. Получим: $\sqrt{7} = \left[2,\: \overline{1, \: 1, \: 1, \: 4} \right]$ — часть чисел находятся под чертой т. к. они находятся в цикле.

  4. Восстановить по заданным $q_i = \left[10, \: 4, \: 3, \: 2, \: 4 \right]$ рациональное число $x$.
    Решение

    Для этого воспользуемся разложением, полученным в результате алгоритма Евклида:
    Получим дробь: $$10 + \frac{1}{\displaystyle 4 + \frac{1}{\displaystyle 3 + \frac{1}{\displaystyle 2 + \frac{1}{4}}}},$$ её значением и будет искомым $x$. Посчитав значение этой дроби получим, что $\displaystyle x = \frac{1361}{133}.$

  5. Восстановить по заданным $q_i = \left[\overline{2, \: 9} \right]$ иррациональное число $x$.
    Решение

    Так как число $x$ — иррациональное, то его непрерывная дробь будет бесконечной, поэтому воспользоваться методом из предыдущего примера не получится. Однако, так как мы видим по данным $q_i$, что дробь зацикливается, то можем записать следующие выражение: $$\displaystyle x = 2 + \frac{1}{\displaystyle 9 + \frac{1}{x}}$$ приведем дробь к квадратному уравнению: $$9x^2 — 18x + 2 = 0,$$ $$D = 324 + 72 = 396, \;
    \displaystyle x_{1,2} = 1 \pm \frac{\sqrt{396}}{18}.$$ Т. к. целая часть числа равна 2, то вариант $\displaystyle x = 1-\frac{\sqrt{396}}{18}$ можно отбросить. И окончательный ответ: $$\displaystyle x = 1 + \frac{\sqrt{396}}{18}$$

Простейшие сведения о непрерывных дробях и их свойствах

Тест на знание темы «Простейшие сведения о непрерывных дробях и их свойствах».

Смотрите также

  1. Виноградов И.М. Основы теории чисел. cтр. 14-18
  2. Арнольд В.И. Цепные дроби.
  3. Теоретические материалы основанные на конспекте и лекциях Белозерова Г.С.

М749* Задача на различные доказательства неравенства

Задача из журнала «Квант»(1982 год, 6 выпуск)

Условие

a) Докажите, что если $x_1, x_2, x_3$— положительные числа, то $$\frac{x_1}{x_2 + x_3} + \frac{x_2 }{x_3+x_1} + \frac{x_3}{x_1 + x_2} \ge \frac{3}{2};$$ при каком условии то неравенство превращается в равенство?

б) Докажите, что если $x_1, x_2,…,x_n (n ≥ 4)$ — положительные числа, то

$$\frac{x_1}{x_2 + x_n} + \frac{x_2}{x_3 + x_1} + … + \frac{x_{n-1}}{x_n + x_{n-2}} + \frac{x_n}{x_1 + x_{n-1}} \ge 2.$$ причем равенство возможно только при $n = 4.$

в) Докажите, что при $n>4$ неравенство пункта б) является точным в том смысле, что ни при каком $n$ число $2$ в правой части нельзя заменить на большее.

А. Прокопьев

Решение

a) Пусть $ a=x_2+x_3, b=x_3+x_1, c=x_1+x_2.$ Тогда $x_1=\frac{b+c-a}{2},$ $x_2 = \frac{a+c-b}{2},$ $x_3=\frac{a+b-c}{2}, $ и левая часть неравенства перепишется так: $ \frac{b+c-a}{2a}+\frac{a+c-b}{2b}+\frac{a+b-c}{2c}=$ $\frac{1}{2}(\frac{b}{a}+\frac{a}{b})+\frac{1}{2}(\frac{c}{a}+\frac{a}{c})+\frac{1}{2}(\frac{b}{c}+\frac{c}{b})-\frac{3}{2}.$ Каждая из скобок в этом выражении, не меньше $2$ в силу известного неравенства $x + \frac{1}{x} \ge 2$ при $x > 0.$ Поэтому вся левая часть не меньше $3-\frac{3}{2} = \frac{3}{2}.$ А так как $x + \frac{1}{x} = 2$ только при $x = 1,$ доказанное неравенство обращается в равенство только при $a = b = c.$

б) Докажем неравенство индукцией по $n.$ При $n = 4$ оно очевидно: $$\frac{x_1}{x_2+x_4}+\frac{x_2}{x_3+x_1} + \frac{x_3}{x_4+x_2}+\frac{x_4}{x_1+x_3} = \frac{x_1+x_3}{x_2+x_4}+\frac{x_2+x_4}{x_1+x_3} \ge 2$$ равенство возможно в том и в только в том случае, когда $x_1 + x_3 = x_2 + x_4.$

Докажем теперь неравенство для произвольных положительных чисел $ x_1, …, x_{n + 1},$ предполагая, что оно справедливо для любых $ n (n \ge 4)$ положительных чисел. Выберем наименьшее из чисел $ x_1, …, x_{n + 1}.$ Поскольку они входят в неравенство симметрично, можно, не ограничивая общности, считать, что это $ x_{n + 1}.$ Тогда $x_{n+1} > 0,$ $x_{n+1} \le x_n$ и $x_{n + 1} \le x_1,$ и поэтому $$\frac{x_1}{x_2 + x_{n+1}} + \frac{x_2}{x_3+x_1} + … + \frac{x_n}{x_{n + 1}+x_{n- 1}}+$$ $$ +\frac{x_{n+1}}{x_1+x_n}> \frac{x_1}{x_2+x_n}+\frac{x_2}{x_3 + x_1} + … + \frac{x_n}{x_1 + x_{n-1}} \ge 2 $$

(последнее неравенство выполняется по предположению индукции). Попутно получаем, что при $n>4$ равенство невозможно.

в) Числа $x_1, …, x_n$ удобно расставлять по окружности; тогда каждое слагаемое в левой части рассматриваемого неравенства есть одно из этих чисел, деленное на сумму двух соседних с ним. При $n = 2k$ определим $x_i$ так, как показано на рисунке 1, а при $n = 2k+1$ — как на рисунке 2.

 

В первом случае получим сумму $$2(\frac{1}{q+1}+ \frac{q}{q^2+1}+\frac{q^2}{q^3+q}+ … + \frac{q^{k-1}}{q^{k-1}+q^{k-2}})= 2(1 + \frac{(k-2)q}{g^2+1}),$$

а во втором —

$$ \frac{1}{2q} + 2(\frac{q}{q^2+1} + \frac{q^2}{q^3 + q} + … + \frac{q^k}{q^k+q^{k-1}})=\frac{1}{2q} + \frac{2(k-1)q}{q^2+1}-\frac{2q}{q+1}=$$ $$=2+(\frac{1}{2q} + \frac{2(k-1)q}{q^2+1} — \frac{2}{q+1}).$$

В обоих случаях при достаточно большом $q$ значение левой части будет сколь угодно близко к $2$, поэтому число $2$ в неравенстве на большее заменить нельзя.

А. Егоров

 

М697. Пузатость прямоугольника

Задача

разделение квадрата на прямоугольники

Назовем пузатостью прямоугольника отношение его меньшей стороны к большей (пузатость квадрата равна 1). Докажите ,что, как бы не резать квадрат на прямоугольники, сумма их пузатостей будет не меньше 1.

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

Будем считать что длина стороны квадрата равна 1. Тогда пусть мы разбили квадрат на $ n$ прямоугольников размерами $ a_k\times b_k$ причем при всех $ k$ $ a_k\leq b_k$

Одно из возможных разбиений квадрата на прямоугольники

тогда:

$ {\textstyle1\geq b_k\Rightarrow\frac1{b_k}\geq b_k\Rightarrow\frac{a_k}{b_k}\geq a_k\times b_k\Rightarrow\sum_{k=1}^n}\frac{a_k}{b_k}\geq{\textstyle\sum_{k=1}^n}a_k\times b_k=1$ (сумма $ {\textstyle\sum_{k=1}^n}a_k\times b_k$ является суммой площадей прямоугольников и по свойству площади равна площади квадрата (то есть 1)).

А это значит что:

$ {\textstyle\sum_{k=1}^n}\frac{a_k}{b_k}\geq1 $ . А это и значит, что как бы не резать квадрат на прямоугольники, сумма их пузатостей будет не меньше 1.

Что и требовалось доказать.