Period of a sequence defined by its preceding term

Question

A sequence $x_n$ is defined such that $$x_{n+1}= \frac{\sqrt3 x_n -1}{x_n + \sqrt3}, n\ge1, x_0\neq-\sqrt3 $$

We now have to find the period of this sequence.

By substituting values for $x_0$ I found out the period to be $6$. Also I proved this by finding all $x_{n+k}, 1\le k \le 6$ in terms of $x_n$ thereby showing $x_{n+6}= x_n$. But this takes up a fair amount of time.

Is there any other method to find out the period of this sequence?

Answer 1

This is really nice. I like the answer above and I also follow up the suggestion of lab bhattacharjee.

Assume $x_n = \tan y_n$ and $y_0 \ne \pi / 3$.

$$ \tan y_{n+1} = \frac{\tan y_n \sqrt{3} - 1 }{ \tan y_n + \sqrt{3}} = \frac{-1}{\tan (y_n + \pi / 3)} $$

From this it seems to be possible to derive

$$ \tan y_{n+2} = \tan (y_n + 2\pi/3) $$

And this leads directly to the period of 6.

I'd be interested if anyone has any insights on a link between this approach and the approach of Mark.

Answer 2

Consider the function $f(x) = \frac{\sqrt{3} x - 1}{x + \sqrt3}$

We are looking for the $n$ such that $f^{(n)}(x) = x$.

Fixed points of $f$ are $i$ and $-i$ in the complex plane. We can hope that perturbation about $i$ is can be approximately modeled as $f(\epsilon + i) - i \approx c \epsilon $ for some complex $c$. Further applications of $f$ can again be approximated using the model, reasoning (heuristically) that applications of $f$ near the fixed point will still leave us close enough to the fixed point that the model is still a reasonable approximation. In that case we can look for $n$ such that $f^{n}(\epsilon + i) = \epsilon + i$ which translates to $c^n \epsilon \approx \epsilon$.

Of course, for $c$ we choose the derivative of $f$ at $i$. This is $\frac{4}{(\sqrt{3} + i)^2}$. Now take powers of $c$ until you get $1$.

It turns out $c^6 = 1$ exactly.

Edit: I now elaborate on the above heuristics

Suppose a function $g$ is analytic at $0$ and that $g(0) = 0$ and $g$ is invertible in a neighborhood of $0$. Call the derivative $g'(0) = c$. By chain rule one can show ${g^{(n)}}'(0) = g'(0)^n$.

Now suppose you have some function $f$ with fixed point $p = f(p)$.
Set $g(x) = f(p + x) - p$.

$g(g(x)) = f(p + g(x)) - p = f(p + f(p + x) - p) - p = f(f(p + x)) - p$.
$g^{n}(x) = f^{n}(p + x) - p$

Suppose $N$ is the number of compositions at which the system cycles, then $f^{(N)}(x) = x$ and ${f^{(N)}}'(x) = 1$ for all $x$.

It becomes a necessary condition that $c^N = g'(0)^N = {g^{N}}'(0) = (f^{N}(p + x) - p)' = 1$.

This gives us an algorithm to find candidates of the period of some system $f$.
1. Find some fixed point $p$ of the system.
2. Take the derivative $f$ at $p$, call it $c$.
3. If $|c| \ne 1$, the system does not cycle. Stop.
4. Compute $2\pi / \text{arg}{[c}]$. If this is a rational number, then the denominator must be a divisor of the period. Otherwise the system does not cycle.