Proving the real numbers are complete

If $p\in\mathbb{Q}$ is smaller than $\sqrt{2}$, we want to find another rational $p<q<\sqrt{2}$. Now, this can easily be handled with decimal fractions, but if you want something neater that relies solely on $p$, then what we basically want to do is find a rational $r\in\mathbb{Q}\cap(0,\sqrt{2}-p)$ and define $q=p+r$.

Note that $\sqrt{2}-p\not\in\mathbb{Q}$, but $2-p^2 = (\sqrt{2}-p)(\sqrt{2}+p)\in\mathbb{Q}$. If we want it to be small enough, it suffices that $\frac{\sqrt{2}+p}{2+p} < 1$, so that $$\frac{2-p^2}{2+p} = (\sqrt{2}-p)\frac{\sqrt{2}+p}{2+p}<\sqrt{2}-p.$$

The formula is unimportant. Teaching how to come up with nice formulas like that is beyond the scope of the book: it is more in the domain of numerical methods or possibly number theory. (although maybe Newton's method is talked about in the book; it's sort of lucky that that works out nicely here)

Focusing on how to come up with the formula is a red herring -- while it may be interesting as an independent study, it is really irrelevant to what you're trying to learn from his book: all that matters is that it can be done. If you didn't have that nice formula, you would simply do something tedious and straightforward; e.g. something with decimal approximations.

Doing the tedious and straightforward thing, however, would distract from the idea he's trying to teach you. Not only would you get bogged down in details, but suddenly you're trying to learn two things rather than just one.

Thus, Rudin pulled something nice out of a hat -- a simple way to blitz through the technical details of an otherwise simple idea that he wants to convey about the very basics of the field of real numbers so that he can get on with teaching you analysis.

Formally? The formula for $q$ doesn't come from anywhere; it's just pulled out of a hat. He uses it to define $q$. Since what you're seeking to prove is just that a $q$ with such-and-such properties exists, you're allowed to produce such a $q$ in whichever crazy way you want to, as long as you're able to prove afterwards that it has such-and-such properties.