1

The function $f$ is defined on the set of positive integers by $$f(1) = 1,$$ $$f(2n) = 2f(n),$$ $$nf(2n + 1) = (2n + 1)(f(n) +n), n \geq 1$$

i) Prove that $f(n)$ is always an integer.

ii) For how many positive integers less than 2007 is $f(n) = 2n$ ?

For the first part, the answer key said that we can define a new variable of $g(n)=\frac{f(n)}{n}$ and this shows by induction that all $f(n)$ are integers. But for the second part, we are required to guess that $g(n)$ counts the number of $1$s in the binary notation of $n$. Does anyone know what the motivation for this is or any other more natural way to solve part (ii)?

danimal
  • 1,889
Hector Lombard
  • 649
  • 3
  • 11

1 Answers1

1

The motivation for $g$ in the first place is the odd-number relation: $$ nf(2n+1) = (2n+1)f(n) + (2n+1)n $$ dividing by $n(2n+1)$ lets us separate $2n+1$ from $n$ entirely: $$ \frac{f(2n+1)}{2n+1} = \frac{f(n)}{n} + 1 $$ and here we clearly see the motivation for $g$.

As for how to think about binary, consider this: The recursive equations for $g$ says that the value of $g(n)$ is built recursively on the binary expansion of $n$: As you add bit by bit, starting with the most significant, the recursive definitions tell you how the value of $g$ changes depending on whether you add a $0$ or a $1$.

That doesn't mean that this approach guarantees an answer. You will have to look into exactly how the recursive definition of $g$ plays out. But it means it is likely to be a fruitful approach to pursue.

Arthur
  • 199,419