Tuesday, March 29, 2011

Dirichlet convolution is commutative

The Dirichlet convolutions was introduced here.  The following illustrates a proof technique that avoids writing ` \frac{n}{d} ` over and over again.
Theorem
Proof:-
For any ` n ` we have
   ` (f \mbox{*} g)(n)  `
= ` \sum_{n=cd}f (c) \cdot g(d) `
= ` \sum_{n=cd}f (d) \cdot g(c) `  [ as ` d ` runs through all divisors of  ` n `, so does ` c = \frac{n}{d} ` ]
= ` \sum_{n=cd}g(c) \cdot f(d) `
= ` (g \mbox{*} f)(n)  `
(proven) 

The proof technique can be extended to prove the associativity law.

No comments:

Post a Comment

Comment répondez vous?