How to determine divergent series from inductive defintion 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?
 A: 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.
A: 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

*

*If $f(0) + f(1) > 1$, then $f(n) + f(n+1) > 1$ for all $n$.

*If $f(0) + f(1) = 1$, then $f(n) + f(n+1) = 1$ for all $n$.

*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.
