Why is ∑_(k=1)^n k^m a polynomial with degree m+1 in n?

Colten Andrade

Colten Andrade

Answered question

2022-09-23

Why is k = 1 n k m a polynomial with degree m + 1 in n?

Answer & Explanation

Solomon Fernandez

Solomon Fernandez

Beginner2022-09-24Added 5 answers

Let V be the space of all polynomials f : N 0 F (where F is a field of characteristic zero). Define the forward difference operator Δ f ( n ) = f ( n + 1 ) f ( n ). It is not hard to see that the forward difference of a polynomial of degree d is a polynomial of degree d 1, hence defines a linear operator V d V d 1 where V d is the space of polynomials of degree at most d. Note that dim V d = d + 1.
We want to think of Δ as a discrete analogue of the derivative, so it is natural to define the corresponding discrete analogue of the integral ( f ) ( n ) = k = 0 n 1 f ( k ). But of course we need to prove that this actually sends polynomials to polynomials. Since ( Δ f ) ( n ) = f ( n ) f ( 0 ) (the "fundamental theorem of discrete calculus"), it suffices to show that the forward difference is surjective as a linear operator V d V d 1 .
But by the "fundamental theorem," the image of the integral is precisely the subspace of V d of polynomials such that f ( 0 ) = 0, so the forward difference and integral define an isomorphism between V d 1 and this subspace.
More explicitly, you can observe that Δ is upper triangular in the standard basis, work by induction, or use the Newton basis 1 , n , ( n 2 ) , ( n 3 ) , . . . for the space of polynomials. In this basis we have Δ ( n k ) = ( n k 1 ) , and now the result is really obvious.
The method of finite differences provides a fairly clean way to derive a formula for n m for fixed m. In fact, for any polynomial f ( n ) we have the "discrete Taylor formula"
f ( n ) = k 0 Δ k f ( 0 ) ( n k )
and it's easy to compute the numbers Δ k f ( 0 ) using a finite difference table and then to replace ( n k ) by ( n k + 1 ) . I wrote a blog post that explains this, but it's getting harder to find.
Thordiswl

Thordiswl

Beginner2022-09-25Added 2 answers

The formula just drops right out if we use the Euler Maclaurin Summation Formula.
For f ( x ) = x m we have
k = 0 n f ( k ) = 0 n f ( x )   d x + n m 2 + j = 0 B 2 j ( 2 j ) ! ( f ( 2 j 1 ) ( n ) f ( 2 j 1 ) ( 0 ) )
Where B j are the Bernoulli numbers and f ( j ) ( x ) is the j t h derivative of f .
Since f ( x ) is polynomial, the terms in
j = 0 B 2 j ( 2 j ) ! ( f ( 2 j 1 ) ( n ) f ( 2 j 1 ) ( 0 ) )
all are zero after a point 2 j 1 > m and thus we get the formula for
as a polynomial in n , with degree m + 1.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?