 Solution

ID: 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/solution

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

and

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

. Suppose the bounds hold for exponents

n

and

n + 1

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$ .

 New to topics? Read the docs here!