MathDB

For two non-negative integers

i, j

, create a new integer

i \# j

defined as the following: Express the two numbers in base

2

, and compare each digit. If their

k

th digit is the same, then the

k

th digit of

i \# j

0

. If their

k

th digit is different, then the

k

th digit of

i \# j

1

(of course we are talking in base

2

). For instance,

3 \# 5=6

. Show that for arbitrary positive integer

n

, the number can be expressed with finite operations of

\#

s and integers of the form

2^k-1

4