 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/discrete-mathematics-continuous-mathematics-and-probability/3/a/iv/solution

0 \leq F_{n} \leq 2^{n}

F_{0} = 0 \leq 1

and

F_{1} = 1 \leq 2

hold. If the bound holds at

n - 1

and

n

F_{n + 1} = F_{n} + F_{n - 1} \leq 2^{n} + 2^{n - 1} \leq 2^{n + 1} .

Thus the definition of big O notation holds with

C = 1

, proving

F_{n} = O (2^{n}) .

 New to topics? Read the docs here!