A Property of the fusc() Function

Function fusc, one of whose properties we are going to prove, has been defined as a shift of the the number q(n) of hyperbinary representations of an integer n. The latter appeared in several contexts, enumeration of the fractions on a binary tree, in particular.

Function fusc admits a recursive definition:

fusc(0) = 0,
fusc(1) = 1,
fusc(2n) = fusc(n),
fusc(2n + 1) = fusc(n) + fusc(n + 1), n = 1, ...

Here are the first 100 values of the function:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19, 7, 16, 9, 11, 2, 11, 9, 16, 7.

The function has an interesting graph, see Gary Davis' blog.

Proposition

fusc(n) is even iff n is divisible by 3.

Proof

The inductive proof is a simplified version of that given by Gary Davis.

The proposition definitely holds for a few first values of the function. For the inductive step assume it holds for all values k < N, and consider fusc(N).

The simplest approach is to consider N modulo 6:

N = 6n + 0: fusc(6n) = fusc(3n) which is even by the inductive assumption.
N = 6n + 1: fusc(6n + 1) = fusc(3n) + fusc(3n + 1) is odd, because the first addend is even, while the second is odd.
N = 6n + 2: fusc(6n + 2) = fusc(3n + 1) is odd by the inductive assumption.
N = 6n + 3: fusc(6n + 3) = fusc(3n + 1) + fusc(3n + 2) is even, because both addends are odd.
N = 6n + 4: fusc(6n + 4) = fusc(3n + 2) is odd by the inductive assumption.
N = 6n + 5: fusc(6n + 5) = fusc(3n + 2) + fusc(3n + 3) is odd as the sum of an odd and an even number.

The proof is complete.

41162605