I am researching about linear recurrence relations. I noticed that for every positive integer $k$, the sequence $\{n^k\}_{n=1}^\infty$ is a solution of the following homogeneous linear recurrence relation: $$\sum_{i=0}^{k+1}c_ia_{n+i}=0\quad,\quad c_i=\binom{k+1}{i}\left(-1\right)^{i}\quad,\quad\forall n\in\mathbb{N}$$ (The proof is a straightforward use of the identities involving binomial coefficients.)
The recursive relation above is one of order $k+1$. Is it possible to find a homogeneous linear recurrence relation of smaller order, for which $\{n^k\}_{n=1}^\infty$ is a solution?
Hints: Your question is equivalent to check if $(X+\ell)^k$ for $\ell = 0,\ldots,k$ is a basis of $\mathbb R_k[X]$. This is equivalent to say if the matrix $\left(\binom{k}{j}\ell^j\right)_{0\le\ell\le k,\,0\le j\le k}$ is invertible.