2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Фибоначчи k-го уровня
Сообщение07.10.2017, 15:23 


21/11/12
468
$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-я дроби дают более точное приближение, нежели соседние коровы. Проблема. Интересен также вопрос делимости членов указанных последовательностей, но этим пока не занимался.

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение09.10.2017, 18:48 


21/11/12
468
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}$$ Такая дробь периодична и отображает точку золотого коровьего сечения, которая не является квадратичной иррациональностью.

Сообщение отредактировано модератором Karan по просьбе автора.

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение24.10.2017, 04:02 


21/11/12
468
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$.

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение30.10.2017, 23:22 


21/11/12
468
Еще закономерности: $$\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} C^{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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group