Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
2  
If a limit $L \ge 0$ exists it satisfies $L = L^{1/k} + L^{1/k}$, so either $L = 0$ or $L = 2^{ \frac{k}{k-1} }$. I think it should not be hard to show that the sequence is bounded away from $0$ if it is ever positive, so it remains to show that the limit exists and this should be a relatively straightforward if tedious argument. –  Qiaochu Yuan Dec 28 '11 at 2:09
6  
Of course, what is straightforward if tedious for Qiaochu could be devious and nerve-wracking for others. –  Gerry Myerson Dec 28 '11 at 2:26
    
Indeed. It sounds easy enough to argue that the sequence is bounded, but rather non-straightforward to show that it necessarily converges towards a limit. A priori one could think it might also end up converging towards a cycle, or even in chaotic behavior. –  Henning Makholm Dec 28 '11 at 2:58
2  
This is being offered on the margin to this question. –  Alex B. Dec 28 '11 at 3:50
1  
Cool question, I must say! –  Nikhil Bellarykar Dec 28 '11 at 5:58

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
    
Ah so assuming they get closer and closer as you go to infinity they would be equal so adding them would be same as multiplying by two ($L=2L^p$). The third step was a little difficult to follow, but now I understand. Best answer so far! :) –  itdoesntwork Dec 28 '11 at 14:45

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}}$.

share|improve this answer
    
Great answer, but a little to complicated for my simple mind :) –  itdoesntwork Dec 28 '11 at 14:45
    
I'll edit to add an intuitive explanation. –  Alex Becker Dec 28 '11 at 19:36
    
@itdoesntwork Does that help? –  Alex Becker Dec 28 '11 at 19:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.