Lesson 5

Hence, once we know that \(S_{k}(n)\) is a polynomial of degree at most \(k+1\), finitely many values are enough to certify the answer. Suppose a polynomial \(P(n)\) of degree at most \(k+1\) agrees with \(S_{k}(n)\) for \(n=0,1,\dotsc,k+1\). Consider \[Q(n)=P(n)-P(n-1)-n^{k}.\] The polynomial \(Q\) has degree at most \(k\): the leading terms of \(P(n)\) and \(P(n-1)\) cancel. Also, \(Q(1)=Q(2)=\dotsb=Q(k+1)=0\). Thus \(Q\) has more roots than its degree, so \(Q\) is identically zero. Since \(P(0)=S_{k}(0)=0\), it follows by induction that \(P(n)=S_{k}(n)\) for every \(n \in \mathbb{Z}_{\ge 0}\).