$f(n) = \Sigma_{d|n} \mu(n/d)F(d)$

150 Views Asked by At

The question says:

If $F(n) = \Sigma_{d|n} f(d)$ for every positive integer $n$, prove that $f(n) = \Sigma_{d|n} \mu(n/d)F(d)$.

What I know so far is that divisors of $n$ can be paired together. Hence, using mobius inversion formula, the following holds true:

$$f(n) = \Sigma_{d|n}\mu(\frac{n}{d})F(\frac{n}{d})$$

However, it is not exactly the same as in the question.

The question is from An introduction to The Theory of Numbers by Ivan Niven.

2

There are 2 best solutions below

2
On BEST ANSWER

The formula in the problem is the Mobius inversion formuala (see the link below with the substitution of $n/d$ into $d$):

https://en.wikipedia.org/wiki/Möbius_inversion_formula

You quoted the formula incorrectly.

0
On

This would be very useful if it was written as a hint:

Use mobius formula with the following substitution:

$$d = \frac{n}{d}$$