We start from [A004718](http://oeis.org/A004718) named "The Danish composer Per Nørgård's "infinity sequence", invented in an attempt to unify in a perfect way repetition and variation"
$$a(2n) = -a(n), \qquad a(2n+1) = a(n) + 1, \qquad a(0)=0$$
More generally, we have $a=a\_2$ where
$$a\_k(n)=(-1)^{n+1}a\_k\left(\left\lfloor{n \over k}\right\rfloor\right)+(n \operatorname{mod} k), \qquad a\_k(0)=0.$$
Next we define
$$s\_k(n)=\left\lfloor\log\_{k}n\right\rfloor, \qquad s\_k(0)=0$$
also
$$p\_k(n)=\prod\_{i=0}^{s\_k(n)} (1+a\_k\left(\left\lfloor{n \over k^i}\right\rfloor\right))$$
and finally
$$q\_k(n) = \sum\_{j=0}^{k^n-1}p\_k(j)$$
What is nice here, it is the fact, that for even $k$
$$q\_k(n)=\binom{k+1}{2}^n$$
How can one prove it? How it can be extended for odd $k$ (I mean simple correction of $a\_k(n)$ recurrence relation)?



Voyage into the golden screen (sequence defined by recurrence relation)
Our strategy of proof will be to prove the identities
$$q\_k(m) = \sum\_{n=0}^{k^m-1}\prod\_{i=0}^{s\_k(n)} (1+a\_k\left(\left\lfloor{n \over k^i}\right\rfloor\right)) =\sum\_{n=0}^{k^m-1}(1 + (n \operatorname{mod} k) ) \prod\_{i=1}^{s\_k(n)} (1+a\_k\left(\left\lfloor{n \over k^i}\right\rfloor\right))$$ $$= (\sum\_{n=0}^{k-1} (1+(n\operatorname{mod} k)) ) (\sum\_{n=1}^{k^{m-1}-1 } \prod\_{i=0}^{s\_k(n)} (1+a\_k\left(\left\lfloor{n \over k^i}\right\rfloor\right)) = {k+1 \choose 2} q\_{k} (m-1) $$ giving the proof by statement by induction.


Of these identities, only the second is nontrivial. The first is by definition, the third is because we can sum $n \operatorname{mod} k$ and $\lfloor n/k \rfloor$ independently, and the fourth is by definition.


To prove the second identity, note that if $n$ is even, $\left\lfloor {n \over k^i} \right\rfloor = \left\lfloor { n+ 1 \over k^i} \right\rfloor$ for all $i \geq 1$. Thus


$$\prod\_{i=0}^{s\_k(n)} (1+a\_k\left(\left\lfloor{n \over k^i}\right\rfloor\right)) + \prod\_{i=0}^{s\_k(n+1)} (1+a\_k\left(\left\lfloor{n+1 \over k^i}\right\rfloor\right)) $$ $$= ( 1+ a\_k(n) + 1 + a\_k(n+1) ) \prod\_{i=1}^{s\_k(n)} (1+a\_k\left(\left\lfloor{n \over k^i}\right\rfloor\right))$$ $$ = \left(1 - a\_k \left( \left \lfloor {n \over k} \right \rfloor \right) + (n \operatorname{mod} k) + 1 + a\_k \left( \left \lfloor {n \over k} \right \rfloor \right) + (n+1 \operatorname{mod} k ) \right) \prod\_{i=1}^{s\_k(n)} (1+a\_k\left(\left\lfloor{n \over k^i}\right\rfloor\right))$$ $$ = \left(1 + (n \operatorname{mod} k) + 1 + (n+1 \operatorname{mod} k ) \right) \prod\_{i=1}^{s\_k(n)} (1+a\_k\left(\left\lfloor{n \over k^i}\right\rfloor\right))$$


$$( 1+ (n\operatorname{mod} k) \prod\_{i=1}^{s\_k(n)} (1+a\_k\left(\left\lfloor{n \over k^i}\right\rfloor\right)) + (1 + (n+1 \operatorname{mod} k )) \prod\_{i=1}^{s\_k(n+1)} (1+a\_k\left(\left\lfloor{n+1 \over k^i}\right\rfloor\right)) $$ 


In other words, we can drop all terms that appear the same in $n$ and $n+1$ but with opposite signs, leaving us with the simplified formula.


Something similar could be done with $k$ odd if you replace $(-1)^{n+1}$ by a function which is $1$ if the last digit is even and nonzero, $-1$ if the last digit is odd and nonzero, or $0$ if the last digit is zero - or any other function depending only on the last digit whose sum over all possible last digits is zero.


