0

Given a s and the amount of terms n, is it possible to find the common ratio of a finite geometric series?

$$\sum_{i=1}^n r^i = s$$

I've been able to solve the equation up to

$$\frac{r^{n+1} - r}{r-1} = s$$

but I have no idea how to reduce this further an a way a computer can understand. The closest answer(Geometric series : Find common ration 'r') I can find is to approximate the solution to $$r^n=s$$ But this number is way to inaccurate for my use case. Since wolfram alpha seems to be able to solve these types of problems, I am hoping there is some simple formula I can use to get the answer I need or at least a better approximation.

KReiser
  • 65,137
Benjamin Danger Johnson
  • 35
  • There isn't a unique solution. Consider $r + r^2 = 12$ (so $n = 2$ and $s = 12$). This has the solutions $r = 3$ and $r = -4$. – SCappella Dec 12 '19 at 08:03
  • One idea would be to use the $r^n = s$ approximation and then improve its accuracy using Newton's method or similar. – SCappella Dec 12 '19 at 08:06
  • That's fair, I figured there was no unique solution since I was working with polynomials. I'll take a look at Newton's method. – Benjamin Danger Johnson Dec 12 '19 at 08:25

1 Answers1

0

As you properly wrote it, you end with a polynomial of degree $n+1$ which cannot be solved analytically if $n >4$.

So, you need a numerical method (Newton being probably the simplest).

Consider that you are looking for the zero of function $$f(r)=r^{n+1}- (s+1)r+s$$ for which $$f'(r)=(n+1)r^n-(s+1)\qquad \text{and} \qquad f''(r)=n(n+1)r^{n-1}$$ The first derivative cancels at $$r_*=\left(\frac{s+1}{n+1}\right)^{\frac{1}{n}}$$ which corresponds to a minimum (by the second derivative test).

To get an estimate, use a Taylor expansion around this point and, solving, use $$r_0=r_*+\sqrt{-2\frac{f(r_*)}{f''(r_*)}}$$ and Newton iterates wil be $$r_{n+1}=r_n-\frac{f(r_n)}{f'(r_n)}$$

Let us try for $n=20$ and $s=123456789$. The iterates are $$\left( \begin{array}{cc} n & r_n \\ 0 & 2.66442 \\ 1 & 2.56586 \\ 2 & 2.50137 \\ 3 & 2.47667 \\ 4 & 2.47363 \\ 5 & 2.47359 \end{array} \right)$$

Comparing Newton, Halley and Householder iterates $$\left( \begin{array}{cccc} n & \text{Newton} & \text{Halley} & \text{Householder} \\ 0 & 2.6644202 & 2.6644202 & 2.6644202 \\ 1 & 2.5658566 & 2.5062787 & 2.4809286 \\ 2 & 2.5013675 & 2.4738521 & 2.4735928 \\ 3 & 2.4766670 & 2.4735928 & \\ 4 & 2.4736339 & & \\ 5 & 2.4735928 & & \end{array} \right)$$

Claude Leibovici
  • 260,315
  • Awesome, this seems to approximate the value very well for my purposes. Took a lot of work to figure out (I'm a bit of a math dummy) but this works well and performs quickly. – Benjamin Danger Johnson Dec 12 '19 at 10:12
  • @BenjaminDangerJohnson. We could do better for $r_0$ but I prefered to stay as simple as possible. We could also reduce the number of iterations using Halley or Householder methods instead of Newton. – Claude Leibovici Dec 12 '19 at 10:16