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

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.

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<q$, and for every $p$ in $B$ we can find a rational $q$ in $B$ such that $q<p$.

$\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<q<p,$ 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<q \Leftrightarrow y > 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.

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.