Results 1 to 9 of 9

Math Help - Limit of an interesting sequence

  1. #1
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Limit of an interesting sequence

    Problem: Fix n_0\in\mathbb{N} and let m,n_0)=1\right\}" alt="E_n=\left\{m\leqslant nm,n_0)=1\right\}" /> (i.e. the set of all m\leqslant n where m and n_0 are coprime). Then, define a_n=\text{card }E_n. Compute \displaystyle \lim_{n\to\infty}\frac{a_n}{n}.

    Remark: I recently solved this problem on my blog, if you have seen it I would ask you refrain from answering.
    Last edited by Drexel28; November 4th 2010 at 06:47 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    What is card?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Also sprach Zarathustra View Post
    What is card?
    Cardinality
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    Problem: Fix n_0\in\mathbb{N} and let m,n_0)\right\}" alt="E_n=\left\{m\leqslant nm,n_0)\right\}" /> (i.e. the set of all m\leqslant n where m and n_0 are coprime). Then, define a_n=\text{card }E_n. Compute \displaystyle \lim_{n\to\infty}\frac{a_n}{n}.

    Remark: I recently solved this problem on my blog, if you have seen it I would ask you refrain from answering.
    I guess you mean m,n_0)=1\right\}" alt="E_n=\left\{m\leqslant nm,n_0)=1\right\}" />.

    Isn't it just the product of the (1-1/p) where p ranges over the prime divisors of n, i.e. the proportion of integers relatively prime to n_0?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    I guess you mean m,n_0)=1\right\}" alt="E_n=\left\{m\leqslant nm,n_0)=1\right\}" />.

    Isn't it just the product of the (1-1/p) where p ranges over the prime divisors of n, i.e. the proportion of integers relatively prime to n?
    Yes, that is what I mean. And I don't know, is it? >:]
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Welcome back on MHF by the way
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    Yes, that is what I mean. And I don't know, is it? >:]
    Yes, it is. This is barely a challenge problem! (*with n_0 instead of n )
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    Yes, it is. This is barely a challenge problem! (*with n_0 instead of n )
    Ah, ****. My bad then. You see, the one subject I am truly ignorant of is number theory. That said, the way I devised of doing it was probably much more difficult than the number theoretic approach. What I did was (sketch):

    Spoiler:
    If n_0=p_1^{\alpha_1}\cdots p_k^{\alpha_k} then (m,n_0)\ne1 \Leftrightarrow p_1\mid m\text{ or }\cdots\text{ or }p_k\mid m. Thus, if _j\mid m\right\}" alt="A_{j,n}=\left\{m\leqslant n_j\mid m\right\}" /> we see that

    [n]=E_n\sqcup\left(A_{1,n}\cup\cdots\cup A_{k,n}\right)

    where the square cup just means that \left\{E_n,A_{1,n}\cup\cdots\cup A_{k,n}\right\} forms a partition of [n]. Thus, a_n=n-\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|. But, by the inclusion exclusion principle

    \displaystyle \left|A_{1,n}\cup\cdots\cup A_{k,n}\right|=\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left|\bigcap_{s\in S}A_{s,n}\right|

    where S_j=\left\{S\subseteq [k]:|S|=j\right\}. Thus, noticing that any subcollection of \{p_1,\cdots,p_k\} is a family of coprime numbers we see that

    _s\mid m\text{ for all }s\in S\right\}=\left\{m\leqslant n:\prod_{s\in S}p_s\mid m\right\}" alt="\displaystyle \bigcap_{s\in S}A_{s,n}=\left\{m\leqslant n_s\mid m\text{ for all }s\in S\right\}=\left\{m\leqslant n:\prod_{s\in S}p_s\mid m\right\}" />

    From where simple reasoning leads us to

    \displaystyle\left|\bigcap_{s\in S}A_{s,n}\right|=\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor

    Thus,

    \displaystyle a_n=n-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor

    From where it quickly follows that

    \displaystyle \lim_{n\to\infty}\frac{a_n}{n}=1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left(\prod_{s\in S}p_s\right)^{-1}

    At least we know now that

    \displaystyle \prod_{j=1}^{k}\left(1-\frac{1}{p_j}\right)=1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left(\prod_{s\in S}p_s\right)^{-1}

    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    Yes, it is. This is barely a challenge problem! (*with n_0 instead of n )
    OH MY GOD! Is the number theoretic way to do it this:

    Spoiler:
    Let n_0=p_1^{\alpha_1}\cdots p_k^{\alpha_k}

    Notice that (m,n_0)=1\Leftrightarrow (m+n_0\ell,n_0)=1. Thus, one can easily see that E_{n_0(n+1)}=E_{nn_0}\cup\left\{k+n_0n:k\in E_{n_0}\right\}. It easily follows then by induction that a_{nn_0}=na_{n_0}. But, evidently by definition a_{n_0}=\varphi(n_0). Thus, a_{nn_0}=n\varphi(n_0). So, notice that a_n is increasing since E_n\subseteq E_{n+1}. Then, if \gamma_{n_0} denotes reduction \text{ mod }n_0 that

    a_{n-\gamma_{n_0}(n)}\leqslant a_n\leqslant a_{n+n_0-\gamma_{n_0}(n)}

    But, notice that since n_0\mid n-\gamma_{n_0}(n),n+n_0-\gamma_{n_0}(n) that \frac{n_0-\gamma_{n_0}(n)}{n_0},\frac{n+n_0-\gamma_{n_0}(n)}{n_0} are both integers. Thus, our previous discussion applies and tells us that

    \displaystyle a_{n-\gamma_{n_0}(n)}=a_{n_0\left[\frac{n-\gamma_{n_0}(n)}{n_0}\right]}=\varphi(n_0)\frac{n-\gamma_{n_0}}{n_0}

    and

    \displaystyle a_{n+n_0-\gamma_{n_0}(n_0)}=a_{n-0\left[\frac{n+n_0-\gamma_{n_0}(n)}{n_0}\right]}=\varphi(n_0)\left[\frac{n+n_0-\gamma_{n_0}(n)}{n_0}\right]

    Notice then though that clearly

    \displaystyle \lim_{n\to\infty}\frac{\varphi(n_0)}{n}\left[\frac{n-\gamma_{n_0}(n)}{n_0}\right]=\lim_{n\to\infty}\frac{\varphi(n_0)}{n}\left[\frac{n+n_0-\gamma_{n_0}(n)}{n_0}\right]=\frac{\varphi(n_0)}{n_0}

    So, that by the squeeze theorem it follows that

    \displaystyle \lim_{n\to\infty}\frac{a_n}{n}=\frac{\varphi(n_0)}  {n_0}=\frac{1}{n_0}\left(n_0\prod_{j=1}^{k}\left(1-\frac{1}{p_j}\right)\right)=\prod_{j=1}^{k}\left(1-\frac{1}{p_j}\right)


    My mind is blown.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. An interesting limit
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 22nd 2010, 12:04 PM
  2. interesting probability puzzle involving out-of-sequence series
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: November 20th 2010, 11:58 AM
  3. Interesting sequence - find closed form
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 30th 2009, 09:38 AM
  4. Interesting Limit
    Posted in the Calculus Forum
    Replies: 2
    Last Post: June 10th 2009, 11:44 AM
  5. interesting limit
    Posted in the Calculus Forum
    Replies: 3
    Last Post: August 29th 2007, 09:58 PM

Search Tags


/mathhelpforum @mathhelpforum