# Choice of $q$ in Baby Rudin's Example 1.1

First, my apologies if this has already been asked/answered. I wasn't able to find this question via search.

My question comes from Rudin's "Principles of Mathematical Analysis," or "Baby Rudin," Ch 1, Example 1.1 on p. 2. In the second version of the proof, showing that sets A and B do not have greatest or lowest elements respectively, he presents a seemingly arbitrary assignment of a number $$q$$ that satisfies equations (3) and (4), plus other conditions needed to show that $$q$$ is the right number for the proof. As an exercise, I tried to derive his choice of $$q$$ so that I may learn more about the problem.

If we write equations (3) as $$q = p - (p^2 - 2)x$$, we can write (4) as

$$q^2 - 2 = (p^2 - 2)[1 - 2px + (p^2 - 2)x^2].$$

Here, we need a rational $$x > 0$$, chosen such that the expression in $$[...]$$ is positive. Using the quadratic formula and the sign of $$(p^2 - 2)$$, it can be shown that we need

$$x \in \left(0, \frac{1}{p + \sqrt{2}}\right) \mbox{ for } p \in A,$$

or, for $$p \in B$$, $$x < 1/\left(p + \sqrt{2}\right)$$ or $$x > 1/\left(p - \sqrt{2}\right)$$.

Notice that there are MANY solutions to these equations! The easiest to see, perhaps, is letting $$x = 1/(p + n)$$ for $$n \geq 2$$. Notice that Rudin chooses $$n = 2$$ for his answer, but it checks out easily for other $$n$$.

The Question: Why does Rudin choose $$x = 1/(p + 2)$$ specifically? Is it just to make the expressions work out clearly algebraically? Why doesn't he comment on his particular choice or the nature of the set of solutions that will work for the proof? Is there a simpler derivation for the number $$q$$ that I am missing?

