An Interesting Matrix

Consider the matrix

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}$

It has an interesting relationship with this sequence:

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$

Do you remember the Fibonacci sequence? Begin with $0$ and $1$. Get each new term by adding the two previous terms. This is an important example of a recursively defined sequence. If we were to define the sequence symbolically:

$F_n = \left\{ \begin{array}{rl} 0 & \text{if } n = 0\\ 1 & \text{if } n = 1\\ F_{n-1} + F_{n-2} & \text{if } n > 1 \end{array} \right.$

The reason this is a recursive definition is because the general term $F_n$ is written as a function of preceding terms.

Let’s construct a column vector of the first two numbers in that sequence:

$\begin{bmatrix} 0 \\ 1 \\ \end{bmatrix}$

Now let’s repeatedly left-multiply our matrix with this vector. (Remember that matrix multiplication is not commutative and in this case right-multiplication would not be defined.) As we proceed, we might notice a pattern…

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix}$ $\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ \end{bmatrix}$ $\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 2 \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \\ \end{bmatrix}$ $\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 \\ 3 \\ \end{bmatrix} = \begin{bmatrix} 3 \\ 5 \\ \end{bmatrix}$ $\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 \\ 5 \\ \end{bmatrix} = \begin{bmatrix} 5 \\ 8 \\ \end{bmatrix}$ $\vdots$

You should notice the Fibonacci sequence emerging as you continue to multiply by that matrix. It is tempting to conclude that this matrix can be used to calculate any number in the Fibonacci sequence, but that has to be proved. We can personally verify that the statement holds for the first hundred terms, but I would ask you about the thousandth. Maybe it stops working at the millionth iteration? However high we can count, we can always count one higher. This is the essence of mathematical induction. It’s a good idea to use induction whenever you have a statement concerning something that is countably infinite.

Mathematical induction is actually a form of deductive reasoning. In order for the argument to work, you need a base case. This is something that is often very trivially true, but must always be shown nevertheless. After you show the base case holds, you use the fact to be proved to show that the fact still holds after incrementation. This is the induction step.

In other words, we are trying to prove something is true for all $n$, where $n$ is a natural number. The base case corresponds to the smallest value of $n$ for which our statement has meaning. Often it’s $n=0$ or $n=1$, but sometimes it might be $n=2$, and so forth. Then, for the induction step, we take as our induction hypothesis the very statement we are trying to prove. The induction hypothesis is a statement about $n$ which we use to prove the equivalent statement about $n+1$. The base case and the induction step together form a complete proof. Let’s try it.

We want to say that if we multiply the matrix with the column vector $n$ times, the resulting column vector will have as its rows the Fibonacci numbers corresponding to $n$ and $n+1$, respectively. It’s awkward to say in English but we can write it symbolically pretty nicely:

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}^n \cdot \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} F_n \\ F_{n+1} \\ \end{bmatrix}$

Let’s prove it by induction. What would the base case be? It would make mathematical sense to have $n=0$ as the exponent of the matrix, but that would mean we multiply it zero times, which is doing nothing. So let’s use $n=1$ as the base case.

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}^1 \cdot \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} 0 \cdot 0 + 1 \cdot 1 \\ 0 \cdot 1 + 1 \cdot 1 \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} F_1 \\ F_2 \\ \end{bmatrix}$

This shows the base case is true. Now, we assume the statement is true for $n$ and prove that it’s true for $n+1$.

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}^{n+1} \cdot \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}^n \cdot \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix}$

We know this is true because we know exponents mean repeated multiplication. The reason this benefits us is because now we can use our induction hypothesis! We now see

$\begin{alignedat}{1} \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}^{n+1} \cdot \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} &= \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} F_n \\ F_{n+1} \\ \end{bmatrix} \\ &= \begin{bmatrix} F_n \cdot 0 + F_{n+1} \cdot 1 \\ F_n \cdot 1 + F_{n+1} \cdot 1 \\ \end{bmatrix} \\ &= \begin{bmatrix} F_{n+1}\\ F_n + F_{n+1}\\ \end{bmatrix} \\ &= \begin{bmatrix} F_{n+1}\\ F_{n+2}\\ \end{bmatrix} \end{alignedat}$

This completes the induction step, which completes the whole proof.