Упрощение суммирования с помощью R(n-1, q+1)

[kthxbye]

Пусть $f(n)$ - произвольная функция, значения которой - целые неотрицательные числа.

Пусть $g(n,m)$ - произвольная функция, значения которой - целые числа.

Пусть $b(n)$ - целочисленная последовательность, задаваемая рекуррентно через

$$b(2^m(2k+1))=\sum\limits_{j=0}^{f(m)}g(m,j)b(2^j k), b(0)=1$$

Пусть $s(n,q)$ - целочисленная последовательность, такая, что

$$s(n,q)=\sum\limits_{j=0}^{2^n-1}b(2^q j)$$

Пусть $R(n,q)$ - целочисленные коэффициенты, задаваемые рекуррентно через

$$R(n,q)=R(n-1,q+1)+\sum\limits_{j=0}^{f(q)}g(q,j)R(n-1,j), R(0,q)=1$$

Требуется доказать, что при $n\geqslant 0, q\geqslant 0$ будем иметь

$$R(n,q)=s(n,q)$$

[Dendr]

$s(0,q)=\sum\limits_{j=0}^{0}b(2^qj)=1=R(0,q)$
Далее по индукции: пусть равенство выполняется для всех значений первого аргумента до $n$ включительно.
Тогда

$$R(n+1,q)=s(n,q+1)+\sum\limits_{j=0}^{f(q)}g(q,j)s(n,j)$$

Рассмотрим $s(n+1,q)$:

$$s(n+1,q)=\sum\limits_{j=0}^{2^{n+1}-1}b(2^qj)= \sum\limits_{i=0}^{2^n-1}\left(b(2^q\cdot2i)+b(2^q(2i+1))\right)=\sum\limits_{i=0}^{2^n-1}b(2^{q+1}i)+\sum\limits_{i=0}^{2^n-1}b(2^q(2i+1))=$$

$$=s(n,q+1)+\sum\limits_{i=0}^{2^n-1}\sum\limits_{j=0}^{f(q)}g(q,j)b(2^qi)=s(n,q+1)+\sum\limits_{j=0}^{f(q)}g(q,j)s(n,q)=R(n+1,q)$$

Как видно, функция $g(n,m)$ не обязана быть целочисленной, даже действительной.