Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 2 / e

For a nonzero geometric sequence, substitute $H_n=c{q}^n$ into the linear recurrence and cancel $c{q}^{n-1}$:The characteristic equation of a linear recurrence therefore has rootsThe zero sequence $c=0$ is a degenerate solution for any $q$ for which the displayed expression is defined. A nonzero sequence with $q=0$ cannot satisfy the recurrence at $n=1$, since it would require $0=0+H_0$.

The linearity of the Fibonacci recurrence allows a linear combinationThe initial conditions give $A+B=0$ and $A\varphi +B\psi =1$. Since $\varphi -\psi =\sqrt{5}$, we obtain $A=1/\sqrt{5}$ and $B=-1/\sqrt{5}$. Thus Binet's formula is

Use mathematical induction with two base cases. At $n=0$, the formula gives $(1-1)/\sqrt{5}=0=F_0$. At $n=1$, it gives $(\varphi -\psi )/\sqrt{5}=1=F_1$.

If it holds at $n-1$ and $n$, then the Fibonacci recurrence givesThe identities ${\varphi }^2=\varphi +1$ and ${\psi }^2=\psi +1$ turn the numerator into ${\varphi }^{n+1}-{\psi }^{n+1}$. Thus