# How to represent $x^n$ as a sum of $P_k:= (x)(x-1)\dots(x-k+1)$?

Just for curiosity I want to represent $$x^n$$ as a sum of $$P_k:= (x)(x-1)\dots(x-k+1)$$.

Since $$x=P_1,\ xP_n= P_{n+1} +nP_n$$, this proves that it is possible for any $$x^n$$ to be represented as a sum of $$P_k:= (x)(x-1)\dots(x-k+1)$$ where $$1\le k \le n$$, $$\ n \in \mathbb{N}$$. We have $$x^n = \sum\limits_{k=1}^n C_{(n,k)} P_k$$ where $$C_{(n,k)}$$ is just some constant that depends on $$n, \ k$$, This also give us a way to calculate the first $$C_{(n,k)}$$ for $$1\le n\le 6$$.

$$x=P_1$$ $$x^2 = P_1+ P_2$$ $$x^3 = P_1 + 3P_2 +P_3$$ $$x^4=P_1 +7 P_2 + 6P_3 +P_4$$ $$x^5=P_1+15P_2 +25P_3+10P_4 +P_5$$ $$x^6=P_1+31P_2 +90P_3 +65P_4+15P_5+ P_6$$

The question is How to represent $$C_{(n,k)}$$ in a "nice" closed from? I expected at first that $$C_{(n,k)}$$ have some relation to the binomial coefficients $$x, \ x^2, \ x^3$$ I believed that such simple relation could be found, but after I calculated $$x^4, \ x^5, \ x^6$$ it turns out that $$C_{(n,k)}$$ is more complicated that I initially thought .

After some thinking representing $$x^n$$ as a sum of $$P_k$$ can be useful ,For example:

$$\sum\limits_{r=1}^m r^n = \sum\limits_{r=1}^m\sum\limits_{k=1}^n C_{(n,k)} P_k(r)$$ where $$P_k(r)=(r)(r-1)\dots(r-k+1)= k!\dbinom{r}{k}$$

$$\sum\limits_{r=1}^m \sum\limits_{k=1}^n C_{(n,k)} P_k(r)= \sum\limits_{k=1}^n C_{(n,k)} \sum\limits_{r=1}^m P_k(r)=\sum\limits_{k=1}^n C_{(n,k)} \sum\limits_{r=1}^m P_k(r)$$ $$= \sum\limits_{k=1}^n C_{(n,k)} \sum\limits_{r=1}^m k!\dbinom{r}{k}$$

$$\sum\limits_{r=1}^m\dbinom{r}{k} =\dbinom{m+1}{k+1}$$

So $$\sum\limits_{r=1}^m r^n =\sum\limits_{k=1}^n k!C_{(n,k)} \dbinom{m+1}{k+1}$$

This gives us a general formula for $$\sum\limits_{r=1}^m r^n$$.

Another example is evaluating $$\sum\limits_{r=1}^\infty\frac{r^n x^r}{r!}$$ where $$n$$ is a natural number.

$$\sum\limits_{r=1}^\infty\frac{r^n x^r}{r!} = \sum\limits_{r=1}^\infty\frac{\sum\limits_{k=1}^n C_{(n,k)} P_k(r) }{r!}x^r = \sum\limits_{k=1}^n C_{(n,k)} \sum\limits_{r=1}^\infty \frac{P_k(r)x^r}{r!}$$ $$=\sum\limits_{k=1}^n C_{(n,k)} \sum\limits_{r=1}^\infty \frac{x^r}{(r-k)!}=e^x\sum\limits_{k=1}^n C_{(n,k)} x^k$$

This is related to Stirling numbers of the first kind and the second kind.

Specifically, (see https://en.wikipedia.org/wiki/Falling_and_rising_factorials#Connection_coefficients_and_identities) \begin{align} x^n & = \sum_{k=0}^{n} \begin{Bmatrix} n \\ k \end{Bmatrix} (x)_{k} \\ & = \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} (-1)^{n-k} x^{(k)}, \end{align} where $$\begin{Bmatrix} n \\ k \end{Bmatrix}$$ is Stirling numbers of the second kind.

You can also understand this from the perspective of Vieta's.

Since $$P_k:= (x)(x-1)\dots(x-k+1)$$, by Vieta's, we have $$P_k = x^k + a_{k-1}^{(k)} x^{k-1} + \cdots + a_{1}^{(k)} x + a_0^{(k)}$$ with $$a_{k-1}^{(k)} = \frac{k(k-1)}{2}.$$ Hence, $$$$x^n = P_n + \frac{n(n-1)}{2} P_{n-1} + b_{n-2}^{(n)} P_{n-2} + \cdots + b_{n-2}^{(n)} P_{n-2} + b_{1}^{(n)} P_{1}.$$$$

We make sure that the coefficient of $$x^{n-1}$$ on the RHS is $$0$$ as in LHS. Now, the coefficient of $$x^{n-2}$$ on the RHS is $$a_{n-1}^{(n)} a_{n-2}^{(n - 1)} + b_{n-2}^{(n)}$$, which should be $$0$$, and thus $$b_{n-2}^{(n)} = \frac{n(n-1)}{2} \times\frac{(n-1)(n-2)}{2} = \frac{n (n-1)^2 (n-2)}{4}.$$

So now we have $$$$x^n = P_n + \frac{n(n-1)}{2} P_{n-1} + \frac{n (n-1)^2 (n-2)}{4} P_{n-2} + b_{n-3}^{(n)} P_{n-3} + \cdots + b_{n-2}^{(n)} P_{n-2} + b_{1}^{(n)} P_{1}.$$$$ We use Vieta's again to get $$a_{k-2}^{(k)} = \sum_{i \neq j \in [k-1]} ij.$$ (See What is the sum of products of pairs of integers: $\sum_{0\le i<j\le n} ij$?)

• But the numbers $1, 31, 90, 65, 15, 1$ at that oeis page don't match up with what OP has written, $1,31,140,75,15,1$. Commented Mar 27 at 9:02
• @GerryMyerson He is right, I made a mistake.
– pie
Commented Mar 27 at 9:27

Maybe this can be another way to solve the problem, let me know if you agree with me.

You can observe that

$$P_k(j)=0$$

for each $$j\leq k-1$$, and that

$$P_k(j)=j(j-1)\cdots (j-k+1)=\binom{j}{k}k!$$

Now we have that

$$x^n=\sum_{k=1}^nC_{n,k}P_k \implies j^n=\sum_{k\leq j}C_{n,k} \binom{j}{k}k!$$

Hence you get the following linear system

$$\begin{pmatrix}1 & 0 & 0 & \dots & 0 \\ \binom{2}{1}1!& \binom{2}{2}2! & 0 & \dots &0 \\ \vdots & && &\\ \binom{n}{1}1! & \binom{n}{2}2! & \dots & &\binom{n}{n}n! \end{pmatrix}C_n=\begin{pmatrix}1^n \\ 2^n \\ \vdots \\ n^n\end{pmatrix}$$

You can find the inverse of this matrix to get the values of $$C_{n,k}$$.

You can find here a way to invert a lower triangular matrix.

• the link doesn't work, But this is a nice representation of this problem.
– pie
Commented Mar 27 at 9:31
• Link should be math.stackexchange.com/questions/1003801/… Commented Mar 27 at 10:04
• I am sorry, now it works :) Commented Mar 27 at 10:57