Question Corner and Discussion Area

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.Closed-form solutions are more of a rarity than one might think, and not as important as one might think. The equation you are trying to solve can be written asConsider 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:

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?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.Thank you and best wishes, Ned Piburn

R^N + R^(N-1) + ... + R + 1 - q = 0 (*)where q = S/A1. This equation does not have a general closed-form solution for R in terms of familiar functions (like addition, multiplication, taking powers, and extracting roots) of N and q, unless N < 5.

(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.

This part of the site maintained by (No Current Maintainers)

Last updated: April 19, 1999

Original Web Site Creator / Mathematical Content Developer: Philip Spencer

Current Network Coordinator and Contact Person: Joel Chan - mathnet@math.toronto.edu

Navigation Panel:

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 graphical version (better pictures & formulas)

Access printed version in PostScript format (requires PostScript printer)

Go to University of Toronto Mathematics Network Home Page