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

Question

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 $$

Answer 1

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

• https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
• https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
• https://en.wikipedia.org/wiki/Falling_and_rising_factorials
• The $P_k$ you defined is $(x)_{k}$, the falling factorial.

---

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.

• See also https://oeis.org/A008277

---

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

• See https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind#Expansions_for_fixed_k

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, \begin{equation} 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}. \end{equation}

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 \begin{equation} 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}. \end{equation} 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$?)

Answer 2

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.