Appendix B — Proof Notes

Sketches, at the level of a careful undergraduate review. Each is a FACT with a citation to a standard treatment.

B.1 — Convergence of ratios to $\phi$. Let $r_n=F_{n+1}/F_n$. Dividing $F_{n+1}=F_n+F_{n-1}$ by $F_n$ gives $r_n=1+1/r_{n-1}$. If $r_n\to r$, then $r=1+1/r$, so $r^2-r-1=0$, whose positive root is $\phi$. Convergence itself follows because the map $x\mapsto 1+1/x$ is a contraction near $\phi$; alternatively, it follows directly from Binet's formula below.^[•]

B.2 — Binet's formula (by characteristic equation). The recurrence $F_n=F_{n-1}+F_{n-2}$ is linear with characteristic equation $x^2=x+1$, roots $\phi$ and $\psi$. The general solution is $F_n=A{\phi }^n+B{\psi }^n$. Imposing $F_0=0$ and $F_1=1$ gives $A=1/\sqrt{5}$, $B=-1/\sqrt{5}$, hence $F_n=({\phi }^n-{\psi }^n)/\sqrt{5}$. Since , ${\psi }^n\to 0$, so $F_n\approx {\phi }^n/\sqrt{5}$; because for all $n\ge 0$, $F_n$ is the nearest integer to ${\phi }^n/\sqrt{5}$.^[•]

B.3 — Cassini's identity (by induction or determinant). Taking determinants of the Q-matrix identity $Q^n=\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]$: since $detQ=-1$, $det\left(Q^n\right)=(-1{)}^n$, and expanding the right side gives $F_{n+1}{F}_{n-1}-F_n^2=(-1{)}^n$, which is Cassini's identity. This is the slickest proof and shows why the identity's sign alternates.^[•]

B.4 — Time complexity of naive recursion. Let $T\left(n\right)$ be the number of calls to compute $F_n$ by naive recursion. Then $T\left(n\right)=T(n-1)+T(n-2)+1$, which itself grows like the Fibonacci numbers, i.e. like ${\phi }^n$. Hence naive recursion is exponential; iteration and memoization reduce this to linear by preserving intermediate results, and matrix exponentiation to logarithmic by repeated squaring.^[•]

B.5 — Tiling interpretation. The number of ways to tile a $2\times n$ board with $1\times 2$ dominoes satisfies $D\left(n\right)=D(n-1)+D(n-2)$ with $D\left(0\right)=D\left(1\right)=1$, giving $D\left(n\right)=F_{n+1}$. The recurrence arises because a tiling ends either in one vertical domino (reducing to $2\times (n-1)$) or two stacked horizontal dominoes (reducing to $2\times (n-2)$).^[•]

B.6 — Sum identity by telescoping. To show $\sum _{i=1}^n{F}_i=F_{n+2}-1$: write each term using the recurrence as $F_i=F_{i+2}-F_{i+1}$. Then the sum telescopes: $\sum _{i=1}^n(F_{i+2}-F_{i+1})=F_{n+2}-F_2=F_{n+2}-1$, since $F_2=1$. Telescoping is the additive analogue of preservation — each term cancels against its neighbor, leaving only the boundary terms, so the whole history collapses to its endpoints. This is a small, clean example of a running total that can be validated in one step against a closed form rather than by re-adding the whole sequence, exactly the kind of cheap invariant check Chapter 8 recommends.

B.7 — GCD property (sketch). To show $gcd(F_m,F_n)=F_{gcd(m,n)}$: the key lemma is $gcd(F_m,F_n)=gcd(F_m,F_{n-m})$ for $n>m$, which follows from the addition formula $F_n=F_{n-m}{F}_{m+1}+F_{n-m-1}{F}_m$ (identity 6 of Appendix A) by reducing modulo $F_m$. Iterating this lemma performs the Euclidean algorithm on the indices, so the index of the resulting Fibonacci number is $gcd(m,n)$.^[•] This identity is striking because it means the Fibonacci numbers carry the divisibility structure of their own indices — a form of preserved provenance built into the sequence itself: the arithmetic relationship between positions survives in the arithmetic relationship between values.