I am trying to find the permanent of a $n\times n $ ($n\geq 4$) matrix $A_n$ of the form $$ \begin{bmatrix} 1 & 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 \\ \vdots &\vdots &\vdots &\vdots &\vdots &\ddots& \vdots &\vdots \\ 1 & 0 & 0 & 0&0& 0 \cdots &1 & 1 \\ 1 & 1 & 0 & 0&0& 0 \cdots& 0 & 1 \end{bmatrix} $$ But I haven't had much luck. There is a hint for this problem though:
Let $B_n$ be the permanent of $A_n$ and calculate $B_n$ by expanding by the first row and column. Show that $B_n = B_{n−1}+ B_{n−2} − 2$. So $\{B_n − 2 | n \geq 3\}$ is a Fibonacci sequence.
I wasn't able to prove $B_n = B_{n−1}+ B_{n−2} − 2$; the rest is clear.