Generalized Fibonacci Sequence Question

The Fibonacci Sequence is defined as the recurrence $a(n)=a_{n-1}+a_{n-2}$ where $a(0)=0$ and $a(1)=1$. Today, I was bored so I considered the sequence $a(n)=\sqrt{a_{n-1}}+\sqrt{a_{n-2}}$. Ten minutes and a C program later, I discovered something: $$\lim_{n \to \infty}{a_n}=4$$ In addition, it doesn't matter what $a(0)$ and $a(1)$ are! It always converges. (Conjecture)

More experimenting lead to a more generalized result:

Consider $a(n)=a_{n-1}^{\frac{1}{k}}+a_{n-2}^{\frac{1}{k}}$ where $a(0)$ and $a(1)$ are any two positive real numbers and k is a positive integer greater than 1. This implies $$\lim_{n \to \infty}{a_n}=2^{\frac{k}{k-1}}$$ I thought that this result was pretty funny so I came here. Can someone shine some light on this discovery and prove this conjecture right? (I'm pretty sure it's not wrong)

Solution 1:

It'll make things easier for me to write $a_{n+2} = a_{n+1}^p + a_n^p$ ($0 < p < 1$), so that the expected limit satisfies $L = 2L^p$, hence $L = 2^{ \frac{1}{1-p} }$. Let $b_n = 2^{ - \frac{1}{1-p} } a_n$; then $$b_{n+2} = \frac{b_n^p + b_{n+1}^p}{2}$$

and we want to show that $b_n \to 1$ if $b_0, b_1$ are positive. The above implies $$\text{min}(b_n^p, b_{n+1}^p) \le b_{n+2} \le \text{max}(b_n^p, b_{n+1}^p)$$

and by induction we find that $$\text{min}_{0 \le i \le 1, \le \lfloor \frac{n}{2} \rfloor \le j \le n}(b_i^{p^j}) \le b_{n+1} \le \text{max}_{0 \le i \le 1, \lfloor \frac{n}{2} \rfloor \le j \le n}(b_i^{p^j})).$$

(The indices may be slightly off.) The conclusion follows from the simple fact that if $x > 0$ then $x^{p^n} \to 1$.

Solution 2:

As Qiaochu said, the statement $\lim\limits_{n \to \infty}{a_n}=2^{\frac{k}{k-1}}$ requires further justification. However, it can be proven as follows:

Intuitive Explanation: We will show that there are three possible behaviors for the sequence $a_n,n\in\mathbb{N}$. First, eventually all terms will be less than $2^{\frac{k}{k-1}}$ and the sequence will be increasing. Second, eventually all terms will be greater than $2^{\frac{k}{k-1}}$ and the sequence will be increasing. Either of these means the limit exists, and using lemmas 1 and 3 we see that it cannot be $0$ so must be $2^{\frac{k}{k-1}}$. Third, it will alternate between being above $2^{\frac{k}{k-1}}$ one term and below $2^{\frac{k}{k-1}}$ the next, getting arbitrarily close to $2^{\frac{k}{k-1}}$.

Lemma 1: For some $n\in\mathbb{N}$, $a_n \geq 1$.

Proof: Suppose that this is not the case, so we have some least upper bound $B<1$ for the sequence $a_n,n\in\mathbb{N}$. Let $a_n$ be such that $a_n>B/2$. Clearly each term is positive and less than $1$ meaning $a_i^{1/k}>a_i$, so $a_{n+1}=a_n^{1/k}+a_{n-1}^{1/k}>a_n^{1/k}>a_n>B/2$ and thus $a_{n+2}=a_{n+1}^{1/k}+a_{n}^{1/k}>a_{n+1}+a_n>B/2+B/2=B$, contradicting $B$ being an upper bound.

Lemma 2: If $a_n > 2^{\frac{k}{k-1}}$, then $a_{n+1}< \max\{a_n,a_{n-1}\}$.

Proof: Note $x>2^{\frac{k}{k-1}}\implies x^{1/k}<\frac{x}{2}$, so if $a_n > 2^{\frac{k}{k-1}}$, $a_{n+1}< 2\max\{a_n,a_{n-1}\}^{1/k}<\max\{a_n,a_{n-1}\}$.

Lemma 3: If $a_0=a_1=1$, the sequence $a_n,n\in\mathbb{N}$ is increasing and has limit $2^{\frac{k}{k-1}}$.

Proof: We shall induct on $n$ from $2^{\frac{k}{k-1}}\geq a_2 = 2\geq a_1\geq a_0$. If $2^{\frac{k}{k-1}}\geq a_n\geq a_{n-1}\geq a_{n-2}$ then $a_{n+1}\geq 2a_n^{1/k}\geq 2\frac{a_n}{2}=a_n$, while $a_{n+1}\leq (2^{\frac{k}{k-1}})^{1/k}+(2^{\frac{k}{k-1}})^{1/k}=(2^{\frac{k}{k-1}})^{1/k}$, thus the sequence is increasing and bounded above, so must have a limit. This limit is either $0$ or $2^{\frac{k}{k-1}}$, and since $a_n\geq 1,\forall n\in \mathbb{N}$ it must be $2^{\frac{k}{k-1}}$

Proof of Theorem: By lemma 1, we have some $a_n>1$. We must also have $a_{n+1}>1$, so applying lemma 3 in light of the fact that $a_{n-1}^{1/k}+a_{n-2}^{1/k}$ is increasing in both $a_{n-1},a_{n-2}$ gives us that the limit inferior $I$ is at least $2^\frac{k}{k-1}$. Suppose we have some $a_{i-1},a_i>2^\frac{k}{k-1}$, so by lemma 2 $a_{i+1}< \max\{a_i,a_{i-1}\}$, but at the same time $a_{i+1}>(2^\frac{k}{k-1})^{1/k}+(2^\frac{k}{k-1})^{1/k}=2^\frac{k}{k-1}$ thus by induction the sequence $a_n,n\in\mathbb{N}$ is eventually decreasing and bounded below by $2^\frac{k}{k-1}$. Then it has a limit, and this limit must be $2^\frac{k}{k-1}$. If no such $a_{i-1},a_i$ exist, then we either have some $a_{i-1},a_i<2^\frac{k}{k-1}$ or all $a_{i-1},a_i$ are on different sides of $2^\frac{k}{k-1}$. In the first case, an argument analogous to the proof of lemma 3 shows that the sequence is has limit $2^\frac{k}{k-1}$. In the second, we can let $a_i>2^\frac{k}{k-1}$, so every term in the sequence $a_i,a_{i+2},\ldots$ is greater than $2^\frac{k}{k-1}$ while every term in $a_{i+1},a_{i+3},\ldots$ is less than $2^\frac{k}{k-1}$. By lemma 2 the first sequence is decreasing, so the limit superior $S$ of $a_n,n\in\mathbb{N}$ exists. It cannot be strictly greater than $2^\frac{k}{k-1}$, as if $S=2^\frac{k}{k-1}+\epsilon/2$ for $\epsilon>0$ we have some $a_{i+2j}<2^\frac{k}{k-1}+\epsilon$ so $a_{i+2j+2}=a_{i+2j}^{1/k}+a_{i+2j+1}^{1/k}<2^\frac{k}{k-1}/2+\epsilon/2+2^\frac{k}{k-1}/2 = S$, which contradicts the fact that the sequence $a_i,a_{i+2},\ldots$ is decreasing. Hence $I \geq 2^\frac{k}{k-1}\geq S$, so $I = S = 2^\frac{k}{k-1}$ thus $\lim\limits_{n \to \infty}{a_n}=2^{\frac{k}{k-1}}$.