Question about a polynomial's degree How can we show that if $p(x)$ is a polynomial of degree $d-1$, then
$$\sum_{k=n_0}^n p(k)$$
is a polynomial in $n$ of degree $d$?
 A: It suffices to prove that $\sum_{k=0}^{n}{p(k)}$ is a polynomial in $n$ of degree $d$, since $\sum_{k=n_0}^{n}{p(k)}$ differs from $\sum_{k=0}^{n}{p(k)}$ by a constant.
Note that $$\sum_{k=0}^{n}{\binom{k}{d}}=\binom{n+1}{d+1}$$ 
This can be proven by induction on $n$, or by double counting the number of ways to choose $d+1$ numbers from $\{0, 1, \ldots, n \}$.
Now we induct on $d$: 
The base case $d=1$ is clearly true. Suppose that the statement holds for $d=i$, then for a polynomial $p(x)$ with degree $(i+1)-1=i$, we may write $p(x)=a\binom{x}{i}+q(x)$ where $a$ is $i!$ multiplied by the leading coefficient of $p(x)$, and $q(x)$ is a polynomial with degree $i-1$. Then 
$$\sum_{k=0}^{n}{p(k)}=\sum_{k=0}^{n}{a\binom{k}{i}}+\sum_{k=0}^{n}{q(k)}=a\binom{n+1}{i+1}+\sum_{k=0}^{n}{q(k)}$$
Note that $a\binom{n+1}{i+1}$ is a polynomial in $n$ of degree $i+1$, and by the induction hypothesis $\sum_{k=0}^{n}{q(k)}$ is a polynomial in $n$ of degree $i$.
Therefore $\sum_{k=0}^{n}{p(k)}$ is indeed a polynomial in $n$ of degree $i+1$, and we are done by induction.
