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.

I have the recurrence relation, with two initial conditions

$$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$

With the help of Wolfram Alpha, I managed to get the result of $O(\Phi^n)$, where $\Phi = \frac{1+\sqrt 5}{2} \approx 1.618$ is the golden ratio.

Is this correct and how can that be mathematically proven?

share|improve this question
    
How did you get this with Wolfram Alpha without knowing explicitly your $O(1)$ term? –  1015 Feb 14 '13 at 14:33
    
I inserted $O(1)$ as a constant $m$, let him write out exact expression in tems of $n$ and $m$, then observed what happens when we send n or m to large numbers. –  Rok Kralj Feb 14 '13 at 14:35
    
Do you mean $O(1)=m=constant$? –  1015 Feb 14 '13 at 14:36
    
Yes, $O(1)$ means a costant factor (that is - not dependent on $n$). –  Rok Kralj Feb 14 '13 at 14:37
1  
No, the notation $O(1)$ means a bounded term: en.wikipedia.org/wiki/Big_O_notation It makes a big difference. If you meant constant, this is very easy, since it can be solved explicitly. But this holds generally when $O(1)$ depends on $n$ and is bounded by $\pm C$, since in this case you can prove by induction that $T(n)$ is bounded by the solutions to the solutions to the relations $S(n)=S(n-1)+S(n-2)\pm C$, $S(0)=S(1)=1$. –  1015 Feb 14 '13 at 14:44

2 Answers 2

up vote 3 down vote accepted

If your $O(1)$ tern is bounded by $C$, your sequence $T(n)$ is bounded by the solution of $S(n)=S(n-1)+S(n-2)+C$. But now writing $S(n)=S'(n)-C$ one has $S'(n)=S'(n-1)+S'(n-2)$ so it is just like the FIbonacci sequence, but with different initial values. Since all such sequences are $O(\phi^n)$, so is $S(n)$ and therefore $T(n)$.

share|improve this answer
    
What if O(1) term is unbounded? –  Rok Kralj Feb 14 '13 at 14:44
    
@RokKralj By definition, if $f\in O(1)$, then $f$ is bounded. –  Rick Decker Feb 14 '13 at 14:48
    
I see now, I have just misunderstood the sentence "If your term is bounded"... –  Rok Kralj Feb 14 '13 at 15:01

You have essentially stated the Fibonacci sequence, or at least asymptotically. There are numberless references, here for instance. And your result is not correct; as you will see from the reference, the Fib sequence behaves as $\phi^n/\sqrt{5}$

share|improve this answer
    
No, $T(n)$ is not a fibonaci sequence, because of the addition of arbitrary constant $O(1)$. Or am I missing something? –  Rok Kralj Feb 14 '13 at 14:26
1  
Asymptotically, it is. –  Ron Gordon Feb 14 '13 at 14:27
3  
How is my result not correct, if $O(\phi^n/\sqrt 5) = O(\phi^n)$? –  Rok Kralj Feb 14 '13 at 14:28
    
Ah, sorry, I'll correct. –  Ron Gordon Feb 14 '13 at 14:29

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.