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

  • 1
    $\begingroup$ 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? $\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^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.

| cite | improve this answer | |
  • $\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^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. $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.