A Question about an Function of Integers

Question

Let $f$ denote a function. Given that $f(1)=1$, $f(2n)=2f(n)$, and $n\cdot f(2n+1)=(2n+1)\cdot(f(n)+n)$ where $n$ is a positive integer, the question is to prove that every $f(n)$ is an integer.
Though what needs to be proven is intuitively true, I am looking for some rigorous approach. Any idea or hint would be appreciated.

Remark: this problem has been solved thanks to lulu. Please see the two solutions posted below. Nevertheless, any new approach is always welcome.

Answer 1

Induction provides a fairly easy approach to the problem (note that your inductive hypothesis must be something like "$f(n)$ is an integer divisible by $n$").

Here, however, is a different approach:

Claim: $f(n)$ is $n$ times the number of $1's$ in the base $2$ expansion of $n$.

Pf: Let $F(n)$ be $n$ times the number of $1's$ in the base $2$ expansion of $n$, so we want to prove that $F(n)=f(n)$. It is clear that $F(1)=f(1)=1$, so now assume that $n>1$.

Case I: $n$ even. So $n=2m$. Let $k$ be the number of $1's$ in the base $2$ expansion of $m$, so that $F(m)=mk$. Since $n=2m$ has the same binary expansion, with an extra $0$ we see that $F(2m)=2mk=2F(m)$ as desired.

Case II: $n$ odd. So $n=2m+1$. Let $k$ be the number of $1's$ in the base $2$ expansion of $m$, so that $F(m)=mk$. We note that $2m+1$ has exactly one more $1$ in its binary expansion than $m$ does so $F(2m+1)=(2m+1)(k+1)$. It is then easy to confirm that $$mF(2m+1)=m(2m+1)(k+1)=(2m+1)(mk+m)=(2m+1)(F(m)+m)$$

Thus $F(n)$ satisfies the same recursion and initial condition as $f(n)$ so $F(n)=f(n)$ and we are done.

Answer 2

First of all, a lot of thanks for lulu's induction hint and another non-inductive ingenious approach. Below is a proof by strong induction for future reference.

• Statement $S$: $f(n)$ is an integer divisible by $n$.
  
• Base step: $f(1)=1$ is divisible by $1$, so $S$ is true for $n=1$.
  
• Assumption step: assume $S$ is true for $n=1,2,...,k$ where $k$ is any positive integer.
• Inductive step: if $k$ is even, then $f(k+1)=(k+1)\cdot\left(\frac {f\left(\frac k2\right)}{\frac k2}+1\right)$. By assumption, since $\frac k2\lt k$, $\frac {f\left(\frac k2\right)}{\frac k2}$ is an integer, and then it is easy to deduce that $f(k+1)$ is an integer divisible by $k+1$. If $k$ is odd, then $f(k+1)=2f\left(\frac {k+1}{2}\right) \Rightarrow \frac {f(k+1)}{k+1}=\frac {f\left(\frac {k+1}{2}\right)}{\frac {k+1}{2}}$. By assumption, since $\frac {k+1}{2}\le k \Leftarrow k\ge1$, $f\left(\frac {k+1}{2}\right)$ is an integer divisible by $\frac {k+1}{2}$, and then $\frac {f(k+1)}{k+1}$ is an integer, and then $f(k+1)$ is an integer divisible by $k+1$.
• Conclusion step: since $S$ is true for $n=1$, and $S$ is true for $n=k+1$ if true for $n=1,2,...,k$ where $k$ is any positive integer, by induction $S$ is true for any positive integer $n$.
  

Please kindly correct me if there is any mistake in the proof above. Thanks.