Matrix whose Determinant is Fibonacci Number

== Theorem ==
The $n \times n$ determinant:
:$D_n = \begin{vmatrix}
1 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 \\
1 & 1 & -1 & 0 & \cdots & 0 & 0 & 0 \\
0 & 1 & 1 & -1 & \cdots & 0 & 0 & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & 0 & \cdots & 1 & 1 & -1 \\
0 & 0 & 0 & 0 & \cdots & 0 & 1 & 1 \\
\end{vmatrix}$
evaluates to $F_{n + 1}$.
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 2}$, let $\map P n$ be the proposition:
:$D_n = F_{n + 1}$
=== Basis for the Induction ===
$\map P 2$ is the case:
Thus $\map P 2$ is seen to hold.
$\map P 3$ is the case:
Thus $\map P 3$ is seen to hold.
$\map P 2$ and $\map P 3$ together form the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P k$ and $\map P {k - 1}$ are true, where $k \ge 3$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
from which it is to be shown that:
:$D_{k + 1} = F_{k + 2}$
=== Induction Step ===
This is the induction step:
Recall the definition of $D_n$:
:$D_{k + 1} = \underbrace {\begin{vmatrix}
1 & -1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\
1 & 1 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 \\
0 & 1 & 1 & -1 & 0 & \cdots & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & -1 & \cdots & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & \cdots & 0 & 0 & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & 0 & 0 & \cdots & 1 & -1 & 0 \\
0 & 0 & 0 & 0 & 0 & \cdots & 1 & 1 & -1 \\
0 & 0 & 0 & 0 & 0 & \cdots & 0 & 1 & 1 \\
\end{vmatrix} }_{k + 1 \text { columns} }$
Expanding by $1$st row using the Expansion Theorem for Determinants requires the evaluation of $2$ cofactors:
:$1 \times C_{1 1}$
and:
:$\paren {-1} \times C_{1 2}$
where $C_{r s}$ denotes the determinant of order $k$ obtained from $D_{k + 1}$ by deleting row $r$ and column $s$.
By the construction of $D_{k + 1}$, it can be seen that $C_{1 1}$ is $D_k$.
The structure of $C_{1 2}$ is seen to be:
:$C_{1 2} = \paren {-1} \times \underbrace {\begin{vmatrix}
1 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 \\
0 & 1 & -1 & 0 & \cdots & 0 & 0 & 0 \\
0 & 1 & 1 & -1 & \cdots & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & \cdots & 0 & 0 & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & 0 & \cdots & 1 & -1 & 0 \\
0 & 0 & 0 & 0 & \cdots & 1 & 1 & -1 \\
0 & 0 & 0 & 0 & \cdots & 0 & 1 & 1 \\
\end{vmatrix} }_{k \text { columns} }$
By Determinant with Unit Element in Otherwise Zero Column:
:$C_{1 2} = \paren {-1} \times \underbrace {\begin{vmatrix}
1 & -1 & 0 & \cdots & 0 & 0 & 0 \\
1 & 1 & -1 & \cdots & 0 & 0 & 0 \\
0 & 1 & 1 & \cdots & 0 & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 1 & -1 & 0 \\
0 & 0 & 0 & \cdots & 1 & 1 & -1 \\
0 & 0 & 0 & \cdots & 0 & 1 & 1 \\
\end{vmatrix} }_{k - 1 \text { columns} }$
which equals $-D_{k - 1}$.
Putting this together, we have:
So $\map P k \land \map P {k - 1} \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{\ge 2}: D_n = F_{n + 1}$
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $24$
Category:Fibonacci Numbers
Category:Determinants