$n\times n$ matrix with zero determinant? Let $n\ge 3$ be a natural number, and for $1\leq k\leq n-2$ consider the $n\times n$ matrix
$$A_{n,k}=\begin{pmatrix}
      1^{k}&       2^{k}&  \cdots& n^{k}\\
    (n+1)^k&     (n+2)^k&  \cdots& (2n)^k\\
     \vdots&      \vdots&        & \vdots\\
(n^2-n+1)^k& (n^2-n+2)^k&  \cdots& n^{2k}        
\end{pmatrix}_{\large{.}}$$
It seems that $\det (A_{n,k})=0$. I can prove this for $n=3$ and $k=1$, and for all $n\ge 4$ and $k=1,2.$ But my ways do not generalize to higher values of $k$.
Is there a simple proof that $\textbf{$\det(A_{n,k})=0$?}$
 A: Notice that every row of the matrix is a linear combination of rows $(1^s,2^s,\dots,n^s)$, $0\leq s\leq k$ (just expand using binomial formula). So they must be linearly dependent.
A: Here's a different way to look at it and generalize it. Let's start with an easier problem: If instead we take a matrix of the first $n^2$ Fibonacci numbers (n>2) we also get a matrix with determinant 0.  Why is this true? The third column will just be the sum of the first two.
Well if we replace the Fibonacci numbers by any sequence $A_i$ defined recursively where each term is a fixed linear combination of the previous m terms, then the same argument shows that a matrix filled with the first $n^2$ (with $n>m$) elements of this sequence will have determinant 0.
Now back to your problem, it would be enough to see that the sequence $1^k, 2^k, 3^k,...$ satisfies a fixed linear recurrence relation based on the previous k+1 terms. Well it just so happens that $a^k = {{k+1}\choose{1}}(a-1)^k -  {{k+1}\choose{2}}(a-2)^k + {k+1\choose 3}(a-3)^k - ... \pm (a - k-1)^k $ for all $a$. (I didn't just pull that recurrence out of nowhere, there is a lot of great structure in the set of sequences satisfying some linear recurrence that one can exploit to find such relations)
