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

The base case $n=3$ isAssume the displayed formula holds at some $n\ge 3$. Adding the next term yieldsThe last step uses $(2n-1)(n+1)-2n=(2n+1)(n-1)$. This is the required formula at $n+1$, completing the proof by mathematical induction. The identity holds for all $n\ge 3$.

Use mathematical induction with two consecutive base cases: $F_2=1=(3/2{)}^0$ and $F_3=2\ge (3/2{)}^1$. Suppose the bounds hold for exponents $n$ and $n+1$. The Fibonacci recurrence givesThus the consecutive pair of bounds advances one step. $F_{n+2}\ge (3/2{)}^n$ for every $n\ge 0$.