Question Corner and Discussion Area

Finding the Ratio from the Sum of a Geometric Series

Thank you for maintaining such an interesting and useful web page. The following problem comes from a real life application: defining a smooth calculational grid for a computational fluid dynamics program.

Consider the sum of N terms of a geometric series:

S = A1 + A1*R + A1*R^2 + ... + A1*R^(N-1)

We know that this is equivalent to:

S = A1 * (1 - R^N) / (1 - R)

We can rearrange this equation to solve for N to get:

N = LN((S*R + A1 - S) / A1) / LN(R).

The challenge is to solve for R. From the form of the first equation, we know that what we seek is one of the roots of a polynomial of degree N-1. If we view the equation in physical terms we should satisfy ourselves that 1) there is a unique real solution and 2) there are reasonable restrictions that we can apply that will eliminate the unsought complex roots.

The physical model that the algebra represents is: S is a distance to be spanned by N computational cells. The first cell has a width of A1 the second a with of A1*R and so on. What we seek is an expansion (or contraction) factor, R, that will cause the sum of N cell widths to be exactly S.

From this we can state the following inequalities:

S > 0 ;	there must be a distance to span.
A1 > 0 ;	the first cell must have width.
A1 < S ;	we won't span the distance with the
	first cell.
N > 1 ;	we have to have at least a second
	cell to cover the remaining distance.
R > 0 ;	follows from above.

From a purely intuitive view there ought to be a closed form generalized solution for R. But I have been unable to see my way to anything but an iterative numerical solution. Can you supply some insight?

Thank you and best wishes, Ned Piburn

R^N + R^(N-1) + ... + R + 1 - q = 0 (*)

(Incidentally, although the form S = A1 * (1 - R^N) / (1 - R) looks simpler, it's not any easier to solve for R; because although, when you rearrange it into a polynomial equation R^N - q R + q - 1 = 0, it looks nicer than (*), it is simply (R-1) times (*). So in finding its roots the first thing you'd do is discover and discard the root R=1; then you'd divide by (R-1) and be left with (*). So it's no easier to use this form; in fact, it's mathematically less convenient because you have the extra root R=1 to worry about).

Solutions by radicals of polynomials of degree <= 4 were known by the 1500's (the degree 2 case being the familiar quadratic formula). For a couple of hundred years mathematicians tried and failed to find such a formula for quintic (degree 5) equations; eventually it was discovered that no such general formula exists, because associated to each such polynomial is an abstract mathematical object called a Galois group, and only when the Galois group has certain nice properties does a solution by radicals exist. All Galois groups for polynomials of degree <= 4 have this property, but the Galois groups for most degree >= 5 polynomials do not. Some do, but equation (*) is not among them (except for very special values of q like 0 or 1).

There are general solutions of quintic equations involving other functions like hypergeometric functions, but from a practical point of view that doesn't matter too much since the only way to evaluate them is by numerical calculations anyway. And besides, that's only for N=5.

However, just because there isn't a "closed-form" solution doesn't mean R is not expressible as a function of N and q! In fact, your "physical arguments" can be translated into precise mathematics. The conditions you gave, namely that N > 1, R > 0, and S > A1 (so that q > 1), mean that R is uniquely defined as a function of N and q. The mathematical proof of that goes like this:

Let f(R) = R^N + · · · + R + (1-q). This f is a continuous function, with f(0) < 0 and f(q-1) > 0. (Reason: f(0) = 1 - q < 0 since q > 1, and f(q-1) = (q-1)^N + · · · + (q-1)^2 + (q-1) + (1-q) which, since (q-1)^N, . . . , (q-1)^2 are all positive, is greater than (q-1) + (1-q) = 0.)

Therefore, by the intermediate value theorem, f(R)=0 for some value of R in the range 0 < R < q-1.

Also, this R is unique: there can be no other R > 0 for whichs f(R) = 0, because f is an increasing function when R > 0 (its derivative is NR^(N-1) + ... + 2R + 1 which is positive).

Therefore, for each N>1 and q>1, there is a unique corresponding R>0 for which (*) holds. The equation does define R as a function of N and q. You could even go on to describe properties of that function; you can prove that it's continuous and differentiable, for example.

It just happens that this function isn't representable as a combination of the few functions we're familiar with, so to calculate its values we need numerical approximations. But that's not an unexpected thing; very few functions are. Even the trigonometric and exponential functions cannot be written as combinations of the simpler functions; that's why we give new names to them. The same thing is true of the function representing R in terms of N and q; if you wanted to use it a lot, you'd just give that function a name and a notation, the way one did with functions like "sin" and "log". To calculate its values you use some kind of numerical method; that's exactly what one does when one calculates sines or logarithms.

Go backward to A Geometric Series Arising From an Arithmetic Series
Go up to Question Corner Index
Go forward to Numbers Defined By Infinite Sums
Switch to text-only version (no graphics)
Access printed version in PostScript format (requires PostScript printer)
Go to University of Toronto Mathematics Network Home Page