# What is the asymptotical bound of this recurrence relation?

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?

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

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

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

-
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
Asymptotically, it is. – Ron Gordon Feb 14 '13 at 14:27
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