How to evaluate / approximate polynomial sum expression over integers?

Question

Given $$P(x) = \sum_{k=0}^Nc_kx^k$$

Can we derive some exact formula for

$$\sum_{k=0}^N P(k)$$

The only thing I can think of is the integral approximation:

$$\int_{0}^{N} P(x)dx \approx \sum_{k=0}^N P(k)$$

or maybe broken into smaller pieces

$$\int_{k}^{k+1} P(x)dx \approx \frac{P(k)+P(k+1)} 2$$ Maybe there are better approaches?

Answer 1

So you are looking for a "nice" form to express $$ \sum\limits_{j = 0}^n {P(j)} = \sum\limits_{k = 0}^n {c_{\,k} \sum\limits_{l = 0}^n {l^{\,k} } } $$

Now, as far as I know, the different formulations for the sums of powers can be summarized in $$ \eqalign{ & S_m (n + 1) = \sum\limits_{0\, \le \,l\, \le \,n} {l^{\,k} } \quad \left| {\;0 \le {\rm integer }k,n} \right. = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\left\langle \matrix{ k \cr j \cr} \right\rangle \left( \matrix{ n + 1 + j \cr k + 1 \cr} \right)} = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\;j!\;\left\{ \matrix{ k \cr j \cr} \right\}\left( \matrix{ n + 1 \cr j + 1 \cr} \right)} = \cr & = {1 \over {k + 1}}\sum\limits_{0\, \le \,j\, \le \,m} {\left( \matrix{ k + 1 \cr j \cr} \right)\;B(j)\;\left( {n + 1} \right)^{\,k + 1 - j} } \cr} $$ where:
- the angle brackets denote the Eulerian Numbers;
- the curly brackets denote the Stirling Numbers of 2nd kind;
- $B(j)$ denote the Bernoulli Numbers.

Therefore, you cannot find a close form in general, unless the $c_k$ obey to a particular function of the index.

Answer 2

$$ h \sum_{k=0}^{N-1} P(kh) > \int_{0}^{1} P(x)dx > h\sum_{k=1}^N P(kh)$$

where $h=1/N$.

As N becomes larger, the magnitude of difference of the terms in the inequality decreases.