Теорема Фарея-Коши [Теория чисел]

[Whitaker]

Здравствуйте, уважаемые друзья!
Читаю книгу К. Чандрасекхарана "Введение в АТЧ" и там доказывается следующее замечательное свойство последовательности Фарея.

Теорема (Фарей-Коши). Если $l/m$ непосредственно следует за $h/k$ в последовательности Фарея $F_N$, то $kl-hm=1$
Она доказывается индукцией. Пусть $a/b$ - несократимая правильная дробь, не принадлежащая $F_N$. Тогда $b\geqslant N+1$ и дробь $a/b$ должна лежать между некоторыми двумя последовательными дробями $h/k$ и $l/m$ в последовательности Фарея $F_N$. Не буду все подробно писать. Они проводят некоторые рассуждения и получают, что $\frac{a}{b}=\frac{h+k}{l+m}$, т.е. $a/b$ - медианта дробей $h/k$ и $l/m$, т.е. $\frac{h}{k}<\frac{h+l}{k+m}<\frac{l}{m}$
Дробь $a/b$, очевидно, удовлетворяет теореме относительно соседних дробей $h/k$ и $l/m$, так как по предположению индукции для $F_N$ мы имеем $kl-hm=1$

Но последний абзац мне непонятен. Объясните пожалуйста его смысл.
Но ведь для того, чтобы доказательство было полностью правильным нужно показать, что дроби $\frac{h}{k}, \frac{h+l}{k+m},\frac{l}{m}$ являются последовательными в $F_{N+1}$. Но как это сделать?

С уважением, Whitaker.

[RIP]

Там предполагается, что теорема справедлива для $F_N$, и доказывается для $F_{N+1}$.

Дальше рассуждения немного запутанные, но в итоге из них следует, что если $a/b\in F_{N+1}\setminus F_N$, то её соседями в $F_{N+1}$ являются некоторые дроби $h/k,l/m\in F_N$, а $a/b$ является их медиантой. Собственно, смысл последнего абзаца в том, что $h/k,a/b$ и $a/b,l/m$ — это две пары соседних дробей в $F_{N+1}$, и для них проверка нужного свойства сводится к равенству $kl-hm=1$ (поскольку $a$ и $b$ выражаются через $h,k,l,m$).

Это доказывает нужное свойство для всех пар соседей в $F_{N+1}$, в которых хотя бы один из соседей не лежит в $F_N$ (причём рассуждения показывают, что тогда второй обязательно лежит). Для остальных пар работает индукция.

[Whitaker]

RIP в сообщении #623980 писал(а):

но в итоге из них следует, что если $a/b\in F_{N+1}\setminus F_N$, то её соседями в $F_{N+1}$ являются некоторые дроби $h/k,l/m\in F_N$.

Но где они это получили? Доказательство немного запутанное.

[RIP]

Их рассуждения (самый конец) показывают, что если дробь из $F_{N+1}\setminus F_N$ лежит между соседними в $F_N$ дробями, то она является их медиантой, а медианта единственна, так что между $h/k$ и $l/m$ не может быть никакой другой дроби, кроме $a/b$. Просто это рассуждение они проглотили.

-- Чт 27.09.2012 16:08:53 --

"Их" в смысле "его".

-- Чт 27.09.2012 16:21:20 --

Т.е. что там делается. Берётся $a/b\notin F_N$. Она лежит между какими-то соседними в $F_N$ дробями $h/k$ и $l/m$. Дальше он колдует и получает некоторые формулы для $a$ и $b$. Потом показывается, что если при этом $a/b\in F_{N+1}$, то есть $b=N+1$, то $a,b$ однозначно выражаются через $h,k,l,m$.

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

[Whitaker]

RIP
я прочитал полностью доказательство несколько раз и мне почти все понятно за исключением только одного места: между $h/k$ и $l/m$ не может никакой дроби, кроме $a/b$.
Но понять этот момент никак я не могу.
Можете ли Вы мне ее объяснить?

[ex-math]

Whitaker
У всех остальных (их вид $\frac{\lambda h+\mu l}{\lambda k+\mu m}$) знаменатель будет больше, чем у $\frac ab$, у которой $\lambda=\mu=1$, так что в $F_{N+1}$ они не войдут.

[Whitaker]

ex-math
Это я вроде осознал.
Я не могу понять почему между дробями $h/k$ и $l/m$ не может быть никакой дроби кроме $\frac{h+l}{k+m}$.
Может быть я какой-то момент не понимаю.

[RIP]

Ну, смотрите. Будем рассуждать от противного. Пусть есть ещё такая дробь. Те же рассуждения дают, что дробь имеет вид $\frac{\lambda h+\mu l}{\lambda k+\mu m}$ (с этими же $h,k,l,m$). Причём её знаменатель уже будет $>N+1$, поскольку все дроби со знаменателем $\le N+1$ мы знаем: в книге доказывается, что такой дробью может быть только медианта. Это значит, что дробь не лежит в $F_{N+1}$. Противоречие. Занавес.

[Whitaker]

RIP
начинаю кое-что понимать, но если Вы не против задам такой вопрос:
Там говорится, что $b\leqslant m+k$, где $b=\lambda m+\mu k$ только в трех случаях $(\lambda, \mu)=(0,1), (1,0), (1,1)$ и показывает, что пары $(0,1), (1,0)$ не подходят (это понятно).
А почему случай $b>m+k$ вообще не рассматривается? Или я чего-то не догоняю?!

[RIP]

Этот случай не нужен, поскольку нам интересен только случай $b=N+1\le m+k$.

[Whitaker]

А почему этот случай нам не интересен $b=N+1>m+k$?
В чем подвох?

[RIP]

Потому что $m+k>N$. Иначе бы между $h/k$ и $l/m$ можно было бы вставить дробь $(h+l)/(k+m)$ со знаменателем $k+m\le N$, что противоречит тому, что дроби выбирались соседними в $F_N$.

Я бы изложил док-во немного по-другому. Возьмём произвольные соседние дроби в $F_N$. Допустим, что между ними затесалась какая-то дробь из $F_{N+1}$ (в принципе, можно из Фареев с большими номерами, но они нам всё равно неинтересны). Дальше бла-бла-бла… формулы… бла-бла-бла… Опа! Такая дробь может быть только одна. Хотя не знаю.

Между прочим, там попутно доказан более сильный факт:
Чтобы из $F_N$ получить $F_{N+1}$, нужно между каждой парой соседних в $F_N$ дробей $h/k<l/m$ с условием $k+m=N+1$ вставить их медианту.

[Whitaker]

RIP
Большое Вам спасибо за помощь!
Благодарю Вас!