Call your displayed matrix $H_{M,N}$.
Theorem The following are equivalent:
$u$ is the Taylor series of a rational function.
There is a finite sequence $q_0,\ldots, q_N$, not all zero, such that for all $m>>0$, $a_mq_N+a_{m+1}q_{N-1}+\cdots+a_{m+N}q_0=0$.
There exists $N$ and $M$ such that $|H_{m,N}|=0$ for all $m>M$.
There exists $M$ and $N$ such that $|H_{m,n}|=0$ for all $m>M$ and $n>N$.
Proof that 1) is equivalent to 2):
$u$ is rational iff there is a polynomial $q$ with $qu$ a polynomial. Taking the $q_i$ to be the coefficients of $q$, we are done.
Proof that 2) implies 3): Suppose $a_mq_N+\cdots+a_{m+N}q_0=0$ for all $ m>M$. Then for all $m>M$, $H_{m,N}$ kills the column vector $\pmatrix{q_0&q_1&\ldots&q_N}^T$, so $|H_{m,N}|=0$.
Proof that 2) implies 4): Exactly as above, noting that $$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$
Proof that 4) implies 3): Trivial.
Proof that 3) implies 2):
Let $N$ be the smallest number with the property that there exists $M$ with $|H_{m,N}|=0$ for all $m>M$. If $M=1$, then $u$ is a polynomial and we are done. Otherwise there are arbitrarily large values of $m$ with $|H_{m,N-1}|\neq 0$.
Claim: $|H_{m,N-1}|\neq 0$ for any m>M. Proof of claim: Let $m>M$. It is pretty easy to check that $$|H_{m,N-1}||H_{m+2,N-1}|=|H_{m+1,N-1}|^2+|H_{m,N}||H_{m+2,N-2}|$$ (I'll come back and insert a proof of this displayed equation when I have a little more time.) By assumption, $|H_{m,N}|=0$, so $|H_{m,N-1}|=0$ would imply $|H_{m+1,N-1}|=0$, whence by induction $|H_{m+p,N-1}|>0$ for all $p>0$, contradicting the last line of the preceding paragraph. This proves the claim.
Continue to assume $m>M$.
Note that $H_{m,N}$ is an $(N+1)\times (N+1)$ matrix of determinant zero that contains a nonsingular $N\times N$ submatrix (namely $H_{m,N-1}$) and hence has rank precisely $N$. Thus there is a unique (up to linear multiples) column vector $\overline{q}$ such that $$H_{m,N}\overline{q}=0$$
Then $\overline{q}$ is the unique (again up to scalar multiples) column vector killed by the top $n$ rows of $H_{n,M}$ and also the unique column vector killed by the bottom $n$ rows. Now since $H_{m+1,N}$ is also rank 1, and because its kernel must be killed by the bottom $n$ rows of $H_{n,M}$,it follows that the kernel is again generated by the same vector $\overline{q}$, and by induction $\overline{q}$ is killed by $H_{m+p,N}$ for all $p\ge 0$, so that in particular $a_{m+p}b_0+\cdots+a_{m+p+N}b_N=0$ for all $p>0$, which, modulo a change of notation, is 2).
Edited to add:
The displayed equation above is a special case of the following:
Theorem: Let $a,b,c,d$ be scalars. Let $\alpha,\beta$ be row vectors of length $n$. Let $\phi,\psi$ be columns of length $n$. Let $B$ be an $n\times n$ matrix. Let $A$ be the following $(n+2)\times(n+2)$ matrix: $$A=\pmatrix{a&\alpha&b\cr\phi&B&\psi\cr c&\beta&d\cr}$$ Then $$det\pmatrix{a&\alpha\cr\phi& B\cr}\cdot det\pmatrix{B&\psi\cr \beta &d\cr} =det\pmatrix{\alpha&b\cr B&\psi\cr} det\pmatrix{\phi&B\cr c&\beta\cr}+det(A)\cdot det(B)$$.
Proof: We can assume $B$ is invertible and then premultiply $A$ by $$\pmatrix{1&0&0\cr 0&B^{-1}&0\cr 0&0&1\cr}$$ where the zeroes represent scalars, rows or columns as appropriate. This does not affect the truth of the theorem and allows us to assume $B$ is the identity, after which row and column operations render the desired equality trivial.