Prove Upper Bound (Big O) for Fibonacci's Sequence?

Question

NOTE: We are not to use proofs (limits, induction, or otherwise) in this problem.

We were to prove the upper bound for the Fibonacci recursion is some exponential. The Fibonacci recurrence relation is given as T(n) = T(n-1) + T(n-2) + 1. Can someone please explain the recursive substitution happening here:

Prove T(n) = O(α^n).
α^n = α^(n-1) + α^(n-2) + 1
α^2 = α + 1 + 1/(α^(n-1))
α^2 = α + 1
α = 1.618 (approx.)

T(n) is interchangeable.
O(n) = 1.6^n

And how is this proving the upper bound, Big O, for that recursion? We are supposed to prove that the upper bound for T(n)=T(n/2) + 1 is O(log n).

Answer 1

in Fibonacci sequence, we know that

$$a_n={\frac { \left( \sqrt {5}+1 \right) ^{n}+ \left( 1-\sqrt {5} \right) ^ {n}}{{2}^{n}}}$$

now, $O(a_n) = O\left({\frac { \left( \sqrt {5}+1 \right) ^{n}}{{2}^{n}}} \right)$

$=O((1.62)^n)$ (Rounding off to 2 decimal places)

Infact you can write this as

$= O(2^n)$

Answer 2

First, the Fibonacci recurrence is really $F_{n + 2} = F_{n + 1} + F_n$ with $F_0 = 0$, $F_1 = 1$.

If you compute a few $F_{n + 1} / F_n$, you'll see they seem to converge to a value near 1.6. As the question doesn't ask for the "best" $a$, we can as well pick $a = 2$ if that makes the work simpler. So we want to prove that there is a constant $c$ such that $F_n \le c \cdot 2^n$ for large enough $n$. It looks like $c = 1$ will do.

Certainly we have $F_0 \le 1 \cdot 2^0$ and $F_1 \le 1 \cdot 2^1$ as base cases. Now use induction: $$ F_{n + 2} = F_{n + 1} + F_n \le 2^{n + 1} + 2^n \le 2^{n + 2} $$ and you are done.

Answer 3

Your $T(n)$ is not the Fibonacci sequence, but that doesn't matter; the asymptotic growth is still the same. Indeed, set $U(n) = T(n) + 1$, so that the recurrence relation becomes $$U(n) = U(n-1) + U(n-2).$$

Now suppose you want to prove that $T(n) = O(\alpha^n)$ (or equivalently, that $U(n) = O(\alpha^n)$) for some $\alpha$. This means that for all $n \ge 1$, $U(n) \le c \alpha^n$ for some constant $c$. (Usually one says "for all suffiicently large $n$", but you can make it "for all $n$" by picking a $c$ large enough.)

So, assuming that you have proved this for a couple of base cases (which you anyway have to do: you haven't specified $T(1)$ and $T(2)$ or any such starting points to determine the sequence), to prove it by induction you'd have to prove that $$U(n) \le c \alpha^n$$ starting from the induction hypothesis that $U(m) \le c\alpha^m$ for all $m < n$. So, you'd need $$c \alpha^{n-1} + c\alpha^{n-2} \le c \alpha^n,$$ or dividing throughout by $c\alpha^{n-1}$, $$ 1 + \alpha \le \alpha^2.$$

This is true, among $\alpha > 1$, for $\alpha = \frac{1 + \sqrt{5}}{2}$ (or greater), and therefore you have proved that $T(n) = O(\alpha^n)$ for any such $\alpha$.

---

Without the $U(n) = T(n) + 1$ trick, we'd want to prove that $$1 + \alpha + \frac{1}{c\alpha^{n-1}} \le \alpha^2$$ for some large $n$, which we can say (as $1/{c\alpha^{n-1}} \to 0$) is satisfied for $\alpha$ only slightly larger than the solution $1 + \alpha = \alpha^2$.

---

In general, given any linear recurrence relation, the same trick works: guess that the general $n$th term is of the form $cx^n$, write down an equation for $x$ (which will be a polynomial), and if $\alpha$ is the largest root of that polynomial equation, then you'll have $T(n) = O(\alpha^n)$.