How to solve $S = x + xn + xn^2 + \cdots + xn^{y-1}$ for $n$

Question

I need to come up with a formula to calculate the coefficient from this formula

$$S = x + xn + xn^2 + \cdots + xn^{y-1} \tag{1}$$

Variables:

• $S$ - total prize pool
• $x$ - amount the last place receives
• $y$ - number of players
• $n$ - coefficient

How do I solve for $n$?

Thank you

Answer 1

The practical way to do it, assuming $ S > xy$. You take the following function $$ f(n) = \left(1+\frac Sx n-\frac Sx \right)^{1/y} $$

and then apply it to itself, until result no longer changes, starting with $n_0=1+1/y$: $n_1=f(n_0)$, $n_2=f(n_1)$ and so on.

For example, for $y=9$, $S/x=15$, we have the following $$n=1.111, 1.115, 1.118, 1.120, 1.121, 1.122, 1.122\dots$$

Answer 2

The equation can be written

$$\frac{n^y-1}{n-1}=\frac Sx$$ or in the polynomial form

$$n^y-\frac Sxn+\frac Sx-1=0.$$

Such an equation doesn't have a closed-form solution, except for a few small values of the degree $y$.

A numerical solution by Newton's method works well.

Answer 3

As Yves Daoust wrote, you are looking for the zero of function $$f(n)=n^y-\frac{ S}{x}(n-1)-1$$ Consider its derivatives $$f'(n)=y\, n^{y-1}-\frac{S}{x}$$ $$f''(n)=y\,(y-1) \, n^{y-2}$$ For $y>1$, the second derivative is always positive.

The first derivative cancels at $$n_*=\left(\frac{S}{x y}\right)^{\frac{1}{y-1}}$$ So, if $f(n_*)<0$ (remember that $n=1$ is a trivial solution to be discarded), to get a starting point for Newton method, expand $f(n)$ as a Taylor series to second order around $n=n_*$ to get $$f(n)=f(n_*)+\frac 12 f''(n_*) (n-n*)^2+O\left((n-n_*)^3\right)$$ and, ignoring the high order tems $$n_0=n_*+\sqrt{-2\frac{f(n_*) }{f''(n_*) }}$$

Now, iterate using $$n_{k+1}=n_k-\frac{ f(n_k)} { f'(n_k)}$$

For the values used by Vasily Mitch $(y=9,S=15x)$, $n_*=1.06594$ , $n_0=1.12738$ anf the iterates would be $$\left( \begin{array}{cc} k & n_k \\ 0 & 1.127375420 \\ 1 & 1.123698919 \\ 2 & 1.123557057 \\ 3 & 1.123556849 \end{array} \right)$$

Let us do the same with huge numbers : $y=123$, $S=123456789\,x$. This will give $n_*=1.11994$ and $n_0=1.16505$. Newton iterates would be $$\left( \begin{array}{cc} k & n_k \\ 0 & 1.165045878 \\ 1 & 1.156842265 \\ 2 & 1.150315554 \\ 3 & 1.146560370 \\ 4 & 1.145520226 \\ 5 & 1.145454006 \\ 6 & 1.145453756 \end{array} \right)$$