мета-Фибоначчива последовательность и её обратная

[maxal]

Определим последовательность $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.$$

[nn910]

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}})})$откуда Ваше утверждение следовало бы более наглядно (два простых ряда перемножаются)

[maxal]

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$, прошу его озвучить...

[nn910]

Я уже исправил .Выступил с критикой опечатки и сделал свою. Извините великодушно.
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
Я стал так делать когда Вы дали задачу,но наткнулся на производящую функцию сильно противоречившую желаемому результату и забил.