[Math] Fibonacci sequence for the determinants

linear algebra

It's really easy question but I think I'm missing some points.

Let $F_n$ is $n$ by $n$ matrix $$F_n=\det \begin{pmatrix} 1 & -1 & & & & \\ 1 & 1 & -1 & & & \\ & 1 & 1 & -1 & & \\ & & . & . & . \\ & & & 1 & 1 \end{pmatrix}$$
Then $F_n=a_{11}c_{11}+a_{12}c_{12}=F_{n-1}+F_{n-2}$
where $a_{ij}$ is $(i,j)$ element of the matrix and $c_{ij}$ is cofactor.

I can't understand the second entry $F_{n-2}$. I think $a_{12}c_{12}$ is not $F_{n-2}$ since it doesn't have $1$ in $(2,1)$ entry of the matrix.

Best Answer

Let's look at a simple example and you will see the pattern. Perform Laplace expansion of $F_4$ along the first row, we get $$F_4 =\left\lvert\begin{matrix}1&-1\\1&1&-1\\&1&1&-1\\&&1&1\end{matrix}\right\rvert =F_3 + \underbrace{(-1)}_{a_{12}} \times \underbrace{(-1)\left\lvert\begin{matrix}1&-1\\&1&-1\\&1&1\end{matrix}\right\rvert}_{c_{12}}. $$ Now, expand the second 3x3 minor on RHS along the first column, we get $$ \left\lvert\begin{matrix}1&-1\\&1&-1\\&1&1\end{matrix}\right\rvert =\left\lvert\begin{matrix}1&-1\\1&1\end{matrix}\right\rvert =F_2. $$ Hence $F_4=F_3+F_2$.