Rank/determinant of the $n\times n$ matrix $((a_{ij}))$ where $a_{ij}=(i+j-1)^2$

Note that $(k+1)^2 - k^2 = 2k+1$. Thus, we have $$ ((m+1)^2,(m+2)^2,\dots,(m+n+1)^2) = \\ (m^2,(m+1)^2,\dots,(m+n)^2) + (2m+1,2m+3,\dots,2m+2n+1) $$ Conclude (inductively, if you like) that the vectors $$ (1,2,\dots,n^2),(1,3,\dots,2n+1),(1,\dots,1) $$ span the row/column space of $A$. Or, if you prefer, you could use the basis $$ (1,\dots,1),(0,1,\dots,n-1), (0,1^2,\dots,(n-1)^2) $$

---

More generally: (I think that) as a consequence of the Newton interpolation formula, the rank of the matrix $$ \pmatrix{f(1)& f(2) & \cdots & f(n)\\ f(2) & f(3) & \cdots & f(n+1)\\ \vdots & \vdots & \ddots & \vdots\\ f(n) & f(n+1) & \cdots & f(2n+1)} $$ will have rank equal to at most $1 + \deg(f)$ (exactly $1 + \deg(f)$, whenever $n \geq 1 + \deg(f)$) for any polynomial $f$.

The fact that the upper left $3 \times 3$ submatrix of $A$ has nonzero determinant implies that the first three columns of $A$ are linearly independent, implying that the rank of $A$ is at least 3.

On the other hand, the column space of $A$ is contained in the image of the linear map which takes a quadratic polynomial $p \in P_2(\mathbb{R})$ to $(p(1), p(2), \ldots, p(n))$. Since $P_2(\mathbb{R})$ has dimension 3, this implies that the rank of $A$ is at most 3.