Induction on the degree of a Polynomial. Let $p(k)$ be a polynomial of degree $d$. Prove $q(n) = \sum_{k=1}^np(k)$ is a polynomial of degree $d + 1$ and that $q(0) = 0$.
First I'll prove that it is equivalent to proving degree of $f_d(n)= 1^d + 2^d + ... n^d$ is $d+1$. Also, let degree of a polynomial be given by $Deg[P]$
We know if $m$ and $n$ are two polynomials with degree $k_1$ and $k_2, \  (k_1 \neq k_2)$ then degree of the polynomial $m+n$ is $max(k_1,k_2)$. $(^*)$
Now, we know degree $f_d < d+2$ (see blockquote below for proof!)

Here, I'll prove $Deg[f_d] < d+2$. If there is a polynomial $r(x) = \sum_{i=0}^{d+2}a_ix^i$ with $Deg[r] = d +2$, then as we know $f_d(n) < n^{d+1}$, but clearly for large $n$, $r(x) > n^{d+1}$.

If $p(k) = \sum_{i=0}^da_ik^i$, then $q(n) = \sum_{k=1}^np(k) = \sum_{i=0}^da_if_i(n)$, and for all $l<d, \ Deg[f_l] < d+1$, so $q$ will have degree $d+1$ iff $Deg[f_d] = d+1$.
Also, I initially had trouble thinking how to define $q$ for non-natural numbers, but here's how: If $q(n) = w(n) \ \forall n \in N$ , then $z(n) = q(n) - w(n)$ has infinite roots and hence is identically zero and so $q(n)$ is always equal to the polynomial $w(n)$ $(^@)$
Now, I'll start the actual induction, I'll use strong induction.The base case, $d=0$ is trivial. Assume for all $i \le d, \ \  Deg[f_i] = i+1$.
We need to prove $Deg[f_{d+1}] = d+2 \iff Deg[f_{d+1} - f_d] = d+2$
$\iff \sum_{i=0}^{n-1}(n-i)^{d+1} - \sum_{i=0}^{n-1}(n-i)^{d} = \sum_{i=0}^{n-1}(n-i)^d(n-i-1)$ has degree $d+2$.
But each $(n-i)^d(n-i-1)$ is like $n^{d+1}$ + blah , where blah has degree $< d+1$
Adding all, we'll have something of sort $n^{d+1} \cdot n$ + blahblah $= n^{d+2}$ + something with degree $< d+1$ which clearly has degree $d+2$ from $(^*)$
So I have just one question:
Is my proof of the first part correct? (Mainly the blockquote and the induction using blah) I know it is frowned upon to ask these questions but It's just like algebra and combi are my weakest subjects, and I think my proof is much easier and very different than the one given in Mikolas Bona's book, and that is usually a tell tale sign for wrong solutions. Trust me, I tried my best to try to find an error but even after reading almost 5-6 times, I'm still not convinced.
On a sidenote, this took insanely long to type :( why am I so trash at latex!
Thanks!
 A: *

*For the block quote, but you might want to add details to demonstrate why those inequalities are true. (Depending on how strict the grader is, this part might be considered writing things without proof and hoping they are true, or hand wavy.)


*I don't know why you care about defining $q(n)$ for non-natural numbers. I blame the problem statement, where it should say that "$q(n)$ can be extended to a polynomial of degree ... ". instead. (That is most probably what they intended, or there was a transcription error.)


*You will need to write out the "blah" part carefully. In particular, you must ensure that the summation doesn't increase the degree too much. This is not obvious. In particular, I take issue with this part.

Adding all, we'll have something of sort $n^{d+1} \cdot n$ + blahblah $= n^{d+2}$ + something with degree $< d+1$ which clearly has degree $d+2$ from $(^*)$

How do you know that the summation doesn't give you $n^{d+3}$ or $n^{d+1}$, or even $n^{d+0.5}$ which is no longer a polynomial?    Arguably, this is the entire crux of the problem, which you compeltely glossed over. At worst, you are assuming the statement in order to prove the statement.
Hence, this is a $0^+$ solution to me.


*Note that the initial lemma likely should be "degree of $m+n$ is at most $\max(k_1 , k_2 ) $, with equality when $k_1 \neq k_2$". This makes it easier to apply it subsequently.


As an aside, using the method of differences, the proof is a one-liner (depending on how many theorems you're willing to assume).

 1. The first difference $D_1 (q)$ is $p(k)$, which is a polynomial of degree $d$, hence $q(n)$ is a polynomial of degree $d+1$.
 2. Verify that the first difference is the polynomial $ p(n+1)$, so $p(1) = D_1 (q) (0) = q(1) - q(0) = p(1) - q(0) \Rightarrow q(0) = 0 $.

