Back to index

If n = \lbrace a_m, a_{m-1}, \ldots, a_2, a_1, 0 \rbrace, then 4n+1 = \lbrace a_m+2, a_{m-1}+2, \ldots, a_2+2, a_1+2, 0 \rbrace.

The converse is also true.

If n is given by

n = \frac{2^{a_m} - \displaystyle\sum_{k=0}^{m-1} 2^{a_k} \, 3^{m-1-k}} {3^m}

then a multiplication by 4 turns every 2^{a_k} into 2^{a_k+2}; and also, since

1 = \frac{(4-1) \cdot 3^{m-1}}{3^m} = \frac{4 \cdot 3^{m-1} - 3^{m-1}}{3^m}

we have (with a_0=0, \; 2^{a_0+2}=4),

4n+1 ~=~ \frac{2^{a_m+2} - \displaystyle\sum_{k=0}^{m-1} 2^{a_k+2} \, 3^{m-1-k}} {3^m} + 1 ~=~ \frac{2^{a_m+2} - \displaystyle\sum_{k=1}^{m-1} 2^{a_k+2} \, 3^{m-1-k} - \cancel{4 \cdot 3^{m-1}} + \cancel{4 \cdot 3^{m-1}} - 3^{m-1}} {3^m}

\square

For the converse, just follow the proof backwards.

The condition a_0=0 means than n is odd, and

4n+1 = 4(2k+1)+1 = 8k+5

for some k; the representation of a number n' that is congruent to 5 modulo 8 can be reduced (via this proposition) to the representation of   \frac{n' - 1}{4}.