Very nice! I can prove it, but I can't give any "deep" reason why it should be true. I'm sure there is a deep idea behind this formula.
By induction on : it's trivial for , so suppose it holds for . Write in binary as , with . We want to show that
Now for any positive , we have
Thus it suffices to notice that there is only one for which , namely .