Solution
= Solution
A direct <mathematical induction> proves $0\le F_n\le2^n$. The base cases $F_0=0\le1$ and $F_1=1\le2$ hold. If the bound holds at $n-1$ and $n$, then the <Fibonacci recurrence> gives
$$
F_{n+1}=F_n+F_{n-1}\le2^n+2^{n-1}\le2^{n+1}.
$$
Thus the definition of <big O notation> holds with $C=1$, proving
$$
\boxed{F_n=O(2^n).}
$$