0

I have trouble understanding the solution in the book regarding using strong induction to prove the following questions:

Questions: Let p(k) be a polynomial of degree d. Prove that q(n) = $\sum_{k=1}^n p(k)$ is a polynomial of degree d+1. Prove that this polynomial q satisfies q(0) = 0.

The solutions can be found here: https://books.google.com.hk/books?id=0ZxIDQAAQBAJ&pg=PA29&dq=A+Walk+Through+Combinatorics+We+prove+the+statement+by+strong+induction+on+d.++If+d%3D0,+then+p+is+a+constant+polynomial,+say+p%3Dc.++Then&hl=en&sa=X&ved=0ahUKEwijxZilzunkAhXLfXAKHbaJD5QQ6AEIKjAA#v=onepage&q=A%20Walk%20Through%20Combinatorics%20We%20prove%20the%20statement%20by%20strong%20induction%20on%20d.%20%20If%20d%3D0%2C%20then%20p%20is%20a%20constant%20polynomial%2C%20say%20p%3Dc.%20%20Then&f=false

After reading the solution, I only understand the first paragraph of the solution, anything after that I'm basically lost. Can anyone further elaborate or provide an alternative explanation?

Thanks.

Gary Liao
  • 1

1 Answers1

0

Let $$p(k)=a_0k^d+a_1k^{d-1}+ ... +a_d.$$

Then $q(n)$ is $a_0\sum _1^n k^d+a_1\sum _1^n k^{d-1}+...$ and you are therefore required to prove that each of the sums $\sum _1^n k^e$ is a polynomial in $n$ of degree $e+1$.