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 .