Рекуррентное соотношение и подходящие дроби

[nnosipov]

Пусть $m \geqslant 5$ --- нечетное число. Положим $L_1=m$ и $L_{k+1}=L_k^2-2$ для $k \geqslant 1$. Докажите, что $L_k=P_{2^k-1}$, где $P_j/Q_j$ --- $j$-я подходящая дробь для $\sqrt{m^2-4}$.

Примечание. Нумерация подходящих дробей начинается с нуля.

[RIP]

Лобовое решение.

Положим $\lambda=\frac{m+\sqrt{m^2-4}}{2}$, так что $L_k=\lambda^{2^{k-1}}+\lambda^{-2^{k-1}}=A_{2^{k-1}}$, где $A_n=\lambda^n+\lambda^{-n}=mA_{n-1}-A_{n-2}$.

Цепная дробь: $\sqrt{m^2-4}=\left[m-1;\overline{1,\frac{m-3}{2},2,\frac{m-3}{2},1,2m-2}\right]$.

Лобовым вычислением проверяем:
\begin{align*} p_{6n}&=A_{3n+1}-\frac{A_{3n}}{2},\\ p_{6n+1}&=A_{3n+1},\\ p_{6n+2}&=\frac{A_{3n+2}-A_{3n+1}}{2},\\ p_{6n+3}&=A_{3n+2},\\ p_{6n+4}&=\frac{A_{3n+3}}{2}-A_{3n+2},\\ p_{6n+5}&=\frac{A_{3n+3}}{2}. \end{align*}

В частности: $p_{2^k-1}=A_{2^{k-1}}=L_k$.

(Оффтоп)

Рекуррентное соотношение для $A_n$ намекает на подходящие дроби для цепной дроби с минусами:

$$\lambda=m-\cfrac{1}{m-\cfrac{1}{m-\dotsb}}.$$

[nnosipov]

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

Лобовое решение.

А как Вы так быстро угадали весь комплект формул? Подозрительно как-то Я вот честно решал систему рекуррентных соотношений.

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

[RIP]

nnosipov в сообщении #1490811 писал(а):

А как Вы так быстро угадали весь комплект формул?

Подогнал под ответ. В условии фактически дано $p_{6n+1}=A_{3n+1}$ и $p_{6n+3}=A_{3n+2}$. Остальные получаются из рекуррентных соотношений.

[nnosipov]

Спасибо, понятно

[RIP]

nnosipov в сообщении #1490811 писал(а):

Где об этом явно написано, не подскажете?

Ссылку не знаю, но можно совсем в лоб с помощью формулы

$$\begin{pmatrix}p_n&p_{n-1}\\q_n&q_{n-1}\end{pmatrix}=\begin{pmatrix}a_0&1\\1&0\end{pmatrix}\begin{pmatrix}a_1&1\\1&0\end{pmatrix}\dotsm\begin{pmatrix}a_n&1\\1&0\end{pmatrix}.$$

Если последовательность $a_n$ периодическая, то фактически задача сводится к возведению матрицы $2\times2$ в степень. Я сначала так и хотел, но терпения не хватило.

[nnosipov]

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

но терпения не хватило

Честно говоря, у меня тоже. (Решать-то я решал, но не дорешал, больно громоздко.)

А формула действительно помогает осознать факт. Наверное, это и есть самое простое объяснение.

[maxal]

nnosipov в сообщении #1490794 писал(а):

Пусть $m \geqslant 5$ --- нечетное число. Положим $L_1=m$ и $L_{k+1}=L_k^2-2$ для $k \geqslant 1$. Докажите, что $L_k=P_{2^k-1}$, где $P_j/Q_j$ --- $j$-я подходящая дробь для $\sqrt{m^2-4}$.

Это же балб-гам Люка-Лемер (почти)

[nnosipov]

maxal
Да, ассоциация с тестом Люка-Лемера мне тоже бросилась в глаза. А наблюдение с подходящими дробями --- это мне сообщили. Я поэкспериментировал с четными $m \geqslant 6$: оказалось, что здесь $L_k=2P_{2^k-1}$ при $k \geqslant 2$. Кстати, в тесте Люка-Лемера можно брать различные $L_1$, но все они четные: см. https://oeis.org/A018844.