2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 мета-Фибоначчива последовательность и её обратная
Сообщение11.09.2009, 09:40 
Модератор
Аватара пользователя


11/01/06
5710
Определим последовательность $b(n)$ рекуррентной формулой:
$b(0)=b(1)=b(2)=1$
и
$b(n) = b(n-1-b(n-1)) + b(n-2-b(n-2))$ для $n>2.$
(A006949)

Зададим минимальную обратную ей последовательность $a(n)$ формулой:
$a(n) = \min \{ k : b(k)=n \}.$
(A120511)

Докажите, что для всех $n>1$ выполняется тождество:
$$a(n) = a(\lceil n/2\rceil) + n.$$

 Профиль  
                  
 
 Re: мета-Фибоначчива последовательность и её обратная
Сообщение15.09.2009, 13:38 


25/05/09
231
maxal,Ваше доказательство уже на A120511,там все понятно.
Однако не кажется ли Вам, что у Deugau и Ruskey (в общем кого-то из них ) в том же топике опечатка
Цитата:
G.f.: P(z) = z / (1-z) * (1 + sum(z^(m^2) * (1 + 1 / (1 - z^(m^2))), m=0..infinity))
$=\sum_{k=1}^{\infty}{a_k z^k}$, а правильно
$\sum_{k=1}^{\infty}{a_k z^k}=\dfrac{z}{1-z} (1+\sum_{m=0}^{\infty}{z^{2^m}(1+\frac{1}{1-z^{2^m}})})$откуда Ваше утверждение следовало бы более наглядно (два простых ряда перемножаются)

 Профиль  
                  
 
 Re: мета-Фибоначчива последовательность и её обратная
Сообщение16.09.2009, 16:09 
Модератор
Аватара пользователя


11/01/06
5710
nn910
Да, в OEIS опечатка - вместо $m^2$ должно быть $2^m$ (я послал в OEIS поправку), но вот знак в $1-z^{2^m}$ там правильный (то есть минус) и производящая функция выглядит так:
$$\frac{z}{1-z} \left(1+\sum_{m=0}^{\infty}{z^{2^m}(1+\frac{1}{1-z^{2^m}})}\right).$$

Если у вас есть альтернативное доказательство формулы $a(n) = a(\lceil n/2\rceil) + n$, прошу его озвучить...

 Профиль  
                  
 
 Re: мета-Фибоначчива последовательность и её обратная
Сообщение16.09.2009, 20:10 


25/05/09
231
Я уже исправил .Выступил с критикой опечатки и сделал свою. Извините великодушно.
2й вариант док-ва(изменены даже определения и названия):
Обозначим $\Delta a_n=a_{n+1}-a_n,n=1,2...$-последовательность разностей (сокращенно ПР) для любой последовательности $a_n$
Из Вашей формулы при $n=2k+2 ,2k+1$следует
(1)$\Delta a_{2k+1}=1$,за исключением$\Delta a_1 =2$ и при $n=2k+1 ,2k$
(2)$\Delta a_{2k}=a_{2k+1}-a_{2k}=a_{k+1}+2k+1-a_k-2k=\Delta a_k+1$
Итак,ПР для последовательности, определяемой нач.условием $a(1)=1$ и Вашим соотношением$a(n)=a([\dfrac{n+1}{2}])+n$ $\Delta a_n$ определена этими двумя формулами рекуррентно,сл-но однозначно.Остается показать что она является ПР для (A120511) Производящая функция ПР получается из исходной производящей функции умножением на $\dfrac{1-z} {z}$и отбрасыванием неверного свободного члена:
$$\sum_{m=0}^{\infty}{z^{2^m}(1+\frac{1}{1-z^{2^m}})}=\sum_{m=0}^{\infty}z^{2^m}(1+\sum_{k=0}^{\infty}z^{k 2^m})=\sum_{m=0}^{\infty}z^{2^m}+\sum_{m=0}^{\infty}\sum_{k=1}^{\infty}z^{k2^m}$$
Первый слагаемый ряд означает,что $\Delta a_n$имеет +1 "бонус",если n точная степень двойки.У второго слагаемого ряда коэффициент при каждой степени n будет равен числу представлений показателя степени в виде $k2^m$(определяемое числом возможных m)т.е 1 для нечетного показателя и 1+степень двойки как делителя -для четного. Но это описание $\Delta a_n$ эквивалентно соотношениям (1) и (2)(строго-например индукцией по m)
Это близко к Вашему док-ву но в "продифференцированной всюду" форме.Новых следствий из него не видно,может только рассмотреть ПР более общих функций, вводимых Deugau и Ruskey, а также ПР каких-нибудь еще посл-тей из OEIS
Я стал так делать когда Вы дали задачу,но наткнулся на производящую функцию сильно противоречившую желаемому результату и забил.

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

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



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

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


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

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