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.