Newton's method can rapidly sum the geometric series

21 Mar 2026

Newton’s iteration for computing the reciprocal of a,

y_{n+1} = y_n(2-ay_n),

can be derived by applying Newton’s method to the function f(x)=1/x-a.

Substituting a=1-x gives

y_{n+1} = y_n(2-(1-x)y_n),

an iteration for computing 1/(1-x). Starting from y_0=1, the first few iterates are

\begin{aligned} y_1 &= 1 \cdot (1+x) = 1+x, \\ y_2 &= (1+x)(1+x^2) = 1+x+x^2+x^3, \\ y_3 &= (1+x+x^2+x^3)(1+x^4) = 1+x+x^2+\cdots+x^7. \end{aligned}

This certainly looks like the geometric series, and after n iterations the result is a polynomial of degree 2^n-1.

To verify, substitute

y_n = \sum_{k=0}^{2^n-1} x^k.

into the Newton iteration. The second factor telescopes to 1+x^{2^n}. This is an instruction to take the first factor and add a copy of it multiplied by x^{2^n}. The result is

y_{n+1} = \sum_{k=0}^{2^{n+1}-1} x^k,

as required.

The sum of a finite geometric series can of course be computed by the formula,

\sum_{k=0}^{n} x^k = \frac{1-x^{n+1}}{1-x},

but this involves division. Newton’s iteration uses only addition and multiplication. It just uses them much more economically than the direct series definition, producing a polynomial of degree 2^n-1 with only 2n multiplications and n additions.

When we discuss factoring a polynomial, we mean factoring it into a product of linear polynomials.

Newton’s iteration instead factors the finite geometric series into a composition of quadratic polynomials^⊕Horner’s method factors a polynomial into a composition of linear polynomials. This is handy for evaluation, but kind of a trivial re-arrangement since it has exactly the same coefficients as standard form..

What other polynomials can be factored this way? Counting free parameters suggests certainly not all of them. Beyond that, I don’t really know, but I think arithmetic circuit complexity considers questions like this.

Shape Operator

Newton's method can rapidly sum the geometric series