How to find the value of the common ratio in geometric series without the method of substitution

Question

It has been sometime since I got myself to solve mathematical equations. So I can't seem to find a way to come to a simplified equation for finding the common ratio knowing the final sum and the value of n in the formula :

$$\text{finalSum} = r(1 - r^n)/(1 - r)$$

For example: 3, 9, 27, 81, 243

$$363 = r(1 - r^5)/(1 - r)$$

Given above is a very simple example. But I'll be dealing these in decimals. Is there any way of getting a simplified equation to get the value of r? Or is the method of substitution the only way?

PS: This is for a program I'm writing

Please let me know.

Thanks

Answer 1

This is binary search based solution for program.

As $r$ is always a positive integer. You can start with say $r=1$ and than calculate the sum using, $$ S = \frac{r(1 - r^n)}{(1 - r)} $$ Let the given sum is $A$. You can than check if $A \geq S$, if yes than double the $r$.

Say, currently $r = 2^k$ for which $A \geq S$ and at $r=2^{k+1}$, $A \leq S$.

Then you know answer lies between $2^k$ and $2^{k+1}$. You can apply binary search on these values to find $r$ for which $A=S$.

Sum at each iteration can be calculated in $O(log(n))$. So, final Time Complexity for this will be $O(log(r')*log(n))$ (where $r'$ is the answer).

Note: This will always give exact $r$.

Ref:

Binary Search

Calculate power in log(n) time

Answer 2

In general, you will need some numerical method and more than likely, Newton would be the simplest.

Consider that you look for the zero of function $$f(r)=\sum_{n=1}^p r^n - A$$

Assuming $r>1$, you immediately see that $$r^p < A \implies r < A^{\frac{1}{p}}$$ which could be a good starting point (for your case, $383^{\frac 15}=3.286$).

So, let $r_0=A^{\frac{1}{p}}$ and iterates according to $$r_{k+1}=r_k-\frac{f(r_k)}{f'(r_k)}=r_k-\frac{(r_k-1) r_k \left(r_k^p-1\right)}{(p (r_k-1)-1) r_k^p+1}$$

For illustration with a "serious" case, let $p=25$ and $A=10^{10}$. This will give us the following iterates

$$\left( \begin{array}{cc} k & r_k \\ 0 & 2.5118864 \\ 1 & 2.4707994 \\ 2 & 2.4605423 \\ 3 & 2.4600107 \\ 4 & 2.4600093 \end{array} \right)$$

Make it apparently more difficult with $p=123$ and $A=10^{345}$ for the following iterates $$\left( \begin{array}{cc} k & r_k \\ 0 & 638.08429 \\ 1 & 638.07615 \end{array} \right)$$