Appendix A — Fibonacci Notation, Terms, and Selected Identities

CANON note on notation. Throughout, $F_n$ denotes the $n$-th Fibonacci number with base cases $F_0=0$, $F_1=1$, and recurrence $F_n=F_{n-1}+F_{n-2}$ for $n\ge 2$. The golden ratio is $\phi =\frac{1+\sqrt{5}}{2}$; its conjugate is $\psi =\frac{1-\sqrt{5}}{2}$.

#The first 50 Fibonacci numbers

FACT. The following are exact values.

The full sequence and enormous term counts are catalogued as sequence A000045 in the On-Line Encyclopedia of Integer Sequences.^[•]

#Selected identities (all FACT)

For all valid $n,m$:

1. Recurrence. $F_n=F_{n-1}+F_{n-2}$.
2. Binet's formula. $F_n=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}}$, and $F_n$ is the nearest integer to ${\phi }^n/\sqrt{5}$.^[•]
3. Cassini's identity. $F_{n-1}{F}_{n+1}-F_n^2=(-1{)}^n$.^[•]
4. Catalan's identity (generalizes Cassini). $F_n^2-F_{n-r}{F}_{n+r}=(-1{)}^{n-r}{F}_r^2$.
5. d'Ocagne's identity. $F_m{F}_{n+1}-F_{m+1}{F}_n=(-1{)}^n{F}_{m-n}$.
6. Addition formula. $F_{m+n}=F_m{F}_{n+1}+F_{m-1}{F}_n$.
7. Sum of terms. $\sum _{i=1}^n{F}_i=F_{n+2}-1$.
8. Sum of squares. $\sum _{i=1}^n{F}_i^2=F_n{F}_{n+1}$.
9. Even-indexed sum. $\sum _{i=1}^n{F}_{2i}=F_{2n+1}-1$.
10. GCD property. $gcd(F_m,F_n)=F_{gcd(m,n)}$.^[•]
11. Q-matrix. ${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n=\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]$.
12. Negative indices. $F_{-n}=(-1{)}^{n+1}{F}_n$.