Фибоначчи k-го ур-я + алгебраическое число в цепную дробь

[Andrey A]

$F_1^{k}=F_2^{k}=...=F_k^{k}=1.$ Проще говоря, $k$ единиц являются начальными членами последовательности $F_n^{k}$. Начиная с $k+1$-го члена имеет место рекуррентное соотношение $F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$. Привычные Фибоначчи - последовательность второго уровня $(k=2)$. Первого - $F_n^{1}=2^{n-1}$ (и самая быстрорастущая), ну а на третьем уровне последовательность коров Нараяны:

$$F_n^{3}=1,1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406,595,872,1278,1873,...$$

Оказывается, задаче 700 лет. Отношение соседних Фибоначчи стремится к точке золотого сечения, предел отношения соседних коров $\approx 1,465571232$ тоже выражается в радикалах (см. Вики). Но чтобы продолжить список, пришлось бы зайти в Вольфрам и законспектировать приближенные значения положительных вещественных корней уравнения $x^k-x^{k-1}-1=0$ а у Нараяны не было Вольфрама! Вопрос: в какой строке $(k)$ и под каким номером $n$ встретится некоторое заданное натуральное число $M$? Ясно, что любое $M$ когда-нибудь да встретится, поскольку за $k$ начальными единицами в $k$-ой строке идут $k$ последовательных членов натурального ряда, но интересуют если не все вхождения, то хотя бы с наименьшим $k$.
Положим $F_n^{k}=M$ и $F_{n-1}^{k}=X$. Тогда дробь $\frac{M}{X}$ приближенно выражает нужную точку золотого сечения $k$-го уровня, и можно записать $\left( \frac{M}{X}\right)^k-\left( \frac{M}{X}\right)^{k-1}-1\approx 0$. Решая это уравнение относительно $k$, получаем

$$k\approx \frac{ \lg M-\lg (M-X)}{ \lg M-\lg X}$$

Все $k$ близкие к целым точкам сразу попадают под подозрение, однако имеем перебор на интервале $\frac{M}{(1+\sqrt{5})/2} <X<M$, и лучшее приближение тоже ни о чем еще не свидетельствует. В случае $M=60$, к примеру, лучшее приближение $\frac{ \lg 60-\lg 23}{ \lg 60-\lg 37} \approx 2$, но $60$ не является числом Фибоначчи. Более того, даже разложение точки золотого сечения в непрерывную дробь снимает вопрос только в случае $k=2$. Для $k=3$ имеем $1,465571232 \approx \frac{1}{1},\frac{3}{2},\frac{19}{13},\frac{22}{15},\frac{85}{58},\frac{447}{305},\frac{1873}{1278},...$ Как видим, 4-я, 5-я и 6-я дроби дают более точное приближение, нежели соседние коровы. Проблема. Интересен также вопрос делимости членов указанных последовательностей, но этим пока не занимался.

[Andrey A]

P.S.
Смещая на единицу нижние индексы в формуле $F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$, получаем $F_{n-1}^{k}=F_{n-2}^{k}+F_{n-k-1}^{k}$. Подстановка нового значения $F_{n-1}^{k}$ в первую формулу возвращает $F_n^{k}=F_{n-2}^{k}+F_{n-k}^{k}+F_{n-k-1}^{k}$. Совершая такую манипуляцию $k-2$ раз, получаем $F_n^{k}=F_{n-k+1}^{k}+F_{n-k}^{k}+F_{n-k-1}^{k}+...+F_{n-2k+2}^{k}$. Иными словами, сумма $k$ последовательных членов сама входит в последовательность $F_n^{k}$, на чем может быть основано альтернативное определение. Значит, на каждом уровне $>1$ имеется хотя бы одно треугольное число отличное от единицы, могут быть и другие. Например
$77=F_{32}^{11}=2+3+4+5+6+7+8+9+10+11$ или $341=F_{41}^{11}=11+12+14+17+21+26+32+39+47+56+66.$

Верно также

$$\det\begin{pmatrix} F_n^{4} & F_{n+1}^{4} & F_{n+2}^{4} & F_{n+3}^{4}\\ F_{n-1}^{4} & F_n^{4} & F_{n+1}^{4} & F_{n+2}^{4}\\ F_{n-2}^{4} & F_{n-1}^{4} & F_n^{4} & F_{n+1}^{4}\\ F_{n-3}^{4} & F_{n-2}^{4} & F_{n-1}^{4} & F_n^{4} \end{pmatrix}=(-1)^{(n-1)(k-1)}$$

Не рисую в общем виде (что-то некрасиво получается), но имеется в виду определитель $k$-го порядка, в данном случае - четвертого. Это связано с темой http://dxdy.ru/post1244374.html#p1244374. Для $k=3$ имеем последовательность трехэтажных дробей (аналог подходящих дробей), каждые три столбца которых образуют единичный определитель третьего порядка:

