The function f on the non-negative integers takes non-negative integer values and satisfies f(4n) = f(2n) + f(n), f(4n+2) = f(4n) + 1, f(2n+1) = f(2n) + 1 for all n. Show that the number of non-negative integers n such that f(4n) = f(3n) and n < 2^{m} is f(2^{m+1}).

**Solution**

f(4.0) = f(2.0) + f(0), so f(0) = 0. Hence f(1) = f(2.0+1) = f(0) + 1 = 1, f(2) = f(4.0+2) = f(0) + 1 = 1. Similarly, f(3) = f(2.1+1) = f(2) + 1 = 2. Calculating a few more terms, in a similar way, we get:

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 f(n) 0 1 1 2 2 3 3 4 3 4 4 5 5 6 6 7 5 6 6 7 7 8The pattern is not obvious.

However, we may notice f(4n) = f(2n) + f(n). That implies that f(2^{k+2}) = f(2^{k+1}) + f(2^{k}). So if we put f(2^{k}) = f_{k}, then f_{k} is just the kth Fibonacci number. A little further study may then suggest that each f(n) is a sum of Fibonnacci numbers. In fact, if n = b_{k}...b_{0} in binary, then f(n) = b_{k}f_{k+1} + ... + b_{0}f_{1}.

To prove this, we just have to verify the equalities in the question. Suppose n = b_{k} ... b_{0}. Then f(n) + f(2n) = (b_{k}f_{k+1} + ... + b_{0}f_{1}) + (b_{k}f_{k+2} + ... + b_{0}f_{2}) = b_{k}f_{k+3} ... b_{0}f_{3} = f(4n), which establishes the first equality. The second and third are obvious.

We now claim that f(3n) = f(4n) iff no two 1s appear in adjacent positions in the binary expansion of n.

Granting the claim, it remains to show that there are f_{m+2} integers < 2^{m} with no adjacent 1s. We prove this by induction on m. For m = 1, we have 0 and 1, and f_{3} = 2. For m = 2, the integers are 0, 1, 3 = 10_{2}, and f_{4} = 3. Suppose it is true for integers < m. Take n < 2^{m}. Let the binary expansion of n be b_{m-1} ... b_{0}. Then n < 2^{m-1} iff b_{m-1} = 0. In this case there are f_{m+1} possible numbers (by induction). If 2^{m-1} ≤ n < 2^{m}, then b_{m-1} = 1, so b_{m-2} = 0. There are then f_{m} possibilities for the remaining digits (by induction). So in total there are f_{m} + f_{m+1} = f_{m+2} possible numbers.

It remains to prove the claim. Suppose there are no adjacent 1s. Then 3n = 2n + n, and there are no carries when this is computed in binary. So if f(n) = b_{k}f_{k+1} + ... + b_{0}f_{1}, then f(3n) = b_{k}(f_{k+1} + f_{k+2}) + ... + b_{0}(f_{1} + f_{2}) = b_{k}f_{k+3} + ... + b_{0}f_{3} = f(4n).

The reverse implication is harder. Let S_{m} be the statement that for 0 < n < 2^{m} we have f(3n) ≤ f(4n) with equality only if the 1s are isolated. For m = 1 we must have n = 1. We have f(3) = f(4) = 2, so S_{1} is true. So assume S_{m} is true. Let n = 2^{m} + k with 0 ≤ k < 2^{m}. Then f(4n) = f(2^{m+2} + 4k) = f_{m+3} + f(4k).

There are three cases to consider.

*Case 1.* 0 < k < 2^{m}/2. Then 3k < 2^{m}, so the binary representations of 3.2^{m} = 2^{m+1} + 2^{m} and 3k do not overlap. So f(3n) = f(2^{m+1} + 2^{m} + 3k) = f_{m+2} + f_{m+1} + f(3k) = f_{m+3} + f(3k) ≤ f_{m+3} + f(4k) (by induction) = f(4n) and we have equality only if the 1s are isolated (since k < 2^{m}, if the 1s are isolated in k, then the 1s are also isolated in n = 2^{m} + k).

*Case 2.* 2^{m}/3 < k < 2^{m+1}/3. Then 3k = 2^{m} + h with h < 2^{m}, so f(3k) = f_{m+1} + f(h). But 3n = 2(^{m+1} + 2^{m}) + 3k = 2^{m+2} + h, so f(3n) = f_{m+3} + f(h) = f_{m+3} + f(3k) - f_{m+1} = f_{m+2} f(3k) ≤ f_{m+2} + f(4k) (by induction) < f_{m+3} + f(3k). We cannot have equality in this case.

*Case 3.* 2^{m+1}/3 < k < 2^{m}. So 3k = 2^{m+1} + h with h < 2^{m}, so f(3k) = f_{m+2} + f(h). We have 3n = (2^{m+1} + 2^{m}) + 2^{m+1} + h = 2^{m+2} + 2^{m} + h, so f(3n) = f_{m+3} + f_{m+1} + f(h) = f_{m+3} - f_{m+2} + f_{m+1} + f(3k) < f_{m+3} + f(3k) ≤ f_{m+3} + f(4k) = f(4n). We cannot have equality in this case. That completes the proof of the claim.

© John Scholes

jscholes@kalva.demon.co.uk

10 Oct 2002