1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Sequence of rationals converging to an irrational limit

  1. Aug 23, 2009 #1
    1. The problem statement, all variables and given/known data
    If [tex](p_n/q_n)_{n \in \mathbb{N}}[/tex] is a sequence of rationals in lowest terms converging to the irrational number [tex]x > 0[/tex], then [tex]\lim_{n \to \infty} q_n = +\infty[/tex].

    2. Relevant equations

    3. The attempt at a solution
    I'm quite clueless about this. But heuristically, I understand the following. Let [tex]x > 0[/tex] be an irrational number and consider any sequence [tex](x_n)[/tex] such that [tex]\lim x_n = x[/tex]. By the Density of [tex]\mathbb{Q}[/tex], we can construct a subsequence [tex](x_{n_k})[/tex] of rationals for all [tex]k \in \mathbb{N}[/tex]. And since [tex]\lim x_n = x[/tex], it implies [tex]\lim_{k \to \infty} x_{n_k} = x[/tex] and thus, this is an instance for which a sequence of rationals converging to an irrational limit.

    As another illustration, I understand that if a sequence [tex](s_n)[/tex] given as [tex]s_n = \sqrt{2} + 1/n[/tex] is a sequence of IRRATIONAL numbers converging to an IRRATIONAL limit.

    However, I cannot quite see why or how to prove this result! I'd appreciate any help!
  2. jcsd
  3. Aug 23, 2009 #2
    Since finding a limit is dependent on getting xn within epsilon of x, then any rational number in an interval of length epsilon must have a denominator of at least [itex]\lceil 1/ \epsilon \rceil[/itex]. Since this can be done for any epsilon, then the donominator much become infinitely great. Proving this rigorously might be sticky though.


    EDIT: Slight errors here. This is true for infinitely many epsilon, but not all. In the limit though qn must go to infinity.
    Last edited: Aug 23, 2009
  4. Aug 24, 2009 #3
    Thanks Elucidus --- I mean, in that heuristic manner, I see that the denominator must go to infinity as well. But is there a rigorous argument for this?

    Thanks :)
  5. Aug 24, 2009 #4


    User Avatar
    Homework Helper

    How about proof by contradiction?

    Let xn be a sequence such that: [tex]\mathbb{Q} \supset x_n = \frac{p_n}{q_n} \rightarrow x[/tex].

    Now assume that qn is bounded, i.e [tex]\exists N_0 > 0 : |q_n| < N_0 , \forall n[/tex]

    There must exist some natural number k, such that: k < x < k + 1.

    And since [tex]x_n \rightarrow x \Rightarrow \exists N_1 \in \mathbb{N} : x_n \in (k, k + 1), \forall n > N_1[/tex].

    Now, we only consider the cases when [tex]x_n \in (k, k + 1)[/tex], i.e, we only consider the cases when n > N1.

    When n > N1, let's see if you can answer the following question:
    1. What is the total number of possible values for pn?
    2. Since qn is upper bounded, what is the total number of possible value for qn?
    3. What is the total number for possible value of pn/qn, is it finite, or infinite?
    4. Now, if you find the min value of |pn/qn - x|, for n > N1, can that value be 0?
    5. What can you conclude about this?
  6. Aug 24, 2009 #5
    @VietDao29 Ahh... thanks! Here's an attempt based on your hints that's hopefully correct!

    Suppose [tex]x_n = p_n / q_n \to x[/tex] where [tex](x_n)[/tex] is a sequence of rational numbers and [tex]x > 0[/tex] is an irrational number. For contradiction, suppose that [tex]\lim_{n \to \infty} q_n \ne +\infty[/tex]; that is, there exists some [tex]N_0 \in \mathbb{N}[/tex] such that [tex]|q_n| \leq N_0[/tex] for all [tex]n \in \mathbb{N}[/tex]. Note that we can take [tex]N_0[/tex] to be an integer by the fact that the natural numbers are unbounded above.

    Let any [tex]\varepsilon > 0[/tex]. And since [tex]\lim x_n = x[/tex], there exists some [tex]N_1[/tex] such that for all [tex]n > N_1[/tex], [tex]|x_n - x| < \varepsilon[/tex]. By the Archimedian Property, there must exist some [tex]k \in \mathbb{N}[/tex] such that [tex]k < x < k + 1[/tex]. Thus, we can focus on [tex]x_n \in (k, k+1)[/tex].

    Now, consider [tex]n > N_1[/tex]. There must be infinitely many [tex]p_n \in \mathbb{N}[/tex] since the set of natural numbers is countable. And since [tex]q_n \in \mathbb{N}[/tex] is bounded, there must exist only finite number of [tex]q_n \in \mathbb{N}[/tex]. Thus, there are infinitely many number of [tex]p_n / q_n[/tex]'s for [tex]n > N_1[/tex]. Now, consider [tex]\min\{|p_n / q_n - x|: n > N_1\}[/tex]. But since [tex]p_n / q_n \in \mathbb{Q}[/tex] and [tex]x > 0[/tex] is an irrational, the minimum of their difference can not be zero. And thus, we have that for [tex]n > N_1[/tex], [tex]0 \ne \min\{|p_n / q_n - x|: n > N_1\} \leq \lim_{n \to \infty} |p_n / q_n - x|[/tex]. Or that [tex]\lim p_n / q_n \ne x[/tex] --- contradiction.

    Thanks again for the hints --- and please let me know if I've made any errors in the above! I appreciate all your help :)
  7. Aug 24, 2009 #6
    Actually, I have a question ---- perhaps I've completely missed the motivation for doing so, but what is the purpose of focusing [tex]x_n \in (k, k+1)[/tex]? I'm taking a guess but please correct me if I'm wrong; by focusing [tex]x_n[/tex] inside two integers differing only by 1, we can be assured that such [tex]x_n[/tex] will not be too "large". Is this a good interpretation? Thanks again :)
  8. Aug 24, 2009 #7


    User Avatar
    Homework Helper

    No, because I want to restrict the number of possible values for pn. You are wrong pn can only take a finite number of integer values. Think again, let's see if you can find out why pn cannot take whatever values it likes.

    Because you don't use the fact that [tex]x_n \in (k, k + 1)[/tex] for n large enough, this is where you went wrong. It's not always true that a set of numbers have a minimum (smallest element) value, it may have infimum though. The smallest element (also called minimum in totally odered set) of set A is the lower bound of A, and also contains in A. You can have a look http://en.wikipedia.org/wiki/Greatest_element" [Broken] for more information. Hopefully, you know all about inf, sup, min, and max, right?

    I'll give you an example:

    [tex]A = \left\{ \frac{1}{n}, n \in \mathbb{N} ^ {*} \right\}[/tex]

    No element in A is 0, but inf(A) = 0, and A does not have a minimum, since [tex]0 \notin A[/tex].


    But if A is a totally ordered set with finite elements, one can easily show that it always have a minimum, and also a maximum (by proof of induction).

    Now, try to prove that pn can only takes a finite number of value, and see if you can complete the problem. :)

    Hope I am being clear enough. :)
    Last edited by a moderator: May 4, 2017
  9. Aug 24, 2009 #8
    Just because qn does not diverge to infinity, does not mean it is bounded above. You must consider the case that it meanders between between large and small numbers. For example [itex]\{ n + (-1)^n(n)\}_{n=0}^{\infty}[/itex] is neither divergent to infinity, nor is it bounded above.

    This reminds me of the proof that the denominator function is continuous at all irrational values.

  10. Aug 24, 2009 #9


    User Avatar
    Homework Helper

    Ahhh. yes, my bad. I totally forget that case.. :( Thanks so much for plotting out my mistake. :D

    Ok, so a quick fix is to notice that:

    If qn does not tend to +infinity, then there exists some upper-bounded sub-sequence [tex]q_{n_k}[/tex].

    Let's see if you can prove it. :)

    And you'll work on this sub-sequence to prove that [tex]\frac{p_{n_k}}{q_{n_k}}[/tex] does not converge to x (in exactly the same manner as I showed you before), and hence, neither does the sequence [tex]\frac{p_n}{q_n}[/tex].
  11. Aug 25, 2009 #10
    Hmm.... I got the above discussion regarding why we want to consider [tex]x_n \in (k, k+1)[/tex] as in that case, [tex]\inf \{x_n : n > N_1\} = k[/tex] and likewise, [tex]\sup\{x_n : n > N_1\} = k + 1[/tex] and since we have determined that [tex]q_n[/tex] is a natural number and is bounded, it must be that there are finitely many number of them. This implies that the rational number [tex]x_n = p_n / q_n \in (k, k+1)[/tex] must be finite and thus implying that [tex]p_n[/tex] is finite --- otherwise, if [tex]p_n[/tex] were infinite, then there would exist some [tex]p_M[/tex], [tex]M > N_1[/tex], such that [tex]x_M = p_M / q_M \notin (k, k+1)[/tex], which is not possible.

    I hope the above argument holds.

    But the later argument confuses me a bit. Here are my questions:
    (1) When we say a sequence [tex](a_n)[/tex] such that [tex]\lim a_n = + \infty[/tex], it means that for all [tex]M > 0[/tex] there exists some [tex]N \in \mathbb{N}[/tex] such that [tex]n > N[/tex] implies [tex]a_n > M[/tex].

    Now, the negation of this (I often get these negation things wrong so please correct me I am): There exists some [tex]M > 0[/tex] such that for all [tex]n \in \mathbb{N}[/tex], [tex]a_n \leq M[/tex].

    I guess what I just wrote above is kind of redundant since as pointed out Elucidus, a sequence not diverging to infinity does not mean that it's bounded; i.e. for a sequence to be bounded, we should have for all [tex]n \in \mathbb{N}[/tex], there exists some [tex]M > 0[/tex] such that [tex]|a_n| \leq M[/tex] --- I guess the order of the quantifiers here really matter between the above statement on "not divergent" and "bounded" matter. Is this correct?

    (2) Another question is the justification of the existence of a subsequence [tex](q_{n_k})[/tex] such that it is bounded above. Can you please explain why this must hold? For instance, using Elucidus's example again of [tex](a_n) = \{ n + (-1)^n(n)\}_{n=0}^{\infty}[/tex], if [tex]n = 2k[/tex] is even, then [tex]a_{2k} = 2k + (-1)^{2k}2k = 4k[/tex] but if [tex]n = 2k + 1[/tex] is odd, then [tex]a_{2k+1} = 0[/tex] and thus [tex]a_{2k}[/tex] clearly diverges to infinity. Of course, there are other combinations of subsequences that one can come up with but for this [tex](a_n)[/tex] in particular, I can't see how it can bounded above.

    Sorry for the numerous questions above! I just want to make I have this question crystal clear :) Thanks again to all and I appreciate you for correcting my errors!
  12. Aug 25, 2009 #11


    User Avatar
    Homework Helper

    Well, yes, it's true, but it's not very clear.

    One can ask you why? If you tell them that there exists something, you must also point it out, or at least explain the reason why it must exist.

    You can makes this a little bit clearer, like this:

    [tex]\frac{p_{n_m}}{q_{n_m}} \in (k, k + 1), \forall m > N_1[/tex] (I'm working with sub-sequence), since qnm is positive (as given). By doing a little bit arrangement, one can get to:

    pnm < (k + 1)qnm < (k + 1) M (where M is one upper-bound of qnm)

    Which in turns, means that pnm can not take more than (k + 1) M different values, hence there is just a finite number of choices for it.

    [tex]\lim a_n = \infty[/tex] means that no matter how "large" you want the value of an to be (larger than a given N, for example), there's a natural number k, such that, from ak + 1 on, the value of this sequence is all greater than N (i.e, for all n > k; we have an > N). Or written formally.

    [tex]\forall N > 0, \exists k \in \mathbb{N} : n > k \Rightarrow a_n > N[/tex].

    And yes, you did get the wrong negation of that (note the "for all" part I bold in the previous paragraph). It should be:

    [tex]\exists N > 0, \forall k \in \mathbb{N}, \exists n > k : a_n \leq N[/tex] instead.

    Let's see if you can "construct" any upper-bounded sub-sequence from that negation.


    The subsequence a2n + 1 = 0, for all n is clearly bounded above by 0, or any positive real number x.

    It's no problem. You can ask as many questions as you wish. I'd be more than grateful to help you understand the problem. :)


    If everything is clear, let's see if you can write a formal proof of this. Just give it a try. :)
    Last edited: Aug 25, 2009
  13. Aug 26, 2009 #12

    Sorry for the late reply --- I was busy yesterday so couldn't get around to go on this forum. But thank you for your great responses and help!

    (1) Yah... now I look at it, it's pretty stupid of me to say that for the sequence [tex](a_n) = \{ n + (-1)^n(n)\}_{n=0}^{\infty}[/tex] that the subsequence [tex] a_{2k+1} = 0 [/tex] is "unbounded" when I have already shown that it is equal to 0 no matter what. Stupid mistake :P

    (2) In the proof below, I'd modified your [tex](k, k+1)[/tex] for some [tex]k \in \mathbb{N}[/tex] argument. The reason is the following. We have that [tex]p_{n_k} / q_{n_k}[/tex] are rationals for every [tex]k[/tex] but it is very possible that it takes on a value, say, [tex]p_{n_k} / q_{n_k} = 1000[/tex]; after all, [tex]\frac{1000}{1}[/tex] is a rational. Then in that case, if we still write [tex]k < p_{n_k} / q_{n_k} = 1000 < k + 1[/tex], with strict inequality, I don't think such a [tex]k \in \mathbb{N}[/tex] exists. That is, we can take [tex]k = 999[/tex] but [tex]k + 1 = 1000[/tex] which means the last inequality must be a "[tex]\leq[/tex]". I think it does no harm to generalize it to some [tex]k_1, k_2 \in \mathbb{N}[/tex] and write the interval as [tex](k_1, k_2)[/tex]. What do you think?
  14. Aug 26, 2009 #13
    I think I will now just reconstruct the entire proof from the beginning and here it is. Hope it'll be fine now :)

    Suppose [tex]x_n = p_n / q_n \to x[/tex] where [tex](x_n)[/tex] is a sequence of rational numbers and [tex]x > 0[/tex] is an irrational number. For contradiction, suppose that [tex]\lim_{n \to \infty} q_n \ne +\infty[/tex]; that is [tex]\exists M > 0[/tex] such that [tex]\forall N_0 \in \mathbb{N}[/tex], [tex]\exists n > N_0[/tex] such that [tex]q_n \leq M[/tex].

    Consider a subsequence [tex](x_{n_k}) = (p_{n_k} / q_{n_k})[/tex] constructed as follows. Set [tex]n_k = N_0 + k[/tex] and clearly, by this choice, we have [tex]n_1 < n_2 < \ldots [/tex]. And hence, by induction, we can have a subsequence [tex](x_{n_k}) = (p_{n_k} / q_{n_k})[/tex]. But since [tex]q_n \leq M[/tex], it follows that [tex]q_{n_k} \leq M[/tex] for [tex]\forall k \in \mathbb{N}[/tex].

    Furthermore, since [tex](x_n)[/tex] is convergent, the subsequence [tex](x_{n_k})[/tex] is convergent and so it is bounded and thus we can pick some [tex]k_1, k_2 \in \mathbb{N}[/tex] such that [tex]x_{n_k} = p_{n_k} / q_{n_k} \in (k_1, k_2)[/tex]. Now, see that [tex]k_1 < \frac{p_{n_k}}{q_{n_k}} < k_2[/tex], rearrange, [tex]k_1 \cdot q_{n_k} < p_{n_k} < k_2 \cdot q_{n_k} \leq k_2 \cdot M[/tex]. And since [tex]p_{n_k}[/tex]'s are integers, it implies that although there are infinitely many [tex]p_{n_k}[/tex]'s, they can only take on finite number of values (i.e. some of the values repeat themselves).

    Now consider [tex]\inf\{|x_{n_k} - x| : k \in \mathbb{N}\} = \inf \{|p_{n_k} / q_{n_k} - x| : k \in \mathbb{N}\}[/tex]. Since [tex]q_{n_k}[/tex]'s are integers and are bounded, so it can only take on finite number of values; similarly, we had shown that [tex]p_{n_k}[/tex]'s are integers and can only take a finite number of values. Thus, there are only finite number of values for [tex]x_{n_k}[/tex] for [tex]\forall k \in \mathbb{N}[/tex] and all of these values are rationals but [tex]x[/tex] is irrational. Thus it follows that [tex]\inf\{|x_{n_k} - x| : k \in \mathbb{N}\} \ne 0[/tex]. It thus follows that [tex]0 \ne \inf\{|x_{n_k} - x| : k \in \mathbb{N}\} \leq \lim_{k \to \infty} |x_{n_k} - x| [/tex] or that [tex]\lim x_{n_k} \ne x[/tex], but since we assumed [tex]\lim x_n = x[/tex] --- contradiction, if a sequence converges, every subsequence converges to the same limit.
    Last edited: Aug 26, 2009
  15. Aug 26, 2009 #14
    never mind...
  16. Aug 27, 2009 #15


    User Avatar
    Homework Helper

    No, as pointed out by Elucidus, if a sequence does not tend to +infinity, it does not mean that it's upper bounded. But instead, there's some (at least 1) sub-sequence in it that is bounded above. And you'll work on that sub-sequence, constructing from the negation of:

    [tex]\forall N > 0, \exists k \in \mathbb{N} : n > k \Rightarrow a_n > N[/tex],

    which should be:

    [tex]\exists N > 0, \forall k \in \mathbb{N}, \exists n > k : a_n \leq N[/tex]

    Ok, fine. But remember that it should be a sub-sequence of a sub-sequence (where qn is upper-bounded) instead.

    This part is fine. Although in this inequality, you may omit the k1qnk < pnk part, since it does not help much, more over qnk varies, and so does k1qnk. Putting it there is okay, but no use, so we may just drop it. :)

    [tex]k_1 \cdot q_{n_k} < p_{n_k} < k_2 \cdot q_{n_k} \leq k_2 \cdot M[/tex]

    No, we don't find the inf of it, instead, we find the min. Because that set is finite, so there exists the minimum.

    The main different between the inf, and the min of a set is that. The inf does not contain in the set, while the min does.

    And if you are using inf in this case, you cannot prove that its value is not 0.

    I gave you an example in some earlier post. Consider the set:

    [tex]A = \left\{ \frac{1}{n}, n \in \mathbb{N} ^ {*} \right\}[/tex]

    0 is nowhere to be in A. But the infimum of A is indeed 0. :)

    And since 0 is not in A, so this set does not have minimum value.

    Fine. :D


    Now, there's only one little problem left is to show that:

    If a sequence does not tend to +infinity, then there's some sub-sequence of it, which is bounded above. Let's see how far you can get.

    Yes, you can, but remember that x is irrational, so x cannot be either k, or k + 1.

    And moreover, since your sequence tends to x, i.e, it'll be "close" enough to x when n is large enough. So if it happens that at some n0, an0 = k, or an0 = k + 1, it just means that n0 is not "large" enough.

    Yes, of course, you can. It's all up to you, as long as you can prove that the number of choices for pn is finite.
  17. Aug 27, 2009 #16
    Hmm... I think the subsequence I'd shown, obtained through an inductive construction, should be bounded above. While our notations vary slightly, but the negation I wrote is exactly what you wrote. And from that negated statement, I'd constructed a subsequence such that it is bounded above. (Of course, I cannot "negate" the fact that I'm wrong, again).

    Actually, just rereading what I'd written on that construction, there's a slight flaw but not fatal (thankfully). I should have written: Set [tex]n_1 > N_0[/tex] so that [tex]q_{n_1} \leq M[/tex] and let [tex]x_{n_1} = p_{n_1} / q_{n_1}[/tex]. And since the aforementioned negated statement holds for [tex]\forall N_0[/tex] where [tex]\exists n > N_0[/tex], we can be sure that there are infinitely many choices of [tex]n[/tex] to have [tex]n_1 < \ldots < n_k[/tex]. Hence, by induction, we have [tex]q_{n_k} \leq M[/tex] and [tex]x_{n_k} = p_{n_k} / q_{n_k} [/tex] for [tex]\forall k \in \mathbb{N}[/tex]. The error was that setting [tex]n_k = N_0 + k[/tex], which is clearly incorrect because the negated statement said [tex]\exists n > N_0[/tex] but it is definitely not necessarily true that this [tex]n = N_0 + k[/tex] (i.e. it must be true that "there exists" this k, but definitely not for "all" k).

    Agreed :)

    I see... I think I got a little confused with the set [tex]\{ x_{n_k} = p_{n_k} / q_{n_k} : k \in \mathbb{N} \}[/tex] since there are indeed infinitely many [tex]x_{n_k}[/tex]'s but it can only take on finite number of values. I agree --- since the set is finite, a minimum (in fact a maximum) as well exists. Just nitpicking but of course, we know that if the minimum / maximium exists, it must equal the infimum / supremum :)

    Thanks :)

    Once again, thanks a lot for your fantastic help on this problem!
    PS. This is actually a hint to a much bigger problem and I'm actually even having trouble justifying the hint.....
  18. Aug 27, 2009 #17


    User Avatar
    Homework Helper

    You're welcome. :)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook