Question 8 of 12

Question 8

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) The Fibonacci recurrence $a_n=a_{n-1}+a_{n-2}$, $a_0=0$, $a_1=1$. (b) The binomial coefficients $\binom{n+1}{k}$, $\binom{n}{k-1}$, $\binom{n}{k}$ for integers $0\le k\le n+1$.

Find. (a) derive/verify Binet's closed form. (b) prove Pascal's identity, algebraically and combinatorially.

Approach. (a) solve the linear homogeneous recurrence via its characteristic equation $x^2=x+1$ and fit the two initial conditions. (b) prove algebraically by expanding factorials, and give the combinatorial "does the last element belong to the subset or not" bijective argument.

1. Part (a) — characteristic equation. The recurrence $a_n=a_{n-1}+a_{n-2}$ has characteristic equation $$x^2 - x - 1 = 0 \quad\Rightarrow\quad x=\frac{1\pm\sqrt5}{2}.$$ Let $\varphi=\frac{1+\sqrt5}{2}$ and $\psi=\frac{1-\sqrt5}{2}$ be the two roots. The general solution of a 2nd-order linear homogeneous recurrence is $a_n=A\varphi^n+B\psi^n$ for constants A, B fixed by the initial conditions: $$a_0=A+B=0 \quad\Rightarrow\quad B=-A$$ $$a_1=A\varphi+B\psi = A(\varphi-\psi) = A\sqrt5 = 1 \quad\Rightarrow\quad A=\frac{1}{\sqrt5},\ B=-\frac1{\sqrt5}$$ (using $\varphi-\psi=\sqrt5$). Substituting back: $$\boxed{a_n=\frac{1}{\sqrt5}\varphi^n-\frac1{\sqrt5}\psi^n =\frac1{\sqrt5}\left(\frac{1+\sqrt5}{2}\right)^n-\frac1{\sqrt5}\left(\frac{1-\sqrt5}{2}\right)^n}$$
2. Part (b) — algebraic proof of Pascal's identity. $$\binom{n}{k-1}+\binom nk = \frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!}$$ Give both fractions the common denominator $k!(n-k+1)!$ by multiplying the first by $k/k$ and the second by $(n-k+1)/(n-k+1)$: $$=\frac{n!\,k}{k!(n-k+1)!}+\frac{n!(n-k+1)}{k!(n-k+1)!} =\frac{n!\big[k+(n-k+1)\big]}{k!(n-k+1)!}=\frac{n!(n+1)}{k!(n-k+1)!}=\frac{(n+1)!}{k!(n+1-k)!} =\boxed{\binom{n+1}{k}}$$
3. Combinatorial (bijective) proof. $\binom{n+1}{k}$ counts the k-element subsets of an $(n+1)$-element set $S=\{x_1,\ldots,x_n,x_{n+1}\}$. Split every such subset by whether it contains the last element $x_{n+1}$: subsets that do contain $x_{n+1}$ are formed by choosing the other $k-1$ elements from the remaining n elements ($\binom{n}{k-1}$ ways); subsets that do not contain $x_{n+1}$ choose all k elements from the remaining n ($\binom{n}{k}$ ways). These two cases are disjoint and exhaustive, so $$\binom{n+1}{k}=\binom{n}{k-1}+\binom nk,$$ matching the algebraic result.