The Lumber Room

"Consign them to dust and damp by way of preserving them"

A “Möbius” inversion formula

leave a comment »

[Not the Möbius inversion formula, but something similar.]
As usual, define the Möbius function μ on the natural numbers as
\mu(n) = \begin{cases}0 \text{ if n is not square free,}\\ -1\text{ if n is squarefree with an odd number of prime factors,}\\ 1\text{ if n is squarefree with an even number of prime factors.}\\\end{cases}
Let f be any function defined on the natural numbers, and let F be the function defined as \displaystyle F(n) = \sum_{j=1}^{n}{f(\left\lfloor{n/j}\right\rfloor)}.
Then it is true that \displaystyle f(n) = \sum_{k=1}^{n}{\mu(k)F(\left\lfloor{n/k}\right\rfloor)}.

Note that f need not be multiplicative; it can be any arbitrarily defined function. I have no idea why it is true. Help?

Written by S

Fri, 2008-11-28 at 18:55:44

Posted in Uncategorized

Tagged with , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s