, 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{aligned} 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{aligned}$$
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{aligned} 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{aligned}$$
Similarly,
$$\begin{aligned} 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{aligned}$$

(D) We complete the deduction. Let $n \ge 1$ and $n = 2^{e_0} + 2^{e_1} + \dots + 2^{e_k}$, where $e_0 > e_1 > \dots > 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} + \dots + \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} + \dots + 2^{e_k}$, where $e_0 > e_1 > \dots > e_k$, we have by (C),
$$c(n) = (1 + \alpha)c(m) = (1 + \alpha)((1 + \alpha)^{e_0} + \dots + \alpha^k(1 + \alpha)^{e_k}) = (1 + \alpha)^{e_0+1} + \dots + \alpha^k(1 + \alpha)^{e_k+1}.$$
As $n = 2m = 2^{e_0+1} + \dots + 2^{e_k+1}$, the desired result follows for $n = 2m$. Suppose $n = 2m + 1$, where $m = 2^{e_0} + 2^{e_1} + \dots + 2^{e_k}$, where $e_0 > e_1 > \dots > e_k$. In this case $n = 2^{e_0+1} + \dots + 2^{e_k+1} + 2^0$ and $m+1 = 2^{e_0} + \dots + 2^{e_k} + 2^0$. Thus
$$c(2m+1) = ac(m) + c(m+1) = \alpha((1+\alpha)^{e_0} + \dots + \alpha^k(1+\alpha)^{e_k}) + ((1+\alpha)^{e_0} + \dots + \alpha^k(1+\alpha)^{e_k} + \alpha^{k+1}) = (1+\alpha)^{e_0+1} + \dots + \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$.