Indija TS 2008

We prove this in four steps. We use $s_n=s(n)$ and $c_n=c(n)$,

(A) If $b(n)$ denotes the number of $1$'s in the binary representation of a non-negative integer $n$, we have $s(n)={\alpha }^{b(n-1)}$, $n\ge 1$. Proof: We use induction. Note that $s(1)=1={\alpha }^{b(0)}$. Suppose $s(r)={\alpha }^{b(r-1)}$, for $1\le r\le 2^{n-1}$. Take any $r$ such that $2^{n-1}+1\le r\le 2^n$. We have $$\begin{array}{rl}s(r)& =\alpha s(r-2^{n-1})\\ & =\alpha {\alpha }^{b(r-2^{n-1}-1)}\\ & ={\alpha }^{b(r-2^{n-1}-1)+1}={\alpha }^{b(r-1)},\end{array}$$ as $r-1$ has exactly one more $1$ in its binary representation than $r-2^{n-1}-1$.

(B) If $m\ge 1$, we have $s(2m+1)=s(m+1)$ and $s(2m)=\alpha s(m)$. Proof: Since $m$ and $2m$ have same number of $1$'s, we have $$s(2m+1)={\alpha }^{b(2m)}={\alpha }^{b(m)}=s(m+1).$$ For even numbers, first we show that $s(2m)=\alpha s(2m-1)$. This is easy to establish by induction. Observe $s(2)=\alpha =\alpha s(1)$. If $2^{n-1}+1\le 2m-1<2n\le 2^n$, we get by induction hypothesis $$s(2m)=\alpha s(2m-2^{n-1})={\alpha }^{2}s(2m-1-2^{n-1})=\alpha s(2m-1).$$ Thus we get $$s(2m)=\alpha s(2m-1)=\alpha s(2(m-1)+1)=\alpha s(m-1+1)=\alpha s(m),$$ where we have used $s(2k+1)=s(k+1)$.

(C) For $m\ge 1$, we have $c(2m)=(1+\alpha )c(m)$ and $c(2m+1)=\alpha c(m)+c(m+1)$. Proof: We have $$\begin{array}{rl}c(2m)& =(s(1)+s(3)+\cdots +s(2m-1))+(s(2)+s(4)+\cdots s(2m))\\ & =(s(1)+s(2)+\cdots s(m))+\alpha (s(1)+s(2)+\cdots s(m))\\ & =(1+\alpha )(s(1)+s(2)+\cdots s(m))=(1+\alpha )c(m).\end{array}$$ Similarly, $$\begin{array}{rl}c(2m+1)& =(s(1)+s(3)+\cdots +s(2m-1)+s(2m+1))+(s(2)+s(4)+\cdots s(2m))\\ & =(s(1)+s(2)+\cdots s(m)+s(m+1))+\alpha (s(1)+s(2)+\cdots s(m))\\ & =\alpha c(m)+c(m+1).\end{array}$$

(D) We complete the deduction. Let $n\ge 1$ and $n=2^{e_0}+2^{e_1}+\cdots +2^{e_k}$, where $e_0>e_1>\cdots >e_k\ge 0$ is the binary representation of a positive integer $n$. We prove $$c(n)=(1+\alpha {)}^{e_0}+\alpha (1+\alpha {)}^{e_1}+{\alpha }^2(1+\alpha {)}^{e_2}+\cdots +{\alpha }^k(1+\alpha {)}^{e_k}.$$

For $n=1$, we have $1=2^0$, and $C(1)=s(1)=1=(1+\alpha {)}^0$. Suppose the statement is true for $c(1),c(2),\dots ,c(n-1)$, $n\ge 2$. If $n=2m$ and $m=2^{e_0}+2^{e_1}+\cdots +2^{e_k}$, where $e_0>e_1>\cdots >e_k$, we have by (C), $$c(n)=(1+\alpha )c(m)=(1+\alpha )((1+\alpha {)}^{e_0}+\cdots +{\alpha }^k(1+\alpha {)}^{e_k})=(1+\alpha {)}^{e_0+1}+\cdots +{\alpha }^k(1+\alpha {)}^{e_k+1}.$$ As $n=2m=2^{e_0+1}+\cdots +2^{e_k+1}$, the desired result follows for $n=2m$. Suppose $n=2m+1$, where $m=2^{e_0}+2^{e_1}+\cdots +2^{e_k}$, where $e_0>e_1>\cdots >e_k$. In this case $n=2^{e_0+1}+\cdots +2^{e_k+1}+2^0$ and $m+1=2^{e_0}+\cdots +2^{e_k}+2^0$. Thus $$c(2m+1)=ac(m)+c(m+1)=\alpha ((1+\alpha {)}^{e_0}+\cdots +{\alpha }^k(1+\alpha {)}^{e_k})+((1+\alpha {)}^{e_0}+\cdots +{\alpha }^k(1+\alpha {)}^{e_k}+{\alpha }^{k+1})=(1+\alpha {)}^{e_0+1}+\cdots +{\alpha }^k(1+\alpha {)}^{e_k+1}+{\alpha }^{k+1}(1+\alpha {)}^0.$$ Thus the relation is true for $n=2m+1$ as well. This completes the proof by induction on $n$.