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^n1}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)?

1$\begingroup$ This looks like a problem about a sum over $n$tuples, artificially translated into numbertheoretic language by recoding the tuples as numbers from $0$ to $k^n1$. Am I missing something? $\endgroup$ – darij grinberg Jun 1 '19 at 7:57

$\begingroup$ Sorry I misunderstood the signs. $\endgroup$ – Will Sawin Jun 1 '19 at 12:52

2$\begingroup$ Where is the "golden screen"? $\endgroup$ – Nik Weaver Jun 1 '19 at 14:26

$\begingroup$ @NikWeaver, it just a name of one of the Nørgård's compositions. $\endgroup$ – user514787 Jun 1 '19 at 17:14
Our strategy of proof will be to prove the identities $$q_k(m) = \sum_{n=0}^{k^m1}\prod_{i=0}^{s_k(n)} (1+a_k\left(\left\lfloor{n \over k^i}\right\rfloor\right)) =\sum_{n=0}^{k^m1}(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}^{k1} (1+(n\operatorname{mod} k)) ) (\sum_{n=1}^{k^{m1}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} (m1) $$ 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.

$\begingroup$ Thank you for answer! There is a little typo after "if $n$ is even". Induction is good, but it obviously useful when we already have result. Can you please also provide an example of function for odd $k$? $\endgroup$ – user514787 Jun 1 '19 at 17:10

$\begingroup$ Also I don't sure that your proof completely correct. $\endgroup$ – user514787 Jun 1 '19 at 17:32

$\begingroup$ @user514787 What do you think might be wrong with my proof? And I did provide an example, in the last paragraph. $\endgroup$ – Will Sawin Jun 1 '19 at 18:36

$\begingroup$ At least part with second identity, exactly first and fourth (you also forget $=$ there) identities are false (if we work with them independently i.e. without $\sum\limits_{n=0}^{k^m1}$). We need to be very careful with $s_k(n)$ and $s_k(n+1)$. Also by example I mean formula which I could check (at least by computation). Your definition is not clear to me. Sorry if it looks like I critique or I want too much. I just trying to understand. Also english not my native. $\endgroup$ – user514787 Jun 1 '19 at 19:48

$\begingroup$ Sorry I was wrong. We may define $s_k(n)$ recursively, exactly $s_k(n)=0$ if $n<k$ and $s_k(n)=s_k\left(\left\lfloor{n \over k}\right\rfloor\right)+1$ otherwise. So it's clear from here that $s_k(n)=s_k(n+1)$ holds for $n$ even. Now I'm trying to understand third identity and of course your example. $\endgroup$ – user514787 Jun 2 '19 at 11:08