Results 1 to 9 of 9

Thread: Limit of an interesting sequence

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

    Limit of an interesting sequence

    Problem: Fix $\displaystyle n_0\in\mathbb{N}$ and let $\displaystyle E_n=\left\{m\leqslant nm,n_0)=1\right\}$ (i.e. the set of all $\displaystyle m\leqslant n$ where $\displaystyle m$ and $\displaystyle n_0$ are coprime). Then, define $\displaystyle a_n=\text{card }E_n$. Compute $\displaystyle \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; Nov 4th 2010 at 05: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
    22
    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 $\displaystyle n_0\in\mathbb{N}$ and let $\displaystyle E_n=\left\{m\leqslant nm,n_0)\right\}$ (i.e. the set of all $\displaystyle m\leqslant n$ where $\displaystyle m$ and $\displaystyle n_0$ are coprime). Then, define $\displaystyle a_n=\text{card }E_n$. Compute $\displaystyle \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 $\displaystyle E_n=\left\{m\leqslant nm,n_0)=1\right\}$.

    Isn't it just the product of the $\displaystyle (1-1/p)$ where $\displaystyle p$ ranges over the prime divisors of $\displaystyle n$, i.e. the proportion of integers relatively prime to $\displaystyle 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
    22
    Quote Originally Posted by Bruno J. View Post
    I guess you mean $\displaystyle E_n=\left\{m\leqslant nm,n_0)=1\right\}$.

    Isn't it just the product of the $\displaystyle (1-1/p)$ where $\displaystyle p$ ranges over the prime divisors of $\displaystyle n$, i.e. the proportion of integers relatively prime to $\displaystyle 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 $\displaystyle n_0$ instead of $\displaystyle 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
    22
    Quote Originally Posted by Bruno J. View Post
    Yes, it is. This is barely a challenge problem! (*with $\displaystyle n_0$ instead of $\displaystyle 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 $\displaystyle n_0=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ then $\displaystyle (m,n_0)\ne1 \Leftrightarrow p_1\mid m\text{ or }\cdots\text{ or }p_k\mid m$. Thus, if $\displaystyle A_{j,n}=\left\{m\leqslant n_j\mid m\right\}$ we see that

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

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

    $\displaystyle \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 $\displaystyle S_j=\left\{S\subseteq [k]:|S|=j\right\}$. Thus, noticing that any subcollection of $\displaystyle \{p_1,\cdots,p_k\}$ is a family of coprime numbers we see that

    $\displaystyle \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 \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 \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 \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 \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
    22
    Quote Originally Posted by Bruno J. View Post
    Yes, it is. This is barely a challenge problem! (*with $\displaystyle n_0$ instead of $\displaystyle n$ )
    OH MY GOD! Is the number theoretic way to do it this:

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

    Notice that $\displaystyle (m,n_0)=1\Leftrightarrow (m+n_0\ell,n_0)=1$. Thus, one can easily see that $\displaystyle 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 $\displaystyle a_{nn_0}=na_{n_0}$. But, evidently by definition $\displaystyle a_{n_0}=\varphi(n_0)$. Thus, $\displaystyle a_{nn_0}=n\varphi(n_0)$. So, notice that $\displaystyle a_n$ is increasing since $\displaystyle E_n\subseteq E_{n+1}$. Then, if $\displaystyle \gamma_{n_0}$ denotes reduction $\displaystyle \text{ mod }n_0$ that

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

    But, notice that since $\displaystyle n_0\mid n-\gamma_{n_0}(n),n+n_0-\gamma_{n_0}(n)$ that $\displaystyle \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 \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 \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 \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 \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: Nov 22nd 2010, 11:04 AM
  2. interesting probability puzzle involving out-of-sequence series
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Nov 20th 2010, 10:58 AM
  3. Interesting sequence - find closed form
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Sep 30th 2009, 08:38 AM
  4. Interesting Limit
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Jun 10th 2009, 10:44 AM
  5. interesting limit
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Aug 29th 2007, 08:58 PM

Search Tags


/mathhelpforum @mathhelpforum