I used gpt5.6-sol to help find a proof for this question. I also verified the proof in lean: https://theoremdb.org/statements/fib-problem-determinant-range/#lean-verification, which is why it took me a week to get to posting this answer.
Setup. For $n\ge 1$ let $M_n=(m_{ij})_{1\le i,j\le n}$ be the $0/1$ matrix with
$$ m_{ij}=\begin{cases}1,& i+j\ \text{is a Fibonacci number},\\ 0,&\text{otherwise.}\end{cases} $$
The claim is that $\det M_n\in\{-1,0,1\}$ for all $n$. In fact something stronger is true:
Theorem. Every $M_n$ is totally unimodular. Consequently every square minor of $M_n$, in particular $\det M_n$, lies in $\{-1,0,1\}$.
Throughout, write $q_0=1,\ q_1=2,\ q_{s+1}=q_s+q_{s-1}$, so that $q_0,q_1,q_2,\dots=1,2,3,5,8,13,\dots$ are the distinct positive Fibonacci numbers. Since every index sum satisfies $i+j\ge 2$, the value $q_0=1$ is never attained, and "$i+j$ is Fibonacci" means $i+j=q_s$ for some $s\ge 1$.
Let $Q_n$ be the bipartite graph with row vertices $r_1,\dots,r_n$, column vertices $c_1,\dots,c_n$, and an edge $r_ic_j$ exactly when $i+j$ is Fibonacci; $M_n$ is its biadjacency matrix. Note that a diagonal entry $m_{ii}=1$ gives the ordinary edge $r_ic_i$, so $Q_n$ has no loops. The map $r_i\leftrightarrow c_i$ is an automorphism of $Q_n$; call it transposition symmetry.
(The loopless Fibonacci-sum graph on $\{1,\dots,n\}$, with $i\sim j$ iff $i+j$ is Fibonacci, is known to be outerplanar of treewidth $2$ :: Arman, Gunderson and Li, Properties of the Fibonacci-sum graph, arXiv:1710.10303. That does not formally transfer to the bipartite row–column graph $Q_n$, so the relevant facts are re-derived below.)
Step 0: local structure at the largest index.
Lemma 0. Fix $m\ge 1$ and let $k$ be the index with $q_k\le m<q_{k+1}$. Put $$a=q_{k+1}-m,\qquad b=q_{k+2}-m .$$ Then the neighbours of $r_m$ with label at most $m$ are exactly $c_a$, together with $c_b$ in case $q_{k+2}\le 2m$. Moreover, if $q_{k+2}\le 2m$ then $k\ge 2$ and $m>q_k$; writing $z=m-q_k\ge 1$ one has $$a+z=q_{k-1},\qquad b+z=q_{k+1},\qquad z<b\le m ,$$ and the neighbours of $c_b$ with label at most $m$ are exactly $r_z$ and $r_m$.
Proof. If $c_j$ is a neighbour of $r_m$ with $1\le j\le m$ then $m+j\in(m,2m]$. We have $q_{k+1}=q_k+q_{k-1}\le 2q_k\le 2m$ (and $q_1=2=2m$ when $k=0$, $m=1$), while $q_{k+3}=q_{k+2}+q_{k+1}>2q_{k+1}>2m$. So the only Fibonacci numbers in $(m,2m]$ are $q_{k+1}$, and $q_{k+2}$ when $q_{k+2}\le 2m$. This gives the first claim.
Suppose $q_{k+2}\le 2m$. If $m=q_k$ we would get $q_{k+2}=q_{k+1}+q_k>2q_k=2m$, a contradiction; hence $m>q_k$ and $z\ge 1$. Also $k=0$ forces $m=1,q_2=3>2$ and $k=1$ forces $m=2,q_3=5>4$, so $k\ge2$ and $q_{k-1}\ge 2$ is a genuine Fibonacci number. The two identities are immediate. From $m<q_{k+1}$ we get $b=q_{k+2}-m>q_{k+2}-q_{k+1}=q_k$, and $z=m-q_k<q_{k+1}-q_k=q_{k-1}\le q_k<b$, so $z<b\le m$.
Finally, a neighbour $r_i$ of $c_b$ with $i\le m$ satisfies $q_k<b<i+b\le m+b=q_{k+2}$, and the only Fibonacci numbers in $(q_k,q_{k+2}]$ are $q_{k+1}$ and $q_{k+2}$; these give $i=z$ and $i=m$ respectively. $\square$
Step 1: $Q_n$ is chordal bipartite.
Lemma 1. Every cycle of $Q_n$ of length at least $6$ has a chord. Equivalently, every induced cycle of $Q_n$ is a $4$-cycle.
Proof. Let $C$ be a cycle of length $\ge 6$ and let $m$ be the largest label occurring on $C$. By transposition symmetry we may assume $r_m\in C$. Every neighbour of $r_m$ on $C$ has label $\le m$, and $r_m$ has two neighbours on $C$, so by Lemma 0 we must be in the case $q_{k+2}\le 2m$, and those two neighbours are $c_a$ and $c_b$. Again by Lemma 0, the neighbours of $c_b$ with label $\le m$ are $r_z$ and $r_m$, so the second neighbour of $c_b$ on $C$ is $r_z$. Thus $C$ contains the path
$$ c_a - r_m - c_b - r_z . $$
Since $a+z=q_{k-1}$ is Fibonacci, $r_zc_a$ is an edge of $Q_n$. As $|C|\ge 6$, the vertices $c_a$ and $r_z$ are at distance $3$ along $C$, so $r_zc_a$ is a chord.
(If $b=m$, i.e. $2m=q_{k+2}$, then $c_b=c_m$ and $a=z=q_{k-1}/2$; the path is $c_a-r_m-c_m-r_a$ with the four vertices distinct since $a<m$, and the chord is the edge $r_ac_a$, which exists because $2a=q_{k-1}$.) $\square$
Step 2: few $4$-cycles through an edge.
Lemma 2. Every $4$-cycle of $Q_n$ has corner sums $q_{t-2},q_t,q_t,q_{t+1}$ for some $t$, with row increment and column increment both equal to $q_{t-1}$. Consequently every edge of $Q_n$ lies in at most two $4$-cycles.
Proof. Let a $4$-cycle use rows $x<X$ and columns $y<Y$, and set $A=x+y$, $B=x+Y$, $C=X+y$, $D=X+Y$. All four are Fibonacci, $A<B,C<D$, and $A+D=B+C$. Assume $B\le C$ and write $A=q_\alpha,B=q_\beta,C=q_\gamma,D=q_\delta$, so $\alpha<\beta\le\gamma<\delta$ and
$$ q_\delta-q_\gamma=q_\beta-q_\alpha . $$
If $\delta\ge\gamma+2$ the left side is at least $q_{\gamma+2}-q_\gamma=q_{\gamma+1}$, while the right side is less than $q_\beta\le q_\gamma$; so $\delta=\gamma+1$ and the common difference is $q_{\gamma-1}$. If $\beta\le\gamma-1$ the right side is less than $q_\beta\le q_{\gamma-1}$, contradiction; so $\beta=\gamma$, and then $q_\alpha=q_\gamma-q_{\gamma-1}=q_{\gamma-2}$. Writing $t=\gamma$ gives the stated corner sums, and both increments equal $q_t-q_{t-2}=q_{t-1}$.
Now fix an edge $r_xc_y$ with $x+y=q_s$. It can sit in such a $4$-cycle in three ways.
- As the $q_{t-2}$ corner. Then $t=s+2$ and the cycle is forced to be $\{x,x+q_{s+1}\}\times\{y,y+q_{s+1}\}$: at most one cycle, no condition.
- As the $q_{t+1}$ corner. Then $t=s-1$, the cycle is forced to be $\{x-q_{s-2},x\}\times\{y-q_{s-2},y\}$, and this requires $x>q_{s-2}$ and $y>q_{s-2}$: at most one cycle.
- As one of the two $q_t$ corners. Then $t=s$, and the two orientations require $x>q_{s-1}$ and $y>q_{s-1}$ respectively: at most one cycle each.
The two orientations in (3) cannot both occur, since $x+y=q_s=q_{s-1}+q_{s-2}<2q_{s-1}$. Cases (2) and (3) cannot both occur, since together their inequalities give $x+y>q_{s-1}+q_{s-2}=q_s$. So there is at most one cycle from (1) and at most one from (2) and (3) combined. $\square$
Step 3: faces of outerplane embeddings.
Lemma 3a. Let $H$ be a graph with an outerplane embedding, and let $f$ be a bounded face whose boundary is a cycle $C$. Then $C$ is an induced cycle of $H$.
Proof. Since $C$ bounds the face $f$, the open disk bounded by $C$ is exactly $f$, so nothing is drawn inside $C$. Suppose $uv$ were a chord; it is drawn outside $C$. The two $u$–$v$ arcs $P_1,P_2$ of $C$ each have length $\ge 2$, and $P_1\cup P_2\cup\{uv\}$ is a theta graph drawn in the plane. In any plane drawing of a theta graph one of the three $u$–$v$ paths is enclosed by the other two; here that path must be $P_1$ or $P_2$, and its internal vertices are then not on the outer face, contradicting outerplanarity. $\square$
Lemma 3b. Let $H\subseteq Q_n$ have an outerplane embedding and let $e$ be an edge of $H$ that is not a bridge. Then every bounded face of $H$ incident with $e$ is bounded by an induced $4$-cycle of $H$. Consequently, an edge that does not border the outer face lies in two $4$-cycles.
Proof. First, a bounded face of a plane graph is enclosed by some cycle of the graph contained in its boundary: the boundary walk decomposes into edge-disjoint cycles together with doubly traversed bridges, it winds once around each point of the face, the doubled bridges contribute nothing to the winding, so one of the cycles winds around the face.
Since $e$ is not a bridge it lies in a block $B$ (a maximal $2$-connected subgraph). Every bounded face $g$ of $B$ is bounded by a cycle, and nothing of $H$ is drawn inside $g$, vertices there would not lie on the outer face, so every bounded face of $B$ at $e$ is also a face of $H$. Conversely, no bounded face of $H$ at $e$ can lie in the outer face of $B$: such a face is enclosed by a cycle $Z$ of $H$, and every cycle lies in a single block. If $Z\subseteq B$, the interior of $Z$ is a union of bounded faces of $B$, disjoint from the outer face of $B$. If $Z$ lies in another block, then $Z$ meets $B$ in at most one vertex, so at least one endpoint of $e$ avoids $Z$; that endpoint lies in the closed disk of $Z$ (the face's closure does), hence strictly inside $Z$, hence off the outer face of $H$, contradicting outerplanarity.
Therefore every bounded face of $H$ at $e$ is a bounded face of $B$, bounded by a cycle $C$ of $B$. In its inherited drawing $B$ is again outerplane, since deleting the rest of $H$ only enlarges the outer face; so $C$ is induced in $B$ by Lemma 3a. A chord of $C$ in $H$ would join two vertices of $B$ and hence lie in $B$, so $C$ is induced in $H$, and Lemma 1 makes it a $4$-cycle.
Finally, suppose $e$ does not border the outer face, so both faces at $e$ are bounded. They are distinct: if they coincided, $e$ would be a bridge, the common face would be enclosed by a cycle $Z$ in a block not containing $e$ (both endpoints of $e$ on $Z$ would place $e$ in the block of $Z$), and as above an endpoint of $e$ would lie strictly inside $Z$. Hence $e$ lies in two $4$-cycles. $\square$
Step 4: $Q_n$ is outerplanar.
Lemma 4. Every $Q_n$ is outerplanar.
Proof. Induction on $n$; the case $n=1$ is trivial. Suppose $Q_{m-1}$ has an outerplane embedding and pass to $Q_m$ by adding $r_m$ and $c_m$. Let $k,a,b,z$ be as in Lemma 0. By Lemma 0 (and transposition symmetry) the new edges are among $r_mc_a,\ r_mc_b,\ r_ac_m,\ r_bc_m$.
Case $2m<q_{k+2}$. Only $c_a$ and $r_a$ are involved: $r_m$ and $c_m$ are pendant vertices attached to $c_a$ and $r_a$. Both $c_a,r_a$ lie on the outer face, so draw the two new edges there.
Case $2m=q_{k+2}$. Then $b=m$ and $a=z$, with $2a=q_{k-1}$, so $r_ac_a$ is an edge of $Q_{m-1}$. The new vertices complete the $4$-cycle $r_a-c_a-r_m-c_m-r_a$, attached along $r_ac_a$.
Case $2m>q_{k+2}$. Then $b<m$, and by Lemma 0 the vertex $c_b$ has $r_z$ as its unique neighbour in $Q_{m-1}$; by symmetry $r_b$ is pendant at $c_z$. Also $r_zc_a$ and $r_ac_z$ are edges of $Q_{m-1}$, since $a+z=q_{k-1}$. Adding $r_m$ completes the $4$-cycle $r_m-c_a-r_z-c_b-r_m$ along the edge $r_zc_a$, and adding $c_m$ completes $c_m-r_a-c_z-r_b-c_m$ along $r_ac_z$. These two attachment edges are vertex-disjoint because $z-a=2m-q_{k+2}>0$.
In the last two cases it remains to check that each attachment edge $e$ borders the outer face of the given embedding of $Q_{m-1}$. If not, then by Lemma 3b it already lies in two $4$-cycles; the newly created $4$-cycle contains a new vertex and so is a third, contradicting Lemma 2.
So each attachment edge is on the outer boundary, and the new $4$-cycle can be drawn in the outer face immediately alongside it, keeping all four of its vertices on the new outer boundary. The old pendant vertices $c_b$ and $r_b$ have their unique neighbour ($r_z$, resp. $c_z$) on that boundary, so they may be redrawn into the required positions. Vertex-disjointness of the two attachment edges means the two insertions do not interfere. This completes the induction. $\square$
Step 5: a parity lemma.
Lemma 5. Let $H$ be an outerplane graph in which every vertex has even degree and every bounded face is a $4$-cycle. Then $4\mid |E(H)|$.
Proof. Work one connected component at a time. A connected graph with all degrees even has no bridges, so its plane dual is bipartite and the faces admit a proper black/white $2$-colouring. Colour the outer face white. Then every edge borders exactly one black face, and every black face is bounded, hence a $4$-cycle. Therefore
$$ |E(H)|=\sum_{\text{black }f}|\partial f|=4\cdot\#\{\text{black faces}\}. \qquad\square $$
Step 6: conclusion via Camion's criterion.
Camion's theorem (P. Camion, Characterization of totally unimodular matrices, Proc. Amer. Math. Soc. 16 (1965), 1068–1073) states that a $\{0,\pm1\}$ matrix is totally unimodular if and only if every square Eulerian submatrix - one all of whose row sums and column sums are even - has entry sum divisible by $4$.
Let $B=M_n[I,J]$ be a square submatrix with all row and column sums even. Its support graph is the subgraph of $Q_n$ induced by $\{r_i:i\in I\}\cup\{c_j:j\in J\}$. Outerplanarity is inherited by subgraphs (Lemma 4) and chordal bipartiteness by induced subgraphs (Lemma 1), and every vertex has even degree, so there are no bridges. Fix an outerplane embedding. Every bounded face is incident with some edge, so by Lemma 3b it is bounded by an induced $4$-cycle. Lemma 5 now gives
$$ \sum_{i\in I,\,j\in J}B_{ij}=|E(B)|\equiv 0 \pmod 4 . $$
Camion's criterion therefore applies to every such $B$, so $M_n$ is totally unimodular, and in particular
$$ \det M_n\in\{-1,0,1\}\quad\text{for every }n\ge 1. \qquad\blacksquare $$