# counting set bits of a natural number

For a natural number $n$ let $f(n)$ denote the number of set bits of $n$ - which is basically the Hamming weight of the binary representation of $n$. See wiki for more info.

I have to prove that $f(n^2) = \frac{1}{2} f(n)(f(n)+1)$ for infinitely many natural numbers. Can induction help here? It holds trivially for $1$ so maybe it is a good approach, I just do not see how to generalize it to $n$ or $n+1$.

Update: Note that for $n=2^k$ for $k>0$ we have that $f(2^k)=1$ and so when we calculate $f((2k)^2) = f(2^{2k})$ which is a power of two again so it is equal to $1$ and so is $$\frac{1}{2} f(2^k)(f(2^k)+1) =1$$

• Try with $n=2^k$. – celtschk Mar 11 '18 at 11:15
• @celtschk do I substitute this into $f$? – mandella Mar 11 '18 at 11:26
• Could you guys look at my updated sol? – mandella Mar 11 '18 at 11:43
• Ok deleted my comments now – Tal-Botvinnik Mar 11 '18 at 11:43
• @mandella yes, looks better now. Please accept one of the answers to avoid going into the unanswered section :-) – Tal-Botvinnik Mar 11 '18 at 11:45

If you want to prove that for all numbers then you can use induction. But not all numbers verify this, for instance $n=3$.
You could use induction inside a set $A$ other than $\mathbb{N}$, if you suspect that all elements of this set verify your expression. In that case the inductive step will be different.
• The relation between powers of 2 is that they are all of the form $2^k$. You can proceed by induction on $k$, i.e. prove for $k=0$ and then the inductive step for $k+1$ assuming true for $k$. – Tal-Botvinnik Mar 11 '18 at 11:30
• Or, you can just note that $f(2^k)=1$ for all $k$, therefore your expression holds if $n=2^k$ for all $k\geq 0$. You don't need induction. – Tal-Botvinnik Mar 11 '18 at 11:31
• So for $f((2^k)^2) = 1$ since $f(2^k)=1$ for $k>0$ right? – mandella Mar 11 '18 at 11:34
• @Tal-Botvinnik: Yes, I now noticed that I misread the “$+1$” part to still be in the argument. – celtschk Mar 11 '18 at 11:34