Recurrence relation for the coefficients of the polynomial $p_n(x) = \prod_{i=0}^{n-1}(x-i)$

92 Views Asked by At

Let's consider the polynomials

$$ p_n(x) = \prod_{i=0}^{n-1}(x-i)=\sum_{i=1}^{n} a_{n,i}x^i$$.

for all $n \in \mathbb{N}$. If $n=1$, then $p_1(x) = x$ and $a_{1,1} = 1$.

Since I know that:

$$p_{n+1}(x) = p_n(x)(x-n)$$

then I can deduce the following:

$$\begin{eqnarray} \sum_{i=1}^{n+1} a_{n+1,i}x^i & = & \sum_{i=1}^{n} a_{n,i}x^i(x-n) = \\ & = & \sum_{i=1}^{n} a_{n,i}x^{i+1}-\sum_{i=1}^{n} na_{n,i}x^i = \\ & = & \sum_{i=2}^{n+1} a_{n,i-1}x^{i}-\sum_{i=1}^{n} na_{n,i}x^i = \\ & = & a_{n,n}x^{n+1} + \sum_{i=2}^{n} (a_{n,i-1}-na_{n,i})x^i -na_{n,1}x.\\ \end{eqnarray}$$

Then I get this recurrence relation for the coefficients $a$:

$$\left\{\begin{array}{lcll} a_{n+1,n+1} & = & a_{n,n} & \\ a_{n+1,i} & = & a_{n,i-1}-na_{n,i} &~\forall i \in \{2, \ldots, n\}, ~\forall n \geq 2 \\ a_{n+1,1} & = & -na_{n,1} & \\ a_{1,1} & = & 1 & \end{array}\right.$$

Is this right? I wrote a Matlab code for this but it seems to work only up to $n=19$!!! I mean, I produce two polynomials, one using the formula

$$p_n(x) = \prod_{i=0}^{n-1}(x-i)$$

and one using the recurrence relation I found. When $n=20$, the difference between the two polynomial is not $0$. Is my maths correct or I have to review my code?

1

There are 1 best solutions below

2
On BEST ANSWER

Hint: $a_{n,i}$ are the Stirling numbers of the first kind