Доказательство эквивалентности формул

[kthxbye]

Если имеем последовательность типа

$$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.

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

[Null]

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

[kthxbye]

Если расписывать через первую и вторую рекурсию соответственно, т.е. в форме

$$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.

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

[kthxbye]

Кроме того, вероятно

$$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.