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$$

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

As a comment suggests, the set of all powers of 2 verify this. You can deduce directly from computations or if you really want to, induction

  • $\begingroup$ Could you elaborate more? I do not see the relation of powers of 2.. $\endgroup$ – mandella Mar 11 '18 at 11:27
  • $\begingroup$ 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$. $\endgroup$ – Tal-Botvinnik Mar 11 '18 at 11:30
  • $\begingroup$ 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. $\endgroup$ – Tal-Botvinnik Mar 11 '18 at 11:31
  • $\begingroup$ So for $f((2^k)^2) = 1$ since $f(2^k)=1$ for $k>0$ right? $\endgroup$ – mandella Mar 11 '18 at 11:34
  • $\begingroup$ @Tal-Botvinnik: Yes, I now noticed that I misread the “$+1$” part to still be in the argument. $\endgroup$ – celtschk Mar 11 '18 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.