I have been trying to solve for $\sqrt x$ using a quotient of polynomial functions. As you know, $\sqrt x \approx \frac{q+x}{2\sqrt q}$ where q = $\lfloor \sqrt x \rfloor ^ 2$. By iteratively applying$f(k) = \frac {x+f(k-1)^2}{2f(k-1)}$, $f(k) \approx \sqrt x$ and $f(0)=\sqrt q$, you can achieve the following formulas: $$\sqrt x \approx \sqrt q$$ $$\sqrt x \approx \frac {q+x}{2\sqrt q}$$ $$\sqrt x \approx \frac {q^2+6qx+x^2}{4\sqrt q(q+x)}$$ $$\sqrt x \approx \frac {q^4+28q^3x+70q^2x^2+28qx^3+x^4}{8\sqrt q(q+x)(q^2+6qx+x^2)}$$ $$.$$ $$.$$ $$.$$ My question is, how can you find the polynomial $t(k)$, where $f(k)=\frac{t(k)}{b(k)}$, i.e. $t(k)$ is the polynomial that is the numerator. I have already found that, $$b(k)=2 ^ {k} \prod_{n=1}^{k-1} t(n)$$ $$t(k)=b(k-1)^2x+t(k-1)^2$$ What I cannot figure out is how to write $t(k)$ as, $$\sum_{n=0}^{2^{k-1}}a_nq^{2^{k-1}-n}x^{n}$$ It is obvious that the first coeffecient of $t(k)$, let it be called $C_1 (n) = 1$ . Finding further functions of the form $C_k (n)$ becomes far more difficult for larger $k$ values. Finding $C_k (n)$ would take a very long time to solve for manually, so is there an easier way of finding it? Here is what I got for $C_2 (n)$ , $$t(k)=b(k-1)^2x + t(k-1)^2$$ Both $t(k-1)$ and $b(k-1)$ are polynomials, therefore when you square them the second term should have a term that looks like, $C_2 (k)q^{2^{k-1}-1}x$. For $t(k-1)^2 $, this term will turn out to be $2C_2(k-1)q^{2^{k-1}-1}x $, and $2^{2(k-1)}q^{2^{k-1}-1}x $, for $b(k-1)^2x $, $$b(k-1)^2x=x(2^{k-1}\sqrt q(q+x)(q^2+6qx+x^2)...(q^{2^{k-2}}+...))^2$$ There turns out to only be one way of multiplying terms to get something in the form $aq^{2^{k-1}-1}x $ and that is by multplying the first terms of each polynomial since, $$\sum_{n=0}^{k} 2^n = 2^{k+1}-1$$ When multiplying out the first terms of every polynomial in $xb(k-1)^2$ you arrive at the answer, $2^{2(k-1)}q^{2^{k-1}-1}x$ . This means that $C_2 (k) = 2C_2 (k-1) + 2^{2(k-1)}$, from this it is easy to show that, $$C_2 (k) = \frac{2^k(2^k-1)}{2}$$ Start by replacing $C_2(k-1) $ by its expanded form, and repeat this process until you reach $C_2(1)$ which is equal to 1. This expansion gives the following, $$C_2(k)=\sum_{n=0}^{k-1} 2^{k-n-1} (2^{2n})=2^{k-1}\sum_{n=0}^{k-1} 2^n=2^{k-1}(2^k-1)=\frac{2^k(2^k-1)}{2}$$ This is as far as I can get, I don't know how to solve for $C_3$ and above. It would be nice if anyone could give me an idea of what to do to get further than just $C_2$.
I have found a solution for $t(k)$ but I don't know how to derive it, I found it while looking at the relation this sequence has to binomial coefficients and found that, $$t(k)=\sum_{n=0}^{2^{k-1}} \binom{2^k}{2n} q^{2^{k-1}-n}x^n$$
P.S. It would be nice if you could tell me the name of the subject of maths that you used so that I can actually understand. Thanks!
I can prove that the quotient of polynomials you have found does indeed converge to $\sqrt{x}$ (although I don't know if this is the derivation you seek). I'm going to use different notation, and I will set $q=1$ for now; it should be fairly straightforward to construct the same argument with arbitrary postive $q$. Let $$P_m (x) = \sum_{n=0}^{2^m} {{2^{m+1}}\choose{2n}}x^n$$ Recognizing that this is simply the sum of the even terms in the binomial expanision of $(1+\sqrt{x})^{2^{m+1}}$, we may use a roots of unity filter to obtain the closed form $$P_m(x)= \frac{(1+\sqrt{x})^{2^{m+1}}+(1-\sqrt{x})^{2^{m+1}}}{2}$$ From there we may evaluate $$\prod_{k=0}^{m-1} P_k(x)= \prod_{k=0}^{m-1} \frac{(1+\sqrt{x})^{2^{k+1}}+(1-\sqrt{x})^{2^{k+1}}}{2} = 2^{-m}\sum_{i=0}^{2^m-1} (1+\sqrt{x})^{2i}(1-\sqrt{x})^{2^{m+1}-2-2i} = 2^{-m} \frac{(1+\sqrt{x})^{2^{m+1}}-(1-\sqrt{x})^{2^{m+1}}}{(1+\sqrt{x})^2-(1-\sqrt{x})^2} = 2^{-(m+1)} \frac{(1+\sqrt{x})^{2^{m+1}}-(1-\sqrt{x})^{2^{m+1}}}{\sqrt{x}}$$ I used the property of natural numbers having unique binary expansions in order to expand the product into the sum where every term with even power appears exactly once. Then the sum is a geometric series and I used the identity $\frac{b^{n+1}-a^{n+1}}{b-a}=b^n+b^{n-1}a+...+ba^{n-1}+a^n$ to evaluate it. An alternate derivation would have followed by multiplying the product by $\frac{(1+\sqrt{x})^2-(1-\sqrt{x})^2}{(1+\sqrt{x})^2-(1-\sqrt{x})^2}$ and repeatedly using the difference of squares identity. Now it follows that $$\lim_{m \to \infty} \frac{P_m(x)}{2^m \prod_{n=0}^{m-1}P_k(x)} = \sqrt{x}$$ since $(1+\sqrt{x})^{2^{m+1}}$ eventually dominates $(1-\sqrt{x})^{2^{m+1}}$.
This establishes that the desired approximation by the quotient of polynomials converges to $\sqrt{x}$.
From the closed forms that I've found, it can also be shown that the quotient of polynomial obeys the original recurrence.
Also in terms of subject matter, I really just used algebra (not abstract or modern algebra). However, these techniques (such as roots of unity filter) are sometimes used for combinatorics problems which can be solved using generating functions.