Voyage into the golden screen (sequence defined by recurrence relation)

Question

We start from 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)?

Answer 1

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.