How to determine divergent series from inductive defintion

Question

Consider the following definition by induction:

$$ \begin{align} f(0)&=1\\ f(1)&=1/2\\ f(n)&=\frac{f(n-2)}{f(n-1)+f(n-2)} \end{align}$$

I can see that this defines a series that oscillates between 0.4 and 0.6 (which is good, because these are supposed to be probabilities). How do I determine this analytically? In other words, how do I show (a) that this is a divergent series, and (b) that it diverges on those values?

Answer 1

Basically not an answer, but this might help? (Too long for a comment.)

If $f(n-1)>f(n-2)$ , then: $$f(n)=\frac{f(n-2)}{f(n-1)+f(n-2)}<\frac{f(n-2)}{f(n-2)+f(n-2)}=\frac{1}2$$

If $f(n-1)<f(n-2)$ , then: $$f(n)=\frac{f(n-2)}{f(n-1)+f(n-2)}>\frac{f(n-2)}{f(n-2)+f(n-2)}=\frac{1}2$$

We have $f(0)=1>f(1)=\frac{1}2$ , so $f(2)>\frac{1}{2}$ .

And $f(2)>\frac{1}2=f(1)$ , so $f(3)<\frac{1}{2}$ .

And $f(3)<f(2)$ , so $f(4)>\frac{1}{2}$ .

From here we can see that the series is jumping around $\frac{1}2$. We do some calculation on the very first values and find that it's getting farther and farther away from $\frac{1}2$ , so it should be divergent?

We should wait for a proper proof.

Answer 2

The sequence $f(n)$ does indeed approach a limit cycle of length two, close to, but not exactly $0.4,\, 0.6$.

Let's look at things in a more general setting. Suppose we have $f(0), f(1) > 0$, and the recurrence $$f(n) = \frac{f(n-2)}{f(n-1) + f(n-2)}$$ for $n \geqslant 2$.

First we note that an obvious induction argument shows $f(n) > 0$ for all $n$, and $f(n) < 1$ for $n \geqslant 2$.

Next, for $n \geqslant 2$ we have $$f(n-1) + f(n) - 1 = f(n-1) - \frac{f(n-1)}{f(n-1) + f(n-2)} = f(n-1)\cdot \frac{f(n-1) + f(n-2) - 1}{f(n-1) + f(n-2)}\,.$$ Thus the sign of $f(n-1) + f(n) - 1$ never changes, in other words

1. If $f(0) + f(1) > 1$, then $f(n) + f(n+1) > 1$ for all $n$.
2. If $f(0) + f(1) = 1$, then $f(n) + f(n+1) = 1$ for all $n$.
3. If $f(0) + f(1) < 1$, then $f(n) + f(n+1) < 1$ for all $n$.

Hence in case 1 we have $f(n+2) < f(n)$ for all $n$, in case 2 we have $f(n+2) = f(n)$ for all $n$, and in case 3 we have $f(n+2) > f(n)$ for all $n$.

In all cases the two sequences $\bigl(f(2n)\bigr)_{n \in \mathbb{N}}$ and $\bigl(f(2n+1)\bigr)_{n \in \mathbb{N}}$ are monotonic and bounded, and therefore convergent. Let $\alpha = \lim_{n \to \infty} f(2n)$ and $\beta = \lim_{n \to \infty} f(2n+1)$.

We always have $0 < \alpha, \beta$. In cases 2 and 3 that is obvious since the sequences are nondecreasing, in case 3 it follows from $$0 < 1 - f(2) \leqslant 1 - f(2n) < f(2n+1) < f(2n-1)$$ and $$0 < 1 - f(3) \leqslant 1 - f(2n+1) < f(2n+2) < f(2n)$$ for all $n \geqslant 1$.

Now we can in all cases note $$\alpha + \beta = \lim_{n \to \infty} f(n-1) + f(n-2) = \lim_{n \to \infty} \frac{f(n-2)}{f(n)} = 1\,,$$ which shows that $\bigl(f(n)\bigr)$ approaches the limit cycle $\alpha,\beta$. (For $\alpha = \beta = \frac{1}{2}$ this isn't a proper cycle.)

In the example $f(0) = 1$ and $f(1) = \frac{1}{2}$ of the question, we are in case 1 and immediately see $\beta < f(3) < f(1) = \frac{1}{2}$, so $\beta < \alpha$. Also we compute $$f(6) = \frac{2338}{3925} < \frac{3}{5}$$ and see that consequently $0.4 < \beta < \alpha < 0.6$. But as a first approximation the values $0.4$ and $0.6$ are pretty good, with $$f(6) \approx 0.59566879 \qquad\text{and}\qquad f(7) = \frac{270825}{661271} \approx 0.40955221$$ we obtain $$0.404332121 < \beta < 0.409552211 \qquad\text{and}\qquad 0.59044778 < \alpha < 0.59566879\,.$$ Further iteration easily yields tighter bounds, but determining the exact limits looks like a difficult problem.