How to reconstruct a polynomial given $P(a),P(2a),P(3a),...$?

Question

Consider $P(x)=a_nx^n+\ldots + a_0$ a polynomial of $\deg(P)=n$.

We may reconstruct $P$ using $n+1$ independent equations, in particular, when we $P(a), P(2a),\ldots, P((n+1)a)$ are given for some $a \neq 0$.

I know $a_n$ can be easily obtained by the Difference Sequences (See for example this), but how to obtain the other terms explicitly?

One idea is to translate the problem in the language of Vandermond, but the inverse of Vandermond is a challenge itself. Does someone have any idea?

Answer 1

The polynomial $$P(x)=a_nx^n+\ldots + a_0$$ passes through points $(a,P(a)), (2a, P(2a)),.... ((n+1)a, P((n+1)a)$

We can use Lagrange interpolation to identify the polynomial passing through these points.

We can also solve the linear system of of $n+1$ equations with $n+1$ unknowns to find the coefficients.

Answer 2

Your idea to use the Vandermonde matrix does lead to a correct solution. The set up is $$\begin{bmatrix} 1 & a & a^2 & \dots &a^n \\ 1 & 2a & (2a)^2 & \dots &(2a)^n \\ \vdots & \vdots&\vdots & \vdots & \vdots \\ 1 & (n+1)a & ((n+1)a)^2 & \dots & ((n+1)a)^n \\ \end{bmatrix} \begin{bmatrix}a_0 \\ a_1 \\ \vdots \\ a_n\end{bmatrix} = \begin{bmatrix}P(a) \\ P(2a) \\ \vdots \\ P((n+1)a)\end{bmatrix} $$ The condition $a\neq 0$ guarantees that the Vandermonde matrix is invertible.