Why does $\sum_{k=n_0}^n{P(k)}$ is a polynomial in $n$ of degree $d$? Let $P(X)$ be a polynomial over $\mathbb{Z}$ of degree $d-1$ and $n_0$ be some constant positive integer. Then why does $\sum_{k=n_0}^n{P(k)}$ is a polynomial in $n$ of degree $d$?
 A: 
Let $f\colon \mathbb Z\to \mathbb R$ be a function such that the difference function $\Delta f\colon \mathbb Z\to\mathbb R$ is a polynomial of degree $ d-1$. Then $f$ is a polynomial of degree $d$.

To see this, note that $f$ is completely determined by its values at $d+1$ consecutive places: These values determine $\Delta f$ at $d$ consecutive places, a polynomial of degree $d-1$ is determined by $d$ consecutive values, hence $\Delta f$ is fully determined, hence so is $f$ (by going up or down step by step).
On the other hand, there exists an interpolating polynomial $p$ of degree $\le d$ that coincides with $f$ on these $d+1$ places. As $\Delta p$ is a polynomial of degree $\le d-1$, then $\Delta(f-p)$ is constantly zero, hence $f-p$ is constant and in fact zero, i.e. $f=p$.
A: For $d\in\Bbb N$ let $B_d[X]=\binom Xd\in\Bbb Q[X]$, where
$$\binom Xd=\frac{X(X-1)(X-2)\ldots(X-(d-1))}{d!}$$
in accordance with the usual definition of binomial coefficients. Then $B_0[X]=1$ while for $d>0$ one has $B_d[X+1]-B_d[X]=B_{d-1}[X]$ (by Pascal's recurrence if you like) which gives that
$$
  \sum_{x=a}^{b-1}B_{d-1}[x]=B_d[b]-B_d[a]
  \qquad\text{for all $a\leq b$;}
$$
the formula can be taken to hold even if $a>b$ if one gives the proper meaning to summation over an interval in reverse order (similarly to integrals, but with some additional care for the bounds of the summation).
Now since $\deg(B_d[X])=d$ for $d\in\Bbb N$, these polynomials form a basis of $\Bbb Q[X]$ as a $\Bbb Q$-vector space. You can express your $P$ in terms of $B_0[X],\ldots,B_{d-1}[X]$, and the last one will occur with nonzero coefficient since $\deg(P[X])=d$. Now with the above formula
$$
  P[X]=\sum_{i=0}^{d-1}c_iB_i[X] \implies
  \sum_{k=n_0}^x P[k]= \sum_{i=0}^{d-1}c_i(B_{i+1}[x+1]-B_{i+1}[n_0])
  =Q[x]-C
$$
where $Q[X]=\sum_{i=0}^{d-1}c_iB_{i+1}[X+1]\in\Bbb Q[X]$ has degree $d$ and $C=\sum_{i=0}^{d-1}c_iB_{i+1}[n_0]\in\Bbb Z$ is a constant depending on the choice of $n_0$ (it will be $0$ for the choice $n_0=0$).
Note that even though $P$ has integral coefficients, in general $Q[X]$ will require rational coefficients. This can already be seen for $P[X]=X=B_1[X]$ where $Q[X]=B_2[X+1]=\frac{X^2+X}2$.
