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

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)?

• This looks like a problem about a sum over $n$-tuples, artificially translated into number-theoretic language by recoding the tuples as numbers from $0$ to $k^n-1$. Am I missing something? – darij grinberg Jun 1 '19 at 7:57
• Sorry I misunderstood the signs. – Will Sawin Jun 1 '19 at 12:52
• Where is the "golden screen"? – Nik Weaver Jun 1 '19 at 14:26
• @NikWeaver, it just a name of one of the Nørgård's compositions. – user514787 Jun 1 '19 at 17:14

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.

• 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$? – user514787 Jun 1 '19 at 17:10
• Also I don't sure that your proof completely correct. – user514787 Jun 1 '19 at 17:32
• @user514787 What do you think might be wrong with my proof? And I did provide an example, in the last paragraph. – Will Sawin Jun 1 '19 at 18:36
• 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^m-1}$). 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. – user514787 Jun 1 '19 at 19:48
• 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. – user514787 Jun 2 '19 at 11:08