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

Use the inclusion-exclusion principle on the multiples of $6,8,11$ in $\{1,\dots ,527\}$. The pairwise least common multiples are $24,66,88$, and the triple least common multiple is $264$. Therefore the count isThe endpoint $528$ is excluded, which is why the numerators are $527$ rather than $528$.

The Fibonacci recurrence, with the supplied initial values, is $F_{n+2}=F_{n+1}+F_n$ for $n\ge 0$, with $F_0=0,F_1=1$. Two initial values are needed for this second-order linear recurrence relation.

Use $G_1=0$ and $G_{n+1}=n{G}_n+n-1$ for $n\ge 1$. Indeed,The initial value is $0!-1=0$, so the recurrence relation produces the specified factorial sequence.

Adding the Fibonacci recurrence and the identical recurrence relation for the Lucas numbers givesLinearity preserves this linear recurrence relation; the initial values come from $0+2$ and $1+1$.

Let $\varphi =(1+\sqrt{5})/2$, the golden ratio. Since ${\varphi }^2=\varphi +1$, multiplication by ${\varphi }^n$ gives ${\varphi }^{n+2}={\varphi }^{n+1}+{\varphi }^n$. Adding this recurrence relation to the one for $A_n$ yieldsThus the extra exponential term changes the initial values, but not the linear recurrence relation.

For $n=0$, the difference is $F_1^2-F_0{F}_2=1=(-1{)}^0$. Define $D_n=F_{n+1}^2-F_n{F}_{n+2}$. The Fibonacci recurrence givesThe inductive step therefore changes $(-1{)}^n$ into $(-1{)}^{n+1}$. By mathematical induction, $D_n=(-1{)}^n$ for all $n\ge 0$, the requested form of Cassini's identity.

Induct on $n$, with the claim quantified over every $m\ge n$. At $n=0$,Suppose the identity holds for a fixed $n$ and every $m\ge n$. For $m\ge n+1$, the Fibonacci recurrence givesApplying the induction hypothesis with $m-1\ge n$ is legitimate. This proves $F_m{F}_{n+1}-F_n{F}_{m+1}=(-1{)}^n{F}_{m-n}$ throughout its domain, a case of the Fibonacci determinant identity.