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 as
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: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.
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