Why sum of digits in even base have such property?

90 Views Asked by At

Function $D(a, b)$ define as sum of digit of $a$ in base $b$. Example $D(5,2)=2$.

Let $$f(m, n)=\sum_{k=1}^m(-1)^{D(k, n)}$$

Example $f(5,2)=(-1)^{D(1,2)}+(-1)^{D(2,2)}+(-1)^{D(3,2)}+(-1)^{D(4,2)}+(-1)^{D(5,2)}=(-1)+(-1)+1+(-1)+1=-1$.

Question: If $n$ is even then $f(m, n)\in\{-2,-1,0\}$ where $m$ is positive integer.

Note : if $a=(a_t...a_1a_0)_b$ and $b=2x+1$ are odd then $D(a, b)$ also odd because we can express $a= (2x+1)^t\cdot a_t+...+(2x+1)\cdot a_1+a_0=a_t+...+a_1+a_0+l$ for some even $l$. So given $a$ odd implies $a_t+...+a_1+a_0$ also odd and we get $D(a, b)$ odd.

Theorem 1: If $n$ is odd then $f(m, n)\in\{-1,0\}$

Proof: if $k$ and $n$ are odd then $D(k, n)$ will be odd. And if $k$ is even and $n$ is odd then $D(k, n)$ will be even. This implies if $m,n$ are odd then $f(m, n)$ will be odd$(=-1)$ and $f(m+1,n)$ will be even$(=0)$.

Source code PARI/GP

for(a=1,100,print([a,sum(k=1,a,(-1)^sumdigits(k, 2))]))
1

There are 1 best solutions below

0
On BEST ANSWER

The point is that if $\ell,n$ are even then $(-1)^{D(\ell,n)}+(-1)^{D(\ell+1,n)}=0$. This is because $\ell$ and $\ell+1$ differ only in the last digit in base $n$.

That means $\sum_{k=0}^{\ell+1}(-1)^{D(k,n)}=0$ for $\ell$ even, because it can be split into $\ell+1$ pairs which each sum to $0$.

Now if $m=\ell+1$ is odd then $$f(m,n)=\sum_{k=0}^{\ell+1}(-1)^{D(k,n)}-(-1)^{D(0,n)}=0-1=-1,$$ whereas if $m=\ell$ is even then $$f(m,n)=\sum_{k=0}^{\ell+1}(-1)^{D(k,n)}-(-1)^{D(0,n)}-(-1)^{D(\ell+1,n)}=-1-(-1)^{D(\ell+1,n)},$$ and since $(-1)^{D(\ell+1,n)}\in\{-1,1\}$, we get $f(m,n)\in\{-2,0\}$.