Find $x_1 + x_2 + \dots+ x_{n}$ and $1^{n+1}x_1 + 2^{n+1}x_2 + \dots + {n}^{n+1}x_{n}$ given a set of linear constraints 
$x_1, x_2, ..., x_{n}$ satisfies
$$1^j x_1 + 2^j x_2 + \dots + n^j x_{n} = {(n+1)}^j,$$
where $j = 1, 2, ..., n$.


Find $x_1 +  x_2 + \dots + x_{n}$ and $1^{n+1}x_1 +  2^{n+1}x_2 + \dots + n^{n+1}x_{n}$.

My thoughts: the given constraints can be expressed in a matrix

$$A=
  \begin{bmatrix}
    \frac{1}{n+1} & \frac{2}{n+1} & ... & \frac{n}{n+1} \\
    (\frac{1}{n+1})^2 & (\frac{2}{n+1})^2 & ... & (\frac{n}{n+1})^2 \\
    ... \\ 
    (\frac{1}{n+1})^{n} & (\frac{2}{n+1})^{n} & ... & (\frac{n}{n+1})^{n} \\
  \end{bmatrix}
$$
Then $X = A^{-1} [1, 1,..., 1]^{T}$  but i don't see any special properties with this matrix. Trying the elimination doesn't lead me anywhere either..
Thorough some experiments from smaller $n$, I can find that $x_i=(-1)^{i+1}{n \choose i}$, and by observing the original equations, it does seem to work, but I'd like to find a way to derive the answers, rather than guessing and verifying it.
 A: 
but I'd like to find a way to derive the answers, rather than guessing and verifying it

The following is one such possible way, which also avoids calculating the $\,x_j\,$ explicitly.
Let $\,a_j = \sum_{k=1}^nk^j \,x_k\,$ for $\,j \ge 0\,$, with $\,a_j = (n+1)^j\,$ for $\,j=1,2,\dots,n\,$.
The form of $\,a_j\,$ indicates that it satisfies an $\,n^{th}\,$ order linear recurrence with characteristic polynomial $\,p(x)=(x-1)(x-2)\dots(x-n)\,$, which can be expanded to $\,p(x)=\sum_{j=0}^n c_j\,x^j\,$ with $\,c_n=1\,$ and $\,c_0=(-1)^n\,n!\;$ ($\,\dagger\,$). It follows that $\,\sum_{j=0}^n c_j\,a_{p+j} = 0\,$ for all $\,p \ge 0\,$, then:

*

*equation for $\,p=0\,$ gives $\,a_0=x_1+x_2+\dots+x_n\,$:

$$
a_0 = - \frac{1}{c_0}\sum_{j=1}^{n} c_j\,a_j = - \frac{1}{c_0}\sum_{j=1}^{n} c_j\,(n+1)^j = -\frac{1}{c_0}\left(p(n+1)-c_0\right)= 1-\frac{n!}{(-1)^n\,n!}
\\ = 1-(-1)^n
$$

*

*equation for $\,p=1\,$ gives $\,a_{n+1}=1^{n+1}x_1 +  2^{n+1}x_2 + \dots + n^{n+1}x_{n}\,$ after similar calculations.

($\,\dagger\,$) $\;$ The polynomial $\,p(x)=(x-1)_n\,$ is a falling factorial and the coefficients $\,c_j=s(n,j)\,$ are Stirling numbers of the first kind, though the answer did not require or use that.
