Help with this determinant I need help to calculate this determinant:
$$\begin{vmatrix}
1^k & 2^k & 3^k & \cdots & n^k \\
2^k & 3^k & 4^k & \cdots & (n+1)^k\\
3^k & 4^k & 5^k & \cdots & (n+2)^k\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
n^k & (n+1)^k & (n+2)^k & \cdots & (2n-1)^k
\end{vmatrix}$$
Where $2\leq n$ and $0\leq k \leq n-2.$
I did the $2\times 2$, $3\times 3$ and $4\times 4$ cases but I couldn't find a pattern to follow.
I did those cases by making zeros in the first column (except the $1^k$ in the first row) and then using the Laplace expansion.
The $2\times 2$ case equals: $3^k -4^k$, the  $3\times 3$ case equals: $15^k -16^k -20^k -27^k +24^k +24^k$
 A: For any $n \ge 1$, let $u_1, \ldots, u_n$ and $v_1,\ldots ,v_n$ be any elements
in any commutative ring.  
For any $0 \le k \le n-2$, consider the $n \times n$ matrix $A = (a_{ij})$ whose entry at row $i$ and column $j$ has the form:
$$a_{ij} = (u_i + v_j)^k$$
By binomial theorem, it can be decomposed as
$$a_{ij} = \sum_{\ell=0}^k \binom{k}{\ell} u_i^\ell v_j^{k-\ell}$$
This means $A$ can be rewritten as a sum of $k+1$ matrix products of column vectors
$$A = \sum_{\ell=0}^k \binom{k}{\ell} U_\ell V_{k-\ell}^T
\quad\text{ where }\quad
U_\ell = \begin{bmatrix}u_1^\ell \\ u_2^\ell \\ \vdots \\ u_n^\ell\end{bmatrix}\text{ and }
V_\ell = \begin{bmatrix}v_1^\ell \\ v_2^\ell \\ \vdots \\ v_n^\ell\end{bmatrix}.
\tag{*1}$$
Since matrix product of a pair of column vectors has rank at most $1$ and matrix rank are sub-additive, i.e. ${\rm rank}(P + Q) \le {\rm rank}(P) + {\rm rank}(Q)$, we get
$${\rm rank}(A) \le \sum_{\ell=0}^k {\rm rank}(U_\ell V_\ell^T) \le \sum_{\ell=0}^k 1 = k+1 < n$$
As a result, matrix $A$ doesn't have full rank and hence $\det A = 0$.
For the problem at hand, take $u_i = i$ and $v_j = j-1$. 
When $0 \le k \le n - 2$, the determinant at hand vanishes.
Update
If one doesn't want to use the concept of rank, there is another approach.
Construct three auxiliary $n \times n$ matrices by


*

*$U$, whose $\ell^{th}$ column is the column vector $U_{\ell-1}$ for $1 \le \ell \le k+1$ and zero otherwise.

*$V$, whose $\ell^{th}$ column is the column vector $V_{k-\ell+1}$ for $1 \le \ell \le k+1$ and zero otherwise.

*$D$, a diagonal matrix whose $\ell^{th}$ diagonal entry is $\binom{k}{\ell-1}$ 
for $1 \le \ell \le k+1$ and zero otherwise.


The decomposition of $(*1)$ can be rewritten as $A = UDV^T$. 
When $k < n - 2$, $U$ contains a zero column and hence
$$\det U = 0\quad\implies\quad\det A = \det U \det D \det V = 0$$
As a side benefit, this approach allow us to compute the determinant at hand when $k = n - 1$. 
When $u_i = i$ and $v_j = j - 1$,
$U$ is a Vandermonde matrix
with determinant
$$\det U = \prod_{1\le i < j \le n}(u_i - u_j) = \prod_{1\le i < j \le n}(i-j) = (-1)^{n(n-1)/2} \prod_{\ell=1}^{n-1} \ell!$$
$V$ can be obtained from a Vandermonde matrix but reversing the order of its columns. It is easy to see its determinant equals to
$$\det V = \prod_{1 \le i < j \le n }(v_j - v_i) = \prod_{1 \le i < j \le n}(j-i)
= \prod_{\ell=1}^{n-1} \ell!$$
The determinant of $D$ is easy, it is just the product of a bunch of binomial coefficients.  Combine these, when $k = n - 1$, the determinant at hand becomes
$$\left. \det A  \right|_{k=n-1}
= (-1)^{\frac{n(n-1)}{2}} \prod_{\ell=0}^{n-1}\binom{n-1}{\ell} \times \left(\prod_{\ell=1}^{n-1}\ell!\right)^2 = (-1)^{\frac{n(n-1)}{2}} ((n-1)!)^n$$
A: Another proof:
Consider the polynomials $P_1(X)=(X+1)^k,\; P_2(X)=(X+2)^k,\dots,\;P_n(X)=(X+n)^k$, which belong to the vector space $\mathbf R_k[X]$ of polynomials of degree at most $k$. This space has dimension $k+1$, hence, if $n>k+1$ (i.e. $k\le n-2$), these polynomials are linearly dependent, so there's a linear relation with  coefficients $\lambda_i\enspace (1\le\lambda\le n)$, not all $0$, such that the polynomial
$$Q(X)=\sum_{i=1}^{n}\lambda_iP_i(X)=0.$$
Now  observe row n° $i$ in the determinant is just $\;\bigl(P_1(i-1), P_2(i-1), \dots P_n(i-1)\bigr)$, so $Q(i-1)=0$ for all $i=1,\dots,n.\,$ If   $C_i$ denotes the $i$-th column of the determinant, this shows we have the following linear relation between columns:
$$\sum_{i=1}^{n}\lambda_i\,C_i=0, $$
hence the determinant is $0$, under the assumption $k\le n-2$.
A: Another proof. 
This involves some tricks on manipulating polynomials. 
$\mathit{Proof}.\blacktriangleleft$
Consider
$$
f(z) = 
\begin{vmatrix}
(z+1)^k & (z+2)^k & (z+3)^k & \cdots & (z+n)^k\\
2^k & 3^k & 4^k & \cdots &  (n+1)^k\\
3^k & 4^k & 5^k & \cdots & (n+2)^k \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
n^k & (n+1)^k & (n+2)^k & \cdots & (2n-1)^k
\end{vmatrix}.
$$
Then the computational definition determinant, i.e.
$$
\det(\boldsymbol A) = \sum_{\sigma \in \mathfrak S_n} \mathrm{sgn}(\sigma) \prod_1^n a_{\sigma(j), j}
$$ 
implies that $f(z)$ is a polynomial of degree $k$. The goal is to compute $f(0)$. Note that $f(1) = f(2) = \cdots = f(n-1) = 0$, since the $1^{\mathrm {st}}$ row coincides with the $ (j+1 )^{\mathrm {st}}$ row, and a determinant with duplicated rows is $0$. Therefore $f(z)$ is a real  polynomial with $n-1$ zeros while its degree is $k \leqslant n-2$. Thus the polynomial is just the zero polynomial, and the original determinant is $f(0) = 0$. $\blacktriangleright$
