Proving Polynomial Expression: 1^k+2^k+...+n^k as a Degree-k+1 Polynomial

[Icebreaker]

"Prove that

$$1^k+2^k+...+n^k$$

can be written as a polynomial in $$n$$ of degree at most $$k+1$$."

Isn't this kinda trivial? I mean I know the "book" solution is to prove by induction, etc, but assuming that I have the above expression, I can prove or disprove it, depending on how I interpret the question.

If it means that it can be written in the above conditions AND NOTHING ELSE, I can easily produce a counterexample:

$$1+2+3 = 3^3 - 7\times3$$

If it means that it can be written in the above conditions, but does not prohibit the existence of other solutions, then it's trivial, because the above expression can be written as

$$an^{k+1}$$ for some real number $$a$$

 

[shmoe]

If it means that it can be written in the above conditions AND NOTHING ELSE, I can easily produce a counterexample:

$$1+2+3 = 3^3 - 7\times3$$

It doesn't mean "and nothing else", it's already written in a form that you wouldn't call a polynomial.

If it means that it can be written in the above conditions, but does not prohibit the existence of other solutions, then it's trivial, because the above expression can be written as

$$an^{k+1}$$ for some real number $$a$$

No choice of a here will hold for all n. Your polynomial is supposed to equal that expression for all values of n.

 

[Icebreaker]

True, no choice of a will hold for every n, but there exists one for every n.

 

[shmoe]

True, no choice of a will hold for every n, but there exists one for every n.

It's not a polynomial if the coefficients aren't constant. Your a will depend on n in some unspecified way, and you haven't solved the problem.

 

[Icebreaker]

No easy way out then. Damn.