• Maybe he did, after all it is not that deep. Walter Rudin was an excellent author.
Dec 20 '10 at 17:40
• There is a good explanation to your question on page 3 of this file (math.berkeley.edu/~gbergman/ug.hndts/m104_Rudin_exs.pdf) In addition, there are many helpful supplemental exercises and answers to many questions that came up during the course of a Rudin analysis class on the page it came from (math.berkeley.edu/~gbergman/ug.hndts/#Rudin). Dec 20 '10 at 17:46
• The title is uninformative.
– lhf
Aug 5 '11 at 16:37
• @menag I think OP wants to know how does the author comes up with that formula for $q$.
– user175968
Jan 2 '17 at 11:49
• Yes, I would like to see the construction of q Jan 2 '17 at 11:50

Rudin's approximation to $\sqrt{2}$ arises simply by applying by the secant method - a difference analog of Newton's method for finding successively better approximations to roots.

As the linked Wikipedia article shows, the recurrence relation for the secant method is as below.

$$\rm S_{n+1}= \dfrac{S_{n-1}\ f\:(S_n) - S_n\ f\:(S_{n-1})}{f\:(S_n)-f\:(S_{n-1})}\qquad\qquad\qquad\qquad$$

For $\rm\ (S_{n-1},S_n,S_{n+1}) = (q,p,p')\$ and $\rm\ f\:(x) = x^2-d\:,\:$ we obtain

$$\rm p'\ =\ \dfrac{q\:(p^2-d) - p\:(q^2-d)}{p^2-d-(q^2-d)}\ =\ \dfrac{(p-q)\:(p\:q+d)}{p^2-q^2}\ =\ \dfrac{p\:q+d}{p+q}$$

Finally specializing $\rm\: q = 2 = d\:$ yields Rudin's approximation $\rm\displaystyle\ p'\ =\ \frac{2\:p+2}{\ \:p+2}$

The secant method has stunningly beautiful connections with the group law on conics. To learn about this folklore, I highly recommend Sam Northshield's Associativity of the Secant Method. The reader already familiar with the group law on elliptic curves, but unfamiliar with the degenerate case of conics, might also find helpful some of Franz Lemmermeyer's expositions, e.g. Conics - a poor man's elliptic curves.

• Thank you for this! Though there's one thing I don't understand: the secant method tells us that in certain cases the sequence ${(S_{n})}$ will converge to the root of the given function, but does it also tell us that the value $S_{n}$ will be closer to the root than $S_{n-1}$? How does Rudin know that p' will be closer to the root than p and not farther away? Aug 25 '16 at 11:59
• The Associativity link is dead Oct 10 '17 at 16:20
• @frogeyedpeas I fixed it Mar 28 '18 at 16:25
• @Rasputin Generally monotonicity is the trick: if $p<\sqrt{2}$ then $\left ( \frac{2p+2}{p+2} \right )^2 = \frac{4p^2+8p+4}{p^2+4p+4}=2\frac{2p^2+4p+2}{p^2+4p+4}<2$, because the denominator of the last expression is equal to the numerator plus $2-p^2$. On the other hand, $q>p$ is apparent from the form $q=p-\frac{p^2-2}{p+2}$.
– Ian
Jun 10 '18 at 4:20
• @Rasputin Actually there's nothing that guarantees that $S_n>S_{n+1}$ or that $S_n<S_{n+1}$ just due to the Secant Method, what you can do however is to once you use the Secant Method to get some expression is to see whether that is the case (if it's not then you have to use some other method). Oct 17 '19 at 10:28

The point here is that iterations of the Möbius transformation $p \mapsto \frac{2p+2}{p+2}$ converge to $\sqrt{2}$, so every time you apply the transformation you get closer to $\sqrt{2}$. This can be thought of as describing a generalized continued fraction

$$2 - \cfrac{2}{4 - \cfrac{2}{4 - \cfrac{2}{\cdots}}}$$

for $\sqrt{2}$. The dynamics of Möbius transformations in general are fairly well-understood; for the transformation $p \mapsto \frac{ap+b}{cp+d}$ the possible fixed points are the roots of the quadratic polynomial $cp^2 + dp = ap + b$, and using the Banach fixed point theorem (or a more specific closed form of iterations of Möbius transformations using linear algebra) one can determine which of the fixed points are attractive or repellent.

So if one wanted to design a Möbius transformation converging to $\sqrt{n}$ for some non-square $n$, this would require that $d = a, c = 1, b = n$, giving

$$p \mapsto \frac{ap + n}{p + a}$$

for some $a$, and it should not be hard to find a value of $a$ such that the fixed point $\sqrt{n}$ is attractive.

While this technique is a nice trick, because the polynomial $cp^2 + dp = ap + b$ is quadratic, it does not generalize to prove the corresponding result for roots of cubic or higher degree polynomials.

• So it seems that you can create linear fractional transformations that converge to square roots. Are there any other types of transformations that one could create to converge to (say) $\sqrt[3]{3}$? Dec 20 '10 at 19:44
• What is [3]? If it's just 3, then this is sqrt{27}, so it falls under the scope of the construction I laid out. More generally I believe you should be able to write down a Mobius transformation converging to any root of a quadratic polynomial with integer (equivalently, rational) coefficients. Dec 20 '10 at 19:46
• Edited. I meant the cube root of 3. Dec 20 '10 at 19:54
• @Trevor: the corresponding thing to try would be something like p -> (ax + 3)(x^2 + a) for some a. But I have not done the computations to check if we can choose a such that sqrt[3]{3} is an attractive fixed point. In any case, this kind of argument gets more unwieldy the more complicated the number you try to do it with; a much more uniform way to prove the corresponding result for arbitrary irrational numbers a is to use, for example, the truncations of the decimal expansion of a or the convergents to its (ordinary) continued fraction. Dec 20 '10 at 20:00
• Halley's method for solving $x^3 = 3$ is the iteration $x \to \frac{x(x^3+6)}{2 x^3 + 3}$. This has an attracting fixed point at $3^{1/3}$, maps rationals to rationals, and converges monotonically to that fixed point from any starting point with $x > 0$. Aug 5 '11 at 16:43

In the interest of making this question and answer more self-contained, here is the example in question. My answer is below.

1.1 Example We now show that the equation $$p^{2}=2\tag{1}$$ is not satisfied by any rational $$p .$$ If there were such a $$p,$$ we could write $$p=m / n$$ where $$m$$ and $$n$$ are integers that are not both even. Let us assume this is done. Then (1) implies $$m^{2}=2 n^{2}, \tag{2}$$ This shows that $$m^{2}$$ is even. Hence $$m$$ is even (if $$m$$ were odd, $$m^{2}$$ would be odd), and so $$m^{2}$$ is divisible by $$4 .$$ It follows that the right side of (2) is divisible by 4 , so that $$n^{2}$$ is even, which implies that $$n$$ is even.

$$\qquad$$The assumption that (1) holds thus leads to the conclusion that both $$m$$ and $$n$$ are even, contrary to our choice of $$m$$ and $$n .$$ Hence (1) is impossible for rational $$p$$.

$$\qquad$$We now examine this situation a little more closely. Let $$A$$ be the set of all positive rationals $$p$$ such that $$p^{2}<2$$ and let $$B$$ consist of all positive rationals $$p$$ such that $$p^{2}>2 .$$ We shall show that $$A$$ contains no largest number and $$B$$ contains no smallest.

$$\qquad$$More explicitly, for every $$p$$ in $$A$$ we can find a rational $$q$$ in $$A$$ such that $$p, and for every $$p$$ in $$B$$ we can find a rational $$q$$ in $$B$$ such that $$q.

$$\qquad$$To do this, we associate with each rational $$p>0$$ the number $$q=p-\frac{p^{2}-2}{p+2}=\frac{2 p+2}{p+2}.\tag3$$ Then $$q^{2}-2=\frac{2\left(p^{2}-2\right)}{(p+2)^{2}}.\tag4$$ $$\qquad$$If $$p$$ is in $$A$$ then $$p^{2}-2<0,(3)$$ shows that $$q>p,$$ and (4) shows that $$q^{2}<2 .$$ Thus $$q$$ is in $$A$$.

$$\qquad$$If $$p$$ is in $$B$$ then $$p^{2}-2>0,(3)$$ shows that $$0 and (4) shows that $$q^{2}>2 .$$ Thus $$q$$ is in $$B$$.

(Transcribed from this image)

I think you hit the nail on the head. He was looking for a rational $$y$$ such that $$q = p+y$$ will have the desired properties in both cases.

First, if $$p \in A$$ we want $$p 0$$ and if $$p \in B$$ we want $$p>q \Leftrightarrow y < 0$$. We might as well take advantage of the sign of $$p^2-2$$ in each case to achieve this by searching for a positive quantity $$x$$ such that $$q = p - (p^2-2)x$$.

As you showed, any choice $$0 < x < 1/(p+\sqrt{2})$$ will satisfy the requirements $$p \in A \Rightarrow q \in A$$ and $$p \in B \Rightarrow q \in B$$. He wanted to ensure $$x$$ was rational, and the easiest way to do this is to take $$x = 1/(p+k)$$ where $$k$$ is an integer larger than or equal to $$2$$. There's no need to complicate matters further than that, so he simply chooses the smallest $$k$$ which works, namely $$2$$.

My derivation was the same as yours, and I doubt you could get it more simple than that.

As for why he didn't comment on his choice: well, that's kind of just how Rudin is. He will rarely (if ever?) comment on the motivation for his proofs! It is endearing to some and perhaps a little infuriating to others.

Below I show that Rudin's approximation arises simply by applying by the secant method - a difference analog of Newton's method for finding successively better approximations to roots.

As the linked Wikipedia article shows, the recurrence relation for the secant method is as below.

$$\rm S_{n+1}= \dfrac{S_{n-1}\ f\:(S_n) - S_n\ f\:(S_{n-1})}{f\:(S_n)-f\:(S_{n-1})}\qquad\qquad\qquad\qquad$$

For $\rm\ (S_{n-1},S_n,S_{n+1}) = (q,p,p')\$ and $\rm\ f\:(x) = x^2-d\:,\:$ we obtain

$$\rm p'\ =\ \dfrac{q\:(p^2-d) - p\:(q^2-d)}{p^2-d-(q^2-d)}\ =\ \dfrac{(p-q)\:(p\:q+d)}{p^2-q^2}\ =\ \dfrac{p\:q+d}{p+q}$$

Finally specializing $\rm\: q = 2 = d\:$ yields Rudin's approximation $\rm\displaystyle\ p'\ =\ \frac{2\:p+2}{\ \:p+2}$

The secant method has beautiful connections with the group law on conics. To learn about this folklore, I highly recommend Sam Northshield's Associativity of the Secant Method. The reader already familiar with the group law on elliptic curves, but unfamiliar with the degenerate case of conics, might also find helpful some of Franz Lemmermeyer's expositions, e.g. Conics - a poor man's elliptic curves.

Finally, note this the approximation can be derived purely algebraically as follows.

Given lower and upper approximations to a square-root, we may obtain a better lower approximation $\rm\ p'\$ by $\:$ "composing" $\:$ them,$\$ namely:

THEOREM $\rm\displaystyle\quad\ \ q\ >\ \sqrt d\ > \ p\ \ \:\Rightarrow\:\ \ \sqrt d\ > \ p'\ >\ p\quad\ \ for\quad\ p' \:=\ \frac{p\:q+d}{p+q}$

Proof: $\rm\quad\displaystyle 0\ \: >\ (q-\sqrt d)\ \ (p-\sqrt d)\ =\ p\:q+d - (p+q)\:\sqrt d\ \ \Rightarrow\ \ \sqrt d\ >\ p'$

Finally $\rm\quad\quad\displaystyle p'-p\ =\ \frac{p\:q+d}{p+q} - p\ =\ \frac{\ d - p^2}{p+q}\: >\ 0\ \ \Rightarrow\ \ p'\ >\ p$

• Note This answer was (partially) merged by a moderator from another question (where it was the accepted answer). If anything appears strange (context, etc) it is probably due to the merge. Jun 17 '16 at 14:34

Given a positive rational $p$ with $p^{2} < 2$, Rudin finds a rational $q$ with $q > p$ and $q^{2} < 2$. He finds an expression for $q$ in terms of $p$ which is definitely based on numerical techniques for finding square root of a number. Giving a formula for $q$ without any explanation makes it all the more mysterious and therefore this question came into being.

A much simpler approach is to show that such a $q$ exists without giving a direct formula for it. This is what Hardy does in the first chapter of his book "A Course of Pure Mathematics". Clearly for any given positive integer $n$, we can find find $n + 1$ rational numbers between $1$ and $2$ namely $1, 1 + 1/n$, $1 + 2/n, \cdots, 1 + n/n = 2$. Since $1^{2} < 2 < 2^{2}$, it is evident that in this sequence of rationals there will be a last whose square is less than $2$ and the next one will have its square greater than $2$.

Thus we have two rationals positive rationals $x, y$ such that $x^{2} < 2 < y^{2}$ and $y - x = 1/n$. By taking $n$ large enough it is easy to see that given any positive rational $\epsilon$ we can find positive rationals $x, y$ with $x^{2} < 2 < y^{2}, x < 2, y < 2$ and $y - x < \epsilon$. It thus follows that $y^{2} - x^{2} = (y + x)(y - x) < 4\epsilon$. This means that $(y^{2} - 2) + (2 - x^{2}) < 4\epsilon$ and hence $(y^{2} - 2) < 4\epsilon, (2 - x^{2}) < 4\epsilon$ as both the expressions $(y^{2} - 2), (2 - x^{2})$ are positive.

Now we choose $4\epsilon = 2 - p^{2}$ and then we can find positive rational $x$ such that $2 - x^{2} < 4\epsilon = 2 - p^{2}$ so that $x > p$ and we already have $x^{2} < 2$.

See the smartness of the above technique. Ideally what we need is an approximation (on the lower side) for $\sqrt{2}$ which is better than existing approximation $p$. So we just need to choose a rational between $p$ and $\sqrt{2}$. This is possible without even defining the symbol $\sqrt{2}$ because we have access to numbers $1$ (lower approx to $\sqrt{2}$) and $2$ (higher approx) and then we can divide the gap between $1$ and $2$ as finely as possible to obtain approximations to $\sqrt{2}$ which are as good as we need.

• Hardy says that given any rational $r$, and positive natural $N$, we can find a rational $s$ lying on either side of $r$. And given any two rational numbers we can interpolate successive rational numbers which differ from each other as little as we please. How do we prove these equivalent statements? Oct 6 '16 at 13:51
• @MaxisJaisi: Hardy says that for given $r, N$ we can find an $s$ on either side of $r$ which differs from $r$ by less than $1/N$. Suppose we want an $s$ on right of $r$ (i.e. $s > r$) then we just have to choose a rational $s$ between $r$ and $r + (1/N)$. This is possible because between any two rationals there lies another rational. Similarly we can choose $s$ between $r - 1/N$ and $r$ and this will be less than $r$. Such statements are very obvious and easy to prove (for a student of 11-12 years) and I don't know what more I can say. Oct 6 '16 at 18:48

Here's how I would be motivated to make Rudin's choice.

Say we have rational $$p=\dfrac a b$$ with integers $$a,b; b\ne0$$.

$$p$$ can be close to $$\sqrt2$$ but not equal. That is, $$a-b\sqrt2$$ can be small but not zero.

To find $$c$$ and $$d$$ such that $$c-d\sqrt2$$ is even smaller, multiply by $$2-\sqrt2,$$ which is between $$0$$ and $$1.$$

I.e., $$(a-b\sqrt2)(2-\sqrt2)=\color{blue}{(2a+2b)}-\color{green}{(a+2b)}\sqrt2 < a-b\sqrt2$$.

So take $$\color{blue}{c=2a+2b}; \color{green}{d=a+2b}; q=\dfrac {\color{blue}{c}}{\color{green}{d}}=\dfrac {\color{blue}{{2a+2b}}}{\color{green}{a+2b}}=\dfrac{\color{blue}{2p+2}}{\color{green}{p+2}}$$.

• Great idea! I like this :) Oct 16 '19 at 7:40

I had this same question.

For a very clear explanation, see page 25 and 26 of this.

This is what the OP says in a comment: Yes, I would like to see the construction of $\,q$ . If that's all, then we are lucky; I've recently posted a derivation of the formula as an answer to this question:

Contrary to a statement in an answer by Paramanand Singh, there is nothing mysterious / magical about the formula by Rudin. Seems that another author has been re-inventing the wheel, though :-(

Summary of the know how. To understand why the above link should be followed.
Essential ingredient is the mediant of two fractions. And how the Stern-Brocot tree is formed with help of these mediants. We initialize $p < \sqrt{2}$ and $q > \sqrt{2}$ as: $$p = \frac{m}{n} \quad ; \quad q = \frac{2n}{m}$$ Where $m$ and $n$ are positive integers. Now form the mediant of $p$ and $q$ , two times: $$q := \frac{m+2n}{n+m} \quad ; \quad q := \frac{m+(m+2n)}{n+(n+m)} = \frac{2m+2n}{m+2n} = \frac{2p+2}{p+2}$$ The rightmost formula is already Rudin's.

Too long for a comment.

Bergman has an explanation of this:

Students are baffled by this ‘‘rabbit-out-of-a-hat’’ definition. One should motivate it, or tell the class, ‘‘Take it for granted, without worrying about where it comes from’’ – or something! I generally partially motivate it, noting that if $p^2 < 2$ we want to increase $p$ slightly, while if $p^2 > 2$ we want to decrease it, so the amount we should change it by should be obtained from $p^2 – 2$. A denominator is needed to prevent overshooting, especially when $p$ is large, so we use one that grows with p, but I said the actual choice of denominator $p+2$ can be regarded as the result of trial and error. For a lengthier but more satisfying motivation, see the exercise packet, exercise 1.1:1...

The exercise packet can be found here:

• Thanks. I'm glad I'm not the only person who was confused by this line. Jul 24 '16 at 3:31

This is a serious problem with the way Rudin complicates a simple problem. In order to prove that the set $A$ has no largest element it is not really necessary to find an explicit formula for a member $q\in A$ with $q > p$ where $p$ is a given member of $A$. We only need to prove that if $p \in A$ then there is a $q \in A$ with $q > p$ and for that that we don't need any mysterious / magical formula for $q$ in terms of $p$.

Hardy in his textbook A Course of Pure Mathematics does it so much better and also teaches the way things work in real-analysis. The crux of the argument by Hardy is that the set of positive rationals is partitioned into $A, B$ such that $A \cup B = \mathbb{Q}^{+}, A\cap B = \emptyset$ and further that we can find a member of $A$ and a member of $B$ which are as close to each other as we please.

Clearly $1 \in A, 2 \in B$ and given any positive integer $n$ we have the following chain of increasing rational numbers $$1, 1 + \frac{1}{n}, 1 + \frac{2}{n}, \ldots, 1 + \frac{n}{n} = 2$$ such that successive numbers in the above chain differ by $1/n$. Since the first member of the chain lies in $A$ and the last member of the chain lies in $B$ it follows that there is a last number in the chain which lies in $A$ and the next one belongs to $B$. Thus we have found two rationals $q, r$ with $q \in A, r \in B$ such that $r - q = 1/n$. Thus we can find a member of $A$ and a member of $B$ which are as close to each other as we please. Moreover we can choose $q, r$ both less than 2.

Now suppose we have a $p \in A$ then by definition of $A$ we have $p^{2} < 2$ and hence $\epsilon = 2 - p^{2}$ is a positive rational number. We can now find a positive integer $n$ such that $1/n < \epsilon/4$. Then by argument in previous paragraph we can find $q, r$ with $q \in A, r \in B$ with $r - q = 1/n < \epsilon/4$. Also both $q, r$ can be chosen to be less than $2$ so $r + q < 4$ and hence $r^{2} - q^{2} = (r - q)(r + q) < \epsilon$. And this means that $$(r^{2} - 2) + (2 - q^{2}) < \epsilon$$ Since $q\in A, r \in B$ each expression in parentheses in above equation is positive and their sum is less than $\epsilon$ so that each expression itself is less than $\epsilon$. Therefore we have $$r^{2} - 2 < \epsilon, 2 - q^{2} < \epsilon$$ By definition of $\epsilon$ it now follows that $$2 - q^{2} < 2 - p^{2}$$ or $q > p$ and thus we have found $q > p, q \in A$.

Note that the most of the deep significant theorems in real-analysis are existential in nature where it is of utmost importance to focus on the existence of a quantity with certain specific desired properties rather than explicitly finding such a quantity and the above proof is a typical example of proofs seen in real-analysis where it shows the existence of an element $q \in A, q > p$ given an element $p \in A$ without explicitly giving a formula for $q$ in terms of $p$.

Rudin on the other hand uses some sort of numerical technique to have explicit formula for $q$ in terms of $p$. Hardy also gives this approach by asking his readers to prove the following simple theorem:

If $x$ is a positive approximation to $\sqrt{2}$ then $(x + 2)/(x + 1)$ is a better approximation to $\sqrt{2}$ but in a different direction so that if $x < \sqrt{2}$ then $(x + 2)/(x + 1) > \sqrt{2}$.

Applying this rule twice we get $$x \to \frac{x + 2}{x + 1}\to\dfrac{\dfrac{x + 2}{x + 1} + 2}{\dfrac{x + 2}{x + 1} + 1} = \frac{3x + 4}{2x + 3}$$ so we can choose $q = (3p + 4)/(2p + 3)$ also.

• While I agree with you that Rudin's approach here is strange, we shouldn't forget that he certainly knows the way things are done in real analysis. Rudin was an top-rate mathematician.
– zhw.
Jan 3 '17 at 22:25
• @zhw.: Rudin was a great fellow and the same is true of G. H. Hardy, but personally I feel that Rudin's book is so typical of American books with a highly formal and boring style. It is specifically designed for teaching undergraduates. But Hardy's book on the other hand is a classic and it is not exactly for teaching students at all. It is meant for self study and targeted at very young students who are totally new to calculus. But this is all a personal opinion and I respect your opinion very much. Jan 4 '17 at 4:19
• You make some good points. I too think there are problems w. Rudin's books. See math.stackexchange.com/questions/2077932/…
– zhw.
Jan 4 '17 at 6:58

I'd do it by trying to get $(p+1/n)^2 < 2$ for some $n\in \mathbb N.$ Note that for any $n\in \mathbb N,$

$$(p+1/n)^2 = p^2 +2p/n + 1/n^2 < p^2 +4/n + 1/n = p^2 + 5/n,$$

where we've used $p<2$ and $1/n^2 \le 1/n.$ So we'll be done if we can make $p^2 + 5/n < 2.$ Can we? Sure, it's the same as saying $n > 5/(2-p^2).$

• Simple and nice. +1 I think OP is trying to solve $p^{2}+2px+x^{2}<2$ like a quadratic in-equation. This is a typical algebraic approach which does not give any dividends in analysis. The right way is to replace $x^{2}$ by $x$ and then we simply get $x < (2 - p^{2})/(2p +1)$. You make it even simpler replacing $2p+1$ by $5$. Jan 4 '17 at 4:39

There is also this approach: it is not difficult to figure out, through the binomial theorem, that both

$$P_n=(1+\sqrt{2})^n+(1-\sqrt{2})^n\qquad\text{and}\qquad Q_n = \frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{\sqrt{2}}$$ are integers, and $$\lim_{n\to +\infty}\frac{P_n}{Q_n}=\sqrt{2}\lim_{n\to +\infty}\frac{(1+\sqrt{2})^n+(1-\sqrt{2})^n}{(1+\sqrt{2})^n-(1-\sqrt{2})^n}=\sqrt{2}\lim_{n\to +\infty}\frac{1+\frac{1}{(3+2\sqrt{2})^n}}{1-\frac{1}{(3+2\sqrt{2})^n}}=\sqrt{2}.$$ Both $$P_n$$ and $$Q_n$$ fulfill the recurrence relation $$\ell_{n+2}=2\ell_{n+1}+\ell_n$$, so $$\frac{P_n}{Q_n}$$ is exactly the $$n$$-th convergent of the continued fraction of $$\sqrt{2}=[1;2,2,2,2,\ldots]$$.

Rudin's choice was quite natural:

From B, let $$q=p-a>\sqrt{2}$$, with $$a,p,q\in\mathbb{Q^+}$$.

It follows that $$a, a rational number. Thus $$a=\frac{p^2-2}{b},$$ with $$b\in\mathbb{Q^+}$$. Notice $$\frac{p^2-2}{p+\sqrt{2}}=p-\sqrt{2}>a,$$ meaning $$b>p+\sqrt{2}$$ so $$p+2$$ will suffice. Having found a nice $$a$$ we can write $$q=p-\frac{p^2-2}{p+2}.$$

The same may be derived from A.

• Please, avoid making several edits. May 6 '20 at 10:58

This is a duplicate question. See 1. I answer it there, but I will repeat partially.

No. This isn't random. It is simple analytic geometry. One is trying to find the root of the equation $f(x)=x^2-2$. One starts with a rational $p$. Now, take the point $(2,2)$ on the graph. Form the chord between $(p,f(p))$ and $(2,2)$, solve for the intersection of the chord with the $x$-axis and that is Rudin's rabbit out of the hat formula. Picture is here: https://ggbm.at/nkfcPUB4