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

There are $n(n-1)\cdots (n-k+1)$ ordered selections without replacement. Each unordered $k$-element subset occurs in exactly $k!$ orders, so the binomial coefficient isOne precise specification of its domain, codomain, and map isHere ${\mathbb{N}}_0=\{0,1,2,\dots \}$, and $0!=1$ includes the single empty selection. The actual values on $D$ are positive, so ${\mathbb{N}}_{+}$ is also a valid codomain. For fixed $n$, one can instead use the function $C_n:\{0,\dots ,n\}\to {\mathbb{N}}_{+}$ with $C_n(k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

Apply the factorial formula for the binomial coefficients:For $n=0$ or $n=1$, the same equality holds with the conventional zero value when the lower index exceeds the upper index.

For $0\le k\le n$, the adjacent binomial coefficients obeySince $\left(\genfrac{}{}{0ex}{}{n}{k}\right)>0$ and $k+1>0$, the sign is determined by the numerator:The printed codomain ${\mathbb{N}}_{+}$ is inconsistent with the displayed map: $g(n)=-1$, and when $n$ is odd, $g((n-1)/2)=0$. With the usual extension $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$ for $k>n$, $g$ is a function ${\mathbb{N}}_0\to \mathbb{Z}$, and $g(k)=0$ for $k>n$; the positive range above remains unchanged. Without that extension, the natural domain is $\{0,\dots ,n\}$.^[ref]

In the intended range $0\le k\le n$, division by the positive binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ givesConsequently the intended remainder isThere is a necessary qualification to the printed unrestricted domain. If binomial coefficients outside $0\le k\le n$ are extended by zero, then every $k>n$ satisfies $g(k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$, regardless of $n\mathrm{mod}3$. For example, $n=3,k=4$ satisfies the literal equality but has $n\mathrm{mod}3=0$. Thus the literal extended-domain premise alone does not determine a remainder; the boxed conclusion requires $0\le k\le n$, or equivalently here $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\ne 0$.

For adjacent binomial coefficients, the ratiois greater than $1$ when $k<(n-1)/2$, equal to $1$ at $k=(n-1)/2$, and less than $1$ afterwards. For odd $n$, the row is therefore increasing up to its two equal central entries and decreasing after them. The maximum is attained exactly atThey are distinct, including when $n=1$, so $k^{\ast }$ is not unique. This is the unimodality of binomial coefficients.

We prove Cassini's identity by mathematical induction. At $n=1$,Suppose $D_n=F_{n-1}{F}_{n+1}-F_n^2=(-1{)}^n$. The Fibonacci recurrence gives $F_{n-1}=F_{n+1}-F_n$ and henceThe induction proves

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