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

Table of contents
- Solution iv

Solution

A direct mathematical induction proves

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

. The base cases

F_{0} = 0 \leq 1

and

F_{1} = 1 \leq 2

hold. If the bound holds at

n - 1

and

n

, then the Fibonacci recurrence gives

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

 Ancestors (12)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version