Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 2 / c / ii

Table of contents
- Solution ii

Solution

Use mathematical induction with two consecutive base cases:

F_{2} = 1 = (3/2)^{0}

and

F_{3} = 2 \geq (3/2)^{1}

. Suppose the bounds hold for exponents

n

and

n + 1

. The Fibonacci recurrence gives

F_{n + 4} = F_{n + 3} + F_{n + 2} \geq (3/2)^{n + 1} + (3/2)^{n} = \frac{5}{2} (3/2)^{n} \geq \frac{9}{4} (3/2)^{n} = (3/2)^{n + 2} .

Thus the consecutive pair of bounds advances one step. $F_{n + 2} \geq (3/2)^{n}$ for every $n \geq 0$ .

 Ancestors (12)

 View article source

 Discussion (0)

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