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 ] 

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



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

Сейчас этот форум просматривают: Bing [bot]


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

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