Results 1 to 3 of 3

Math Help - Arithmetic functions

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    Arithmetic functions

    For two arithmetic functions A(n) and B(n) show that

    \sum_{d|n} A(d)B(n/d) = \sum_{d|n} A(n/d)B(d)

    I figure I need to use the inverse mobius transform somehow but I'm unsure as to what A and B should be in regards to the formula below taken from my notes...

    If F(n) = \sum_{d|n}f(d) for every integer n \geq 1

    then

    f(n)=\sum_{d|n}\mu(n/d)F(d) for every integer n \geq 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Deadstar View Post
    For two arithmetic functions A(n) and B(n) show that

    \sum_{d|n} A(d)B(n/d) = \sum_{d|n} A(n/d)B(d)

    I figure I need to use the inverse mobius transform somehow but I'm unsure as to what A and B should be in regards to the formula below taken from my notes...

    If F(n) = \sum_{d|n}f(d) for every integer n \geq 1

    then

    f(n)=\sum_{d|n}\mu(n/d)F(d) for every integer n \geq 1
     d\mid n \iff \frac{n}{d}\mid n .

    Therefore  \sum_{d\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{\frac{n}{d}\mid n} A(d)B\left(\frac{n}{d}\right) .

    Let  q=\frac{n}{d} \implies d=\frac{n}{q}

    Thus  \sum_{d\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{\frac{n}{d}\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{q\mid n} A\left(\frac{n}{q}\right)B(q) .


    In summary, the identity you're trying to prove simply reverses the order in which the terms are summed.
    Last edited by chiph588@; March 22nd 2010 at 02:27 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by chiph588@ View Post
     d\mid n \iff \frac{n}{d}\mid n .

    Therefore  \sum_{d\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{\frac{n}{d}\mid n} A(d)B\left(\frac{n}{d}\right) .

    Let  q=\frac{n}{d} \implies d=\frac{n}{q}

    Thus  \sum_{d\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{\frac{n}{d}\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{q/mid n} A\left(\frac{n}{q}\right)B(q) .


    In summary, the identity you're trying to prove simply reverses the order in which the terms are summed.
    Great thanks, that's actually exactly what I had (except I had k = n/d...) but I didn't think it was right so I scrapped it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof with arithmetic functions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 24th 2009, 05:58 AM
  2. Multiplicative Arithmetic Functions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 3rd 2009, 06:47 PM
  3. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 8th 2009, 12:36 AM
  4. Arithmetic Functions
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 4th 2008, 12:53 PM
  5. Arithmetic Functions.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 5th 2008, 01:50 PM

Search Tags


/mathhelpforum @mathhelpforum