$$\begin{matrix} & 1 & 2 & 3 & 4 & 6 & 9 & 13 & 19 & 28\ ... \\ & 1 & 1 & 2 & 3 & 4 & 6 & 9 & 13 & 19\ ... \\ & 1 & 1 & 1 & 2 & 3 & 4 & 6 & 9 & 13\ ... & \end{matrix}$$

Такая дробь периодична и отображает точку золотого коровьего сечения, которая не является квадратичной иррациональностью.

[Andrey A]

P.S. P.S.
Члены последовательности $F_n^{k}$ представляют собой континуанты особого вида. Сумма одночленов, образованных вычеркиванием $k$ соседних членов из одночлена, все члены которого – единицы, есть количество композиций $n$ из $k$ и единиц. Об этом было здесь. Возникает гипотеза, которую не берусь строго доказать, но численно подтверждается:
Для конечного числа фиксированных $a>b>c>d>...>0$, не имеющих общего делителя $>1$, последовательность $K_n$ определена, как количество композиций $n$ из $a,b,c,d,…$ и задается рекуррентным правилом $K_n=K_{n-a}+K_{n-b}+K_{n-c}+K_{n-d}+...$ при стартовых условиях $K_0=1,K_{n<0}=0$. Предел отношения соседних членов такой последовательности $(n\rightarrow \infty )$ есть вещественный корень уравнения $x^a-x^{a-b}-x^{a-c}-x^{a-d}-...=1$.

[Andrey A]

Еще закономерности:

$$\sum\ F^{k}_n+1=F^{k}_{n+k}$$

$$\sum\limits_{i=0}^{n} F^{k}_{ki+m}=F^{k}_{kn+m+1}+0^m\ (m<k;0^0=1)$$

$$F^{k+1}_{n+1}=\sum\limits_{i=0} \binom{{n-ki}}{i}$$

Быстрый способ вычисления $k$-боначчи. Хотелось бы эту сумму упростить, вопрос вынесен в пр/р несколько в ином виде. Так же отсюда следуют тривиальные решения для фиксированного $M$:

$$M=F^{M-t_n}_{2M-1-n^2}$$

где $t_n=\frac{n(n+1)}{2}$ ($n$-ая сумма натурального ряда), $n\leq \left \lfloor \frac{\sqrt{8M+1}-1}{2} \right \rfloor$.

[Andrey A]

Andrey A в сообщении #1260646 писал(а):

где $... t_n=\frac{n(n+1)}{2}$ ($n$-ая сумма натурального ряда), $n\leq \left \lfloor \frac{\sqrt{8M+1}-1}{2} \right \rfloor$.

Тут закралась ошибка, провисевшая больше года. Правильно будет так: $n\leq \left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor$. Сформулирую получше что понимается под тривиальными решениями.

$1=F^{k}_{n}$ при условии $n \leqslant k$.

$M=F^{k=M+t}_{n=2M-1+t}$ ($t=0,1,2,...$)

$M=F^{ k=M-\frac{t(t+1)}{2}}_{n=2M-1-t^2}$ ( $0 < t \leqslant \left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor $ ).

Тема суммирования биномиальных коэффициентов получила продолжение. Переношу сюда результат kthxbye

kthxbye в сообщении #1397841 писал(а):

$$\color {blue}{\sum_{q=0}^m}&\color{blue}{\binom{n+(m-q)k}{q}}=\color{blue}{\sum_{q=0}^{\min(n,m)}}&\color{blue}{\binom{n}{q}a_k(m-q)}$$

где

$$a_k(n)=\begin{cases} 0,&\text{если $n<0$;}\\ 1,&\text{если $n=0$;}\\ \sum\limits_{p=0}^k\binom{k}{p}a_k(n-p-1),&\text{если $n>0$.} \end{cases}$$

и пост Ms-dos4

Ms-dos4 в сообщении #1397996 писал(а):

