Tuesday, March 29, 2011

Dirchlet Convolution is Distributive over Addition


The Dirichlet Convolution has the following property:-

The proof is a straightforward exercise.


Proof:-

For any ` n ` we have
   ` [f \mbox{*} (g + h)](n)  `
= ` \sum_{d|n}f(d) \cdot (g+h)(n/d) `
= ` \sum_{d|n}\{ f(d) \cdot g(n/d) + f(d) \cdot h(n/d) \}`
= ` \sum_{d|n}f(d) \cdot g(n/d) + \sum_{d|n}f(d) \cdot h(n/d) `
= ` (f \mbox{*}g)(n) + (f \mbox{*}h)(n)  `
= ` (f \mbox{*}g + f \mbox{*}h)(n)  `

(proven)

No comments:

Post a Comment

Comment répondez vous?