A pattern in determinants of Fibonacci numbers?

Let $$F_n$$ denote the $$n$$th Fibonacci number, adopting the convention $$F_1=1$$, $$F_2=1$$ and so on. Consider the $$n\times n$$ matrix defined by

$$\mathbf M_n:=\begin{bmatrix}F_1&F_2&\dots&F_n\\F_{n+1}&F_{n+2}&\dots&F_{2n}\\\vdots&\vdots&\ddots&\vdots\\F_{n^2-n+1}&F_{n^2-n+2}&\dots&F_{n^2}\end{bmatrix}.$$

I have the following conjecture:

Conjecture. For all integers $$n\geq3$$, $$\det\mathbf M_n=0$$.

I have used some Python code to test this conjecture for $$n$$ up to $$9$$, but I cannot go further. Note that $$\det\mathbf M_1=\det\mathbf M_2=1$$. Due to the elementary nature of this problem I have to assume that it has been discussed before, perhaps even on this site. But I couldn't find any reference on it, by Googling or searching here. Can someone shed light onto whether the conjecture is true, and a proof of it if so?

• Fun question. Next time I teach matrix theory I might use this as an extra credit problem on a homework set involving determinants. As you know now, the solution isn't hard, but it would take a pretty clever student to spot it on their own. Thanks. – John Coleman Dec 3 '18 at 12:19
• Problem A3 from the 2009 Putnam competition has a very similar statement and a very similar solution, only replacing $F_k$ by $\cos k$ (in radians). – Misha Lavrov Dec 3 '18 at 15:46

Here's a hint: what's the relationship between $$F_{k+1}+F_{k+2}$$ and $$F_{k+3}$$? What does that say about the 1st, 2nd, and 3rd columns of this matrix?
The resolution is remarkably simple (many thanks to obscurans' answer for the hint!) By the definition of the Fibonacci numbers, $$F_k+F_{k+1}=F_{k+2}$$ for all $$k$$. If $$n\geq3$$ then these numbers are going to be in the first three columns of every row. Hence the first three rows are linearly dependent, so the determinant is $$0$$. It follows from this that any such sequence following a linear recurrence (of the form $$F_{n}=aF_{n-1}+bF_{n-2}$$, $$a,b$$ are constant), with possibly different starting terms, also satisfies the stated conjecture. In fact, this shows that all such matrices have rank $$2$$, with the only two linearly independent columns being the first two. If the linear recurrence is of higher order, say $$m$$, then the determinant is $$0$$ when $$n>m$$, and the rank of the matrix will be $$m$$.
• One note: the matrix will have rank $\leq$ the order of the linear recurrence, which is not necessarily 2. – obscurans Dec 3 '18 at 2:11
• @obscurans Suppose that the matrix has rank $k$. Does that not mean that the linear recurrence can be rewritten as a linear recurrence of order $k$? I was under the impression that the order of a linear recurrence was the order of its simplest form, though I realize now that that may not be the case. – Spitemaster Dec 3 '18 at 15:31
• There are two different things: a particular linear recurrence, which is an equation with $n$ degrees of freedom of solutions, vs a particular fixed sequence of numbers generated by some linear recurrence. The matrix having rank $k$ does mean a linear recurrence of order $k$ can generate this sequence of numbers. – obscurans Dec 4 '18 at 2:52