[psyang]

Originally Posted by psyang

Maybe a small hint for the proof to get the wheels turning.

Spoiler!

Now that we are working with binary numbers, consider operations as bit operations.

So, for example, multiplying by 2 is the same as a bitshift to the left.

Ok, no bites, so I'll post the solution.

Spoiler!

It's clear from the definition of f that f is defined over all natural numbers.

Let's define g(n) over the naturals such that g(n) reverses the binary representation of n.

We just have to show that g satisfies the conditions on f which are:

1) f(1) = 1
2) f(3) = 3
3) f(2n) = f(n)
4) f(4n+1) = 2f(2n+1) - f(n)
5) f(4n+3) = 3f(2n+1) - 2f(n)

Ok, well it's clear that 1 and 2 are satisfied by g since g(1) = 1 and g(3) = 3 (3 is 11 in binary).

For #3, we know that 2n is the same as a bitshift left of the binary representation of n, which is the same as appending a 0 to the end of the binary string. Reversing that would be the same as 0 followed by the reverse of n, or 0 followed by g(n) which is, of course, g(n).

For #4, the left hand side is g(4n+1) which is performing these operations:
1) shift n left twice [4n]
2) add 1 [+1]
3) reverse the bitstring [g()]
which yields 10[reverse of n]

The right hand side performs these operations:
for g(2n+1):
1) shift n left once [2n]
2) add 1 [+1]
3) reverse the bitstring [g()]

which gives 1[reverse of n] or, 2^k + g(n), where k is 1+high bit index of n.

So 2g(2n+1) is
2^k+1 + 2g(n)

4) we then subtract g(n) from the above which gives
2^k+1 + g(n)
=10[reverse of n]

which is the same as the left hand side.

The final relation is done similarly.

LHS performs:
1) shift n left twice [4n]
2) append 11 [+3]
3) reverse [g()]
This yields
11[reverse of n]

RHS performs:
1) shift n once [2n]
2) add 1 [+1]
3) reverse [g()]
This yields 1[reverse of n] or, put another way, 2^k + g(n) where k is 1+high bit index of n.

4) Multiply by 3 and subtract 2g(n) yields
3(2^k + g(n)) - 2g(n)
=3*2^k + g(n)
= 2^k+1 + 2^k + g(n)
= 11[reverse of n]
= LHS.