莫比烏斯函數一例

05-22

莫比烏斯函數一例

我們來證明 $sum_{i = 1}^nmu(i)^2 = sum_{i = 1}^{lfloorsqrt{n} floor}mu(i)lfloor{frac{n}{i^2}} floor$ ，其中 $mu(x)$ 為莫比烏斯函數。

注意到根據莫比烏斯函數定義，上式左邊其實是在求無平方因子數的個數。我們定義 $f(x) = s$ 為最大的整除 $x$ 的平方數。於是 $sum_{i = 1}^nmu(i)^2 = sum_{i = 1}^n [f(i)= 1]$ 。

學習過莫比烏斯函數的同學都知道我們有經典套路 $[x = 1] = sum_{d|x} mu(d)$ ，那麼我們現在開始證明：

$egin{aligned} sum_{i = 1}^nmu(i)^2 &= sum_{i = 1}^n [f(i)= 1]\ &= sum_{i = 1}^n sum_{d|f(i)} mu(d)\ end{aligned}$

注意到當 $d$ 有平方項時 $mu(d) =0$ ，而 $f(i)$ 根據定義是個平方數，所以如果 $mu(d) e 0$ ，可以得知 $d^2$ 也整除 $f(i)$ 。

所以：

$egin{aligned} end{aligned}$ $egin{aligned} &= sum_{i = 1}^n sum_{d|f(i)} mu(d)\ &= sum_{i = 1}^n sum_{color{red}{d^2|f(i)}} mu(d)\ &= sum_{d = 1}^n mu(d) sum_{color{red}{d^2|i,ile n}}1 & ext{我們換個序}\ &= sum_{d = 1}^n mu(d)color{red}{ lfloorfrac{n}{d^2} floor} \ &= sum_{d = 1}^{color{red}{lfloorsqrt{n} floor}} mu(d) lfloorfrac{n}{d^2} floor \ end{aligned}$

希望你讀懂了：）