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.
Solution 1:
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.