Questions about induction and Big O

Question

Statement:

For any $k \in \mathbb N$, the value of $\displaystyle{\sum_{i=1}^ni^k}$ is a polynomial in $n$ with the leading term $\displaystyle{\frac{1}{k+1}n^{k+1}}$ and next term $\displaystyle{\frac 12n^k}$.

Proof:

By remark $(--)$, there's a polynomial $g$ s.t. $\displaystyle{k!\binom ik = i^k - \binom k2i^{k-1} + g(i)}$ with $g$ of degree at most $k - 2$ meaning $i^k = \displaystyle{k!\binom ik + \binom k2i^{k-1} - g(i)}$.

Let $k = 1$. The sum of first $n$ naturals is $\displaystyle{\sum_{i=1}^ni = \frac 12n^2 + \frac 12n}$ and so the claim holds for base case.

For $k > 1$, we have $\displaystyle{\sum_{i=1}^ni^k = k!\sum_{i=1}^k\binom ik + \binom k2\sum_{i=1}^ki^{k-1} - \sum_{i=1}^kg(i)}$.

Now, $\displaystyle{ k!\sum_{i=1}^k\binom ik = k!\binom{n+1}{k+1}}$ by Hockey Stick identity and $\displaystyle{\binom k2\sum_{i=1}^ki^{k-1} = \binom k2\frac1kn^k + O(n^{k-1})}$ by induction hypothesis. Further note, $\displaystyle{\binom{n+1}{k+1} = \frac{n+1}{k+1}\binom nk}$.

Thus we have $\displaystyle{\sum_{i=1}^ni^k = \frac{1}{k+1}n^{k+1} + \frac 12n^k + O(n^{k-1})}$.

My questions:

1. At the beginning of the proof $g$ is said to be $O(n^{k-2})$, but in conclusion of the proof $g$ is $O(n^{k-1})$. Is it by hypothesis? What I mean is if $g$ is of degree $k - 2$, then by hypothesis $g$ is $\displaystyle{\frac{1}{(k - 2)+1}n^{(k-2)+1} + O(n^{k-3}) = \frac{1}{k - 1}n^{k-1} + O(n^{k-3}) = O(n^{k-1})}$. Does that make sense? If not, what's the reason for this?

2. I am not sure we showed the step from $k$ to $k+1$ holds in the proof. Is it done implicitly? Can someone, please, point out where in the proof the step $k \implies k+1$ happens? Thanks.

Answer 1

If $g$ is a polynomial of degree at most $k-2$, then $|g(n)| \le cn^{k-2}$ for some $c$ for large enough $n > n(c)$, so $g(n) = O(n^{k-2})$ and

$\begin{array}\\ |\sum_{i=1}^n g(i)| &\le |\sum_{i=1}^{n(c)} g(i)|+|\sum_{i=n(c)+1}^n g(i)|\\ &\le n(c)\max_{i=1}^{n(c)}|g(i)|+|\sum_{i=n(c)+1}^n ci^{k-2}|\\ &\le n(c)\max_{i=1}^{n(c)}|g(i)|+|\sum_{i=n(c)+1}^n cn^{k-2}|\\ &\le n(c)\max_{i=1}^{n(c)}|g(i)|+cn^{k-1}\\ \text{so}\\ \dfrac{|\sum_{i=1}^n g(i)|}{n^{k-1}} &\le \dfrac{n(c)\max_{i=1}^{n(c)}|g(i)|+cn^{k-1}}{n^{k-1}}\\ &= c+\dfrac{n(c)\max_{i=1}^{n(c)}|g(i)|}{n^{k-1}}\\ &\le c+1\\ \end{array} $

for $\dfrac{n(c)\max_{i=1}^{n(c)}|g(i)|}{n^{k-1}} \lt 1$ or $n \ge (n(c)\max_{i=1}^{n(c)}|g(i)|)^{1/(k-1)} $.

Therefore $\sum_{i=1}^n g(i) =O(n^{k-1})$.