Mobius Inversion Formula

• Feb 25th 2010, 08:48 PM
mathmaniac234
Mobius Inversion Formula
I understand that the formula for f(n)
f(n) = the sum as d runs through n of µ(d)*F(n/d) by the inversion formula.
The answer I came up with when solving for f(72) was 6912 so I think I am off a bit somewhere...
mu(1)*2*72^2 + mu(2)*2*36^2 + mu(3)*2*24^2 + mu(6)*2*12^2 = f(72) = 6912
I am not sure I am fully understanding how to use mobius inversion formula correctly so any pointers who be appreciated. Thanks for you time!
• Feb 26th 2010, 05:05 AM
tonio
Quote:

Originally Posted by mathmaniac234
I understand that the formula for f(n)
f(n) = the sum as d runs through n of µ(d)*F(n/d) by the inversion formula.
The answer I came up with when solving for f(72) was 6912 so I think I am off a bit somewhere...
mu(1)*2*72^2 + mu(2)*2*36^2 + mu(3)*2*24^2 + mu(6)*2*12^2 = f(72) = 6912
I am not sure I am fully understanding how to use mobius inversion formula correctly so any pointers who be appreciated. Thanks for you time!

Putting $\displaystyle F(n):=\sum\limits_{d\mid n}f(d)\Longrightarrow f(d)=\sum\limits_{d\mid n} \mu(d)F\left(\frac{n}{d}\right)$ , so directly

$\displaystyle f(72)=\sum\limits_{d\mid 72} \mu(72)F\left(\frac{72}{d}\right)=\mu(1)F(72)+\mu( 2)F(36)+$ $\displaystyle \mu(3)F(24)+\mu(4)F(18)+\mu(6)F(12)+\mu(8)F(9)+\mu (9)F(8)+$ $\displaystyle \mu(12)F(6)+\mu(18)F(4)+\mu(24)F(3)+\mu(36)F(2)+\m u(72)F(1)=$ $\displaystyle F(72)-F(36)-F(24)+0+F(12)+0+0+0+0+0+0+0=$

$\displaystyle 2\cdot 72^2-2\cdot 36^2-2\cdot 24^2 + 2\cdot 12^2=6,912$ and thus I get the same value you got and did the same calculations you did.

Why do you think you're wrong?

Tonio
• Feb 26th 2010, 05:28 AM
mathmaniac234
Thanks!
I was still trying to fully understand how to utilize mobius inversion theorem properly and just naturally assumed that I was doing it incorrectly. But seeing you completely write it out has helped with my understanding so I believe we both got the right answer.

Thanks again
• Feb 26th 2010, 08:46 AM
tonio
Quote:

Originally Posted by mathmaniac234
Thanks!
I was still trying to fully understand how to utilize mobius inversion theorem properly and just naturally assumed that I was doing it incorrectly. But seeing you completely write it out has helped with my understanding so I believe we both got the right answer.

Thanks again

Good. Of course, the basic assumption is that f(n) is an arithmetic function...

Tonio