Можно использовать представление биномиального коэффициента через вычеты
$C_n^k = {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {{{{{(1 + z)}^n}} \over {{z^{k + 1}}}}dz}$
Тогда искомая сумма

$$\sum\limits_{j = 0}^m {C_{n + jk}^{m - j}} = {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\sum\limits_{j = 0}^m {{{{{(1 + z)}^{n + jk}}} \over {{z^{m - j + 1}}}}} dz} = - {1 \over {2\pii}}\int\limits_{\left| z \right| = \varepsilon } {{{{{(z + 1)}^n}} \over {{z^{m + 1}}[z{{(z + 1)}^k} - 1]}}dz} + {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {{{{{(z + 1)}^{n + k(m + 1)}}} \over {z{{(z + 1)}^k} - 1}}dz}$$

Второй интеграл равен нулю, что окончательно даёт

$$\sum\limits_{j = 0}^m {C_{n + jk}^{m - j}} = {1 \over {m!}}{\left. {{{{\partial ^m}} \over {\partial {z^m}}}[{{{{(z + 1)}^n}} \over {1 - z{{(z + 1)}^k}}}]} \right|_{z = 0}}$$

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

Тривиальные решения соответствуют суммам $2$-х или $3$-х биномиальных коэффициентов, количество их для фиксированного $M$ бесконечно. Если создать таблицу значений $F^{(k)}_n$ ($n$ по оси $x$, $k$ по оси $y$), выделяя маркером ячейки $=M$, образуется воображаемая кривая, которая в точке $(2M-1;M)$ вырождается в прямую под углом $45^{\circ}$. Количество нетривиальных решений конечно. Возможно ли свести задачу $M=F^{(y)}_x$ к нахождению целых точек на некой алгебраической кривой – вот вопрос. Моей компетенции тут к сожалению не достаточно. Но несколько тривиальных точек справа всё же имеем. Для $M=56$, к примеру, получаем $t \leqslant \left \lfloor \frac{\sqrt{8\cdot 56+17}-3}{2} \right \rfloor=9$, и соответствующие решения $56=F^{11}_{30}=F^{20}_{47}=F^{28}_{62}=F^{35}_{75}=$$F^{41}_{86}=F^{46}_{95}=F^{50}_{102}=F^{53}_{107}=F^{55}_{110}$. Других в данном случае и нет, но для $M=55$ кроме восьми тривиальных решений получаем также $55=F^{6}_{20}=F^{2}_{10}$ , как их найти – самое интересное. Пока что представление суммой биномиальных коэффициентов плодотворно, но могут быть и другие подходы. Судите сами.

[Andrey A]

Всё-таки существует алгоритм для нахождения нетривиальных решений задачи $M=F^{y}_x$. Строится последовательность k-боначчи по простому правилу: если некоторый член последовательности превышает $M$ по величине, то следующий берется с сохранением верхнего индекса, нижний же уменьшается на единицу. В противном случае ($\leqslant M$) верхний индекс уменьшается на единицу, нижний – на двойку. Первым членом последовательности берется наименьшее тривиальное решение. Вычислять сами $k$-боначчи быстрее суммами биномиальных коэффициентов, впрочем это дело вкуса (при большом $M$ в конце возникают подпоследовательности соседних фибоначчи и степенней двойки, там это бессмысленно). Алгоритм конечен, но все ли нетривиальные решения охватываются таким способом – тому доказательств нет. Исключений тоже пока не нашел. Пример $M=60.$
$\left \lfloor \frac{\sqrt{8\cdot 60+17}-3}{2} \right \rfloor=9;\ 60-9\cdot 10/2=15;\ 60\cdot 2-1-9^2=38.$ Имеем последовательность $F^{38}_{15}=60,F^{36}_{14}=59,F^{34}_{13}=58,...,F^{24}_8=53,F^{22}_7=53,F^{20}_6=55,$ $F^{18}_5=60,F^{16}_4=69,F^{15}_4=50, F^{13}_3=60,F^{11}_2=89,$ $F^{10}_2=55,F^{8}_1=128,F^{7}_1=64,F^{6}_1=32$ и два нетривиальных решения: $F^{18}_5=F^{13}_3=60.$

Интересно, что каждое треугольное число, начиная с $n=6$, имеет нетривиальное решение: $t_n=F^{n-4}_{3n-10}$, а также $t_n-2=F^{n-3}_{3n-8}$. Достигнув разности $=1$ между соседними членами (как в начале примера), можно сразу опускаться до ближайшего треугольного числа. Видимо есть и другие возможности для ускорения процесса. Не мытьем так катаньем. Кое-что о треугольных числах было здесь.

[Andrey A]

Andrey A в сообщении #1399222 писал(а):

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

... до ближайшего треугольного числа, не превышающего $M+2.$ Тоже требует доказательств. Верно, быть может, для достаточно большого $M.$

[Munin]

Andrey A в сообщении #1399222 писал(а):

Вычислять сами $k$-боначчи быстрее суммами биномиальных коэффициентов

Не понимаю, почему вы их не вычисляете экспонентами матриц.

[Andrey A]

Munin в сообщении #1399259 писал(а):

... экспонентами матриц.

Да пожалуйста. Если бы из этого следовал какой-то новый алгоритм, то да. А так повторюсь, дело вкуса или затратности. Не дыряв ли предложенный алгоритм — вот в чем вопрос.

Upd 06.03.2021
С моим гуманитарным образованием мне удобней пока так.

[Munin]

Из этого, как я понимаю, следует быстрота и лёгкость вычислений. Впрочем, дело ваше.

[Andrey A]

Munin в сообщении #1399280 писал(а):

... Впрочем, дело ваше.

Да, конечно.

Кое-что добавлю. Обозначим целое положительное число $\left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor$ буквой $c$. Выбирая первым членом $F^{c-2}_{3c-5}$, заметно сокращаем количество вычислений, причем гарантированно выявляются только нетривиальные решения. Практика подсказывает, что отношение числа итераций к величине $M$ в этом случае убывает с ростом $M$, что важно. Но для $M<8$ алгоритм перестает работать, что не очень важно: нетривиальные решения на этом промежутке отсутствуют.
Для строгого доказательства корректности алгоритма пришлось бы чертить схемы, попробую выразиться всё же на словах. Представим таблицу значений $F^{k}_n$ с началом координат в левом верхнем углу ($n$ по оси $x$, $k$ по оси $y$), где ячейки равные некоторому фиксированному $M$ (решения) выделены маркером. Ясно, что при движении в право из любой точки значения ячеек не убывают. Верно так же, что при движении вниз значения ячеек не возрастают. Нетривиальные точки характеризуются неравенством $n/k>3$. Еще закономерность: если из нетривиальной точки ходить конём (диагональ 1:2, шаг вниз — два шага вправо), то всегда придешь в тривиальную точку, равную исходному значению, причем все промежуточные значения (если таковые имели место) меньше исходного. Выберем теперь верхнюю ячейку, помеченную маркером (наименьшее нетривиальное решение), проведем из неё воображаемую диагональ 1:2 и луч вправо вдоль строки. Образуется сектор, направленный вершиной к началу координат (сектор наименьшего решения). Все ячейки под диагональю численно $<M$. Вершина сектора следующего нетривиального решения расположена ниже, численно $=M$ и не может поэтому находиться под диагональю или на ней. Она внутри сектора наименьшего решения. Таким образом сектора всех нетривиальных решений оказываются вложенными друг в друга как матрешки. Правило же составлено так, что попав на луч или диагональ, воображаемый конь с них уже не сходит и, поскольку координаты его движения убывают, неминуемо проходит все точки решений. Тут скорее схема доказательства чем доказательство, но суть происходящего надеюсь ясна.

Еще раз. Первый член последовательности алгоритма $=F^{c-2}_{3c-5}$, где $c=\left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor$. Каждый последующий член сохраняет верхний индекс предыдущего с уменьшением нижнего на единицу если предыдущий был $>M$. В противном случае ($\leqslant M$) верхний индекс уменьшается на единицу, нижний — на двойку. Такая последовательность содержит все нетривиальные решения уравнения $F_x^y=M.$ Тривиальные решения были тут

Andrey A в сообщении #1398300 писал(а):

$1=F^{k}_{n}$ при условии $n \leqslant k$.

$M=F^{k=M+t}_{n=2M-1+t}$ ($t=0,1,2,...$)

$M=F^{ k=M-\frac{t(t+1)}{2}}_{n=2M-1-t^2}$ ( $0 < t \leqslant \left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor $ ).

Наименьшее $M$ с тремя нетривиальными решениями $=281.$

[Andrey A]

PS В пределах тысячи всего три числа, имеющих три нетривиальных решения: $281,533,769.$ Выписывая наименьшие k-боначчи, имеющие $N$ нетривиальных решений ($N=0,1,2,...$), получаем ряд $1,8,34,281,...$ Можно ли продолжить его до бесконечности? Получить бы еще пару-тройку членов, но тут вопрос к обладателям мат.пакетов.

[Andrey A]

$1,8,34,281,2490,...$

$2490=F^{65}_{198}=F^{60}_{187}=F^{36}_{125}=F^{9}_{46} $ (4 нетр. решения).

[Andrey A]

upd 23.06.2019

$17051=F^{158}_{492}=F^{149}_{469}=F^{119}_{388}=F^{54}_{203}=F^{31}_{135}$ (5 нетр. решений).

1) Видимо, количество возможных нетривиальных решений ограничено только величиной $M$ и, вообще говоря, может быть сколь угодно велико.
2) Для $M>7$ количество шагов алгоритма (передвижений "коня") $=2c-\left \lfloor \log_{2}8M \right \rfloor<\sqrt{8M}.$

То и другое требует доказательств.

[dimkadimon]

Andrey A в сообщении #1253915 писал(а):

Вопрос: в какой строке $(k)$ и под каким номером $n$ встретится некоторое заданное натуральное число $M$?

У вас уже есть ответ на этот вопрос для маленьких $M$? Если нет, то можно найти и добавить в OEIS.

-- 08.09.2019, 22:04 --

Смотрите сюда и последовательные линки:

https://oeis.org/A003269