名古屋大学 情報学研究科 数理情報学専攻 2017年8月実施 問題3 離散数学

Author

祭音Myyura

Description

以下の各問に答えよ。

(1)

を非負の整数で定義される関数とする。非負の整数 に対して関数 を

と定める、このとき,

が成立することを示せ。

(2)

を Mobius 関数とする。すなわち、正の整数に対して

とする。

(i)

正の整数 に対して、

が成立することを示せ。ただし、 は のすべての正の約数を動くものとする。

(ii)

を正の整数で定義される関数とする。正の整数 に対して関数 を

と定める。 このとき、

が成立することを示せ。

Kai

(1)

By the binomial theorem

hence

(2)

(i)

The statement clearly holds if .

Assume that and by the fundamental theorem of arithmetic we write

In the sum the only non-zero terms come from and the divisors of which are products of distinct primes.

From the definition of Binomial coefficient, there are ways to choose primes from to multiply together.

Thus:

(ii)

(This is the so-called Mobius inversion formula)

By using the result of Question (2)-(i), i.e.,

If we have , i.e., then we have

and that if otherwise. Hence by considering we get