Доказать равенство.Последовательность Фарея.

[CliniqueHappy]

Обозначим длину последовательности Фарея $F_{n}$через $F\left ( N \right )$Докажите, что$ \sum_{n=1}^{N} F\left ( \left \lfloor \frac{N}{n} \right \rfloor \right ) = \frac{N\left ( N+3 \right )}{2}$

[svv]

Что такое длина последовательности? Многие считают, что последовательности всегда бесконечные.
В обозначении $F(N)$ что понимается под $F$ и что под $N$?

[CliniqueHappy]

svv в сообщении #1273530 писал(а):

Что такое длина последовательности? Многие считают, что последовательности всегда бесконечные.
В обозначении $F(N)$ что понимается под $F$ и что под $N$?

Исправил.Можно найти кол-во целочисленных точек в квадрате с вершинами $\left ( 1;1 \right ),\left ( 1;N \right ),\left ( N;1 \right ),\left ( N;N \right )$, так-же использовать ф-цию мебиуса. В подсказках написано, ну а дальше как быть?
$\sum_{n=1}^{N}\psi\left ( \left \lfloor \frac{N}{n} \right \rfloor \right )=N^{2} $ Где $\psi \left ( N \right )$ количество точек с взаимно простыми координатами в вышеупомянутом квадрате.

[CliniqueHappy]

Что никто не знает как решить это?

[svv]

Посмотрите английскую Википедию, статью Farey sequence, пункт 3.1 Sequence length and index of a fraction. Это, по крайней мере, поможет свести вывод формулы к более простым вещам.

[CliniqueHappy]

$F_{n}=\frac{1}{2}\left ( 3+\sum_{d=1}^{n}\mu \left ( d \right )\left \lfloor \frac{n}{d} \right \rfloor^{2} \right )$ Далее применяется формула обращения мебиуса $g(n)=\sum_{n=1}^{n}f\left ( d \right )$ тогда $g(n)=\sum_{n=1}^{n}\mu \left ( d \right )g\left ( \frac{n}{d} \right )$ и получается искомое выражение в правой части, что здесь $g(n)$$n^{2}$? Не понятен этот переход $F_{n}=\frac{1}{2}\left ( n+3 \right )n-\sum_{d=2}^{n}F_{\left \lfloor \frac{n}{d} \right \rfloor}$

[svv]

Я запишу чуть иначе, и Вы сами догадаетесь:

$$\begin{matrix}f(n)=\sum\limits_{d=1}^n \mu(d) g\left(\frac n d\right)&\Leftrightarrow&g(n)=\sum\limits_{d=1}^n f\left(\frac n d\right)\\\rotatebox[c]{-90}{\(\mathsf{\rightarrow}\)}&&\rotatebox[c]{-90}{\(\mathsf{\rightarrow}\)}\\2|F_{\lfloor n \rfloor}|-3=\sum\limits_{d=1}^n \mu(d) {\lfloor \frac n d \rfloor}^2&\Leftrightarrow&{\lfloor n\rfloor}^2=\sum\limits_{d=1}^n \left( 2|F_{\lfloor \frac n d \rfloor}| -3\right)\end{matrix}$$

[CliniqueHappy]

svv в сообщении #1274157 писал(а):

Я запишу чуть иначе, и Вы сами догадаетесь:

$$\begin{matrix}f(n)=\sum\limits_{d=1}^n \mu(d) g\left(\frac n d\right)&\Leftrightarrow&g(n)=\sum\limits_{d=1}^n f\left(\frac n d\right)\\\rotatebox[c]{-90}{\(\mathsf{\rightarrow}\)}&&\rotatebox[c]{-90}{\(\mathsf{\rightarrow}\)}\\2|F_{\lfloor n \rfloor}|-3=\sum\limits_{d=1}^n \mu(d) {\lfloor \frac n d \rfloor}^2&\Leftrightarrow&{\lfloor n\rfloor}^2=\sum\limits_{d=1}^n \left( 2|F_{\lfloor \frac n d \rfloor}| -3\right)\end{matrix}$$

Спасибо большое все понятно. Поленился расписать(

(Оффтоп)

Перед бегом все мысли о беге, а после бега о результатах)

[svv]

(Оффтоп)

Но зато во время бега прекрасно можно погрузиться в задачу.