What is this recursive function approximating? ($x_i = x_{i-1}^2 / x_{i-2}$)

Question

I came across this recursive function in some code, and it is within a function called "interpolate". Essentially the rule is:

$x_i = x_{i-1}^2 / x_{i-2}$

which can also be defined as:

$x_i = \sqrt{x_{i-1} * x_{i+1}}$

with $x_0$ initialized to 1, and the last element of $x$ initialized to a value which specifies the max value of the function.

Can anyone tell me what this function is supposed to be approximating? There are no comments in the code indicating what this is.

Answer 1

Given: A sequence $x_0,\,x_1,\,x_2,\,\cdots\,x_p$ with $x_0=1$ and $x_p=x$ where $x$ is a known value and $p$ is a known integer, and for $i\ge2$

$$ x_i = x_{i-1}^2 / x_{i-2} $$

This condition implies that $x_i$ and $x_{i-2}$ have the same sign, and it can be re-written

$$ x_{i-1}=\sqrt{x_ix_{i-2}} $$

so that $x_{i-1}$ is the geometric mean of $x_i$ and $x_{i-2}$. This, in turn, implies that $\left\lbrace x_i\right\rbrace$ is a geometric sequence with

$$ x_i=r^i$$

for some $r$.

But we know that

$$ r^p=x $$

Thus

$$r=x^{1/p}$$

So the equation for the sequence is

$$ x_i=x^{i/p} $$

Answer 2

Once $x[0], x[n]$ are specified, this function makes the array display a geometric sequence with those first and last terms.

For example, with $x[n=6]=729,$ the array becomes $[1,3,9,27,81,243,729].$

Can you see from the definition why this is the case?

Answer 3

You have $$x_{n}=\frac{x_{n-1}^2}{x_{n-2}}$$ Take logarithms $$\log(x_{n})=2\log(x_{n-1})-\log(x_{n-2})$$ Define $y_n=\log(x_{n})$ to make $$y_n=2y_{n-1}-y_{n-2}\implies y_n=c_1+c_2 n\implies x_n=c_1 e^{c_2 n}$$ Now, let $x_0=a$ and $x_p=b$; this gives $$c_1=a\qquad \text{and} \qquad b=a e^{c_2 p}\implies c_2=\frac 1 p \log \left(\frac{b}{a}\right)$$