2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Доказательство эквивалентности формул
Сообщение17.07.2021, 07:44 
Аватара пользователя


22/11/13
498
Если имеем последовательность типа
$$a(n) = f(\ell(n))\cdot a(n - 2^{\ell(n)}), a(0)=1$$
где $\ell(n)$ это A000523
$$\ell(n) = \ell(\left\lfloor\frac{n}{2}\right\rfloor) + 1, \ell(1) = 0$$
то справедливо
$$a(n) = f(b(n))\cdot a(n - 2^{b(n)}), a(0)=1$$
где $b(n)$ это A007814
$$b(2n+1) = 0, b(2n) = b(n) + 1$$
Примеры: A001317, A121663.

Как это можно доказать?

 Профиль  
                  
 
 Re: Доказательство эквивалентности формул
Сообщение20.07.2021, 15:59 
Заслуженный участник


12/08/10
1609
Распишите $a(n)$ в произведение в зависимости от его двоичного представления.

 Профиль  
                  
 
 Re: Доказательство эквивалентности формул
Сообщение03.09.2021, 14:57 
Аватара пользователя


22/11/13
498
Если расписывать через первую и вторую рекурсию соответственно, т.е. в форме
$$a(n) = f(q_1)f(q_2)\cdots f(q_m)a(0)$$
имеем
$$\begin{bmatrix}
n & 1 & 2 \\
0 & 0 0 0 0 & 0 0 0 0 \\
1 & 1 0 0 0 & 1 0 0 0 \\
2 & 2 0 0 0 & 2 0 0 0 \\
3 & 2 1 0 0 & 1 2 0 0 \\
4 & 4 0 0 0 & 4 0 0 0 \\
5 & 4 1 0 0 & 1 4 0 0 \\
6 & 4 2 0 0 & 2 4 0 0 \\
7 & 4 2 1 0 & 1 2 4 0 \\
8 & 8 0 0 0 & 8 0 0 0 \\
9 & 8 1 0 0 & 1 8 0 0 \\
10 & 8 2 0 0 & 2 8 0 0 \\
11 & 8 2 1 0 & 1 2 8 0 \\
12 & 8 4 0 0 & 4 8 0 0 \\
13 & 8 4 1 0 & 1 4 8 0 \\
14 & 8 4 2 0 & 2 4 8 0 \\
15 & 8 4 2 1 & 1 2 4 8
\end{bmatrix}$$
Т.е. скорее всего $T_2(n,k)=T_1(n,m-k+1)$, где $m$ это A000120.

А вот почему - большой вопрос.

 Профиль  
                  
 
 Re: Доказательство эквивалентности формул
Сообщение03.09.2021, 17:29 
Аватара пользователя


22/11/13
498
Кроме того, вероятно
$$a(n)=a(0)\prod\limits_{T(n,k)=1}^{}f(2^{k}T(n,k))$$
где
$$T(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor\bmod 2$$$$n=\sum\limits_{k=0}^{\ell(n)}2^{k}T(n,k)$$
что возможно и имел ввиду Null. Чуть иначе это описано во втором комментарии к A001317.

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

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



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

Сейчас этот форум просматривают: tolstopuz


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

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