Путешествие в золотой экран

[kthxbye]

Начинаем мы его с A004718, посвященной датскому композитору (некий Per Nørgård), а точнее его последовательности

$$a(2n) = -a(n), a(2n+1) = a(n) + 1, a(0)=0$$

которую можно представить в виде

$$a_k(n)=(-1)^{n+1}a_k\left(\left\lfloor{n \over k}\right\rfloor\right)+(n \mod k), a_k(0)=0$$

для $k=2$. Далее мы обозначим

$$s_k(n)=\left\lfloor\log_{k}n\right\rfloor, s_k(0)=0$$

затем

$$p_k(n)=\prod_{i=0}^{s_k(n)} (1+a_k\left(\left\lfloor{n \over k^i}\right\rfloor\right))$$

и наконец

$$q_k(m) = \sum_{n=0}^{k^m-1}p_k(n)$$

Что удивительно, для четных $k$ имеем

$$q_k(m)=\binom{k+1}{2}^m$$

Как это можно доказать? Возможно ли обобщение для нетных $k$ (путём незначительной корректировки рекуррентного соотношения для $a_k(n)$)?