Colten Andrade

2022-09-23

Why is $\sum _{k=1}^{n}{k}^{m}$ a polynomial with degree $m+1$ in $n$?

Solomon Fernandez

Beginner2022-09-24Added 5 answers

Let $V$ be the space of all polynomials $f:{\mathbb{N}}_{\ge 0}\to F$ (where $F$ is a field of characteristic zero). Define the forward difference operator $\mathrm{\Delta}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}\to {V}_{d-1}$ where ${V}_{d}$ is the space of polynomials of degree at most $d$. Note that $\mathrm{dim}{V}_{d}=d+1$.

We want to think of $\mathrm{\Delta}$ as a discrete analogue of the derivative, so it is natural to define the corresponding discrete analogue of the integral $(\int f)(n)=\sum _{k=0}^{n-1}f(k)$. But of course we need to prove that this actually sends polynomials to polynomials. Since $(\int \mathrm{\Delta}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}\to {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 $\mathrm{\Delta}$ is upper triangular in the standard basis, work by induction, or use the Newton basis $1,n,{\textstyle (}\genfrac{}{}{0ex}{}{n}{2}{\textstyle )},{\textstyle (}\genfrac{}{}{0ex}{}{n}{3}{\textstyle )},...$ for the space of polynomials. In this basis we have $\mathrm{\Delta}{\textstyle (}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{n}{k-1}{\textstyle )}$, and now the result is really obvious.

The method of finite differences provides a fairly clean way to derive a formula for $\sum {n}^{m}$ for fixed $m$. In fact, for any polynomial $f(n)$ we have the "discrete Taylor formula"

$$f(n)=\sum _{k\ge 0}{\mathrm{\Delta}}^{k}f(0){\textstyle (}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}$$

and it's easy to compute the numbers ${\mathrm{\Delta}}^{k}f(0)$ using a finite difference table and then to replace $(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )$ by $(}\genfrac{}{}{0ex}{}{n}{k+1}{\textstyle )$. I wrote a blog post that explains this, but it's getting harder to find.

We want to think of $\mathrm{\Delta}$ as a discrete analogue of the derivative, so it is natural to define the corresponding discrete analogue of the integral $(\int f)(n)=\sum _{k=0}^{n-1}f(k)$. But of course we need to prove that this actually sends polynomials to polynomials. Since $(\int \mathrm{\Delta}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}\to {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 $\mathrm{\Delta}$ is upper triangular in the standard basis, work by induction, or use the Newton basis $1,n,{\textstyle (}\genfrac{}{}{0ex}{}{n}{2}{\textstyle )},{\textstyle (}\genfrac{}{}{0ex}{}{n}{3}{\textstyle )},...$ for the space of polynomials. In this basis we have $\mathrm{\Delta}{\textstyle (}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{n}{k-1}{\textstyle )}$, and now the result is really obvious.

The method of finite differences provides a fairly clean way to derive a formula for $\sum {n}^{m}$ for fixed $m$. In fact, for any polynomial $f(n)$ we have the "discrete Taylor formula"

$$f(n)=\sum _{k\ge 0}{\mathrm{\Delta}}^{k}f(0){\textstyle (}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}$$

and it's easy to compute the numbers ${\mathrm{\Delta}}^{k}f(0)$ using a finite difference table and then to replace $(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )$ by $(}\genfrac{}{}{0ex}{}{n}{k+1}{\textstyle )$. I wrote a blog post that explains this, but it's getting harder to find.

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

$$\sum _{k=0}^{n}f(k)={\int}_{0}^{n}f(x)\text{}\text{d}x+\frac{{n}^{m}}{2}+\sum _{j=0}^{\mathrm{\infty}}\frac{{B}_{2j}}{(2j)!}({f}^{(2j-1)}(n)-{f}^{(2j-1)}(0))$$

Where $B}_{j$ are the Bernoulli numbers and ${f}^{(j)}(x)$ is the $j}^{th$ derivative of $f$.

Since $f(x)$ is polynomial, the terms in

$$\sum _{j=0}^{\mathrm{\infty}}\frac{{B}_{2j}}{(2j)!}({f}^{(2j-1)}(n)-{f}^{(2j-1)}(0))$$

all are zero after a point $2j-1>m$ and thus we get the formula for

as a polynomial in $n$, with degree $m+1$.

For $f(x)={x}^{m}$ we have

$$\sum _{k=0}^{n}f(k)={\int}_{0}^{n}f(x)\text{}\text{d}x+\frac{{n}^{m}}{2}+\sum _{j=0}^{\mathrm{\infty}}\frac{{B}_{2j}}{(2j)!}({f}^{(2j-1)}(n)-{f}^{(2j-1)}(0))$$

Where $B}_{j$ are the Bernoulli numbers and ${f}^{(j)}(x)$ is the $j}^{th$ derivative of $f$.

Since $f(x)$ is polynomial, the terms in

$$\sum _{j=0}^{\mathrm{\infty}}\frac{{B}_{2j}}{(2j)!}({f}^{(2j-1)}(n)-{f}^{(2j-1)}(0))$$

all are zero after a point $2j-1>m$ and thus we get the formula for

as a polynomial in $n$, with degree $m+1$.

Describe all solutions of Ax=0 in parametric vector form, where A is row equivalent to the given matrix

$$\left[\begin{array}{cccc}1& 3& 0& -4\\ 2& 6& 0& -8\end{array}\right]$$ Find, correct to the nearest degree, the three angles of the triangle with the given vertices

A(1, 0, -1), B(3, -2, 0), C(1, 3, 3)Whether f is a function from Z to R if

?

a) $f\left(n\right)=\pm n$.

b) $f\left(n\right)=\sqrt{{n}^{2}+1}$.

c) $f\left(n\right)=\frac{1}{{n}^{2}-4}$.How to write the expression ${6}^{\frac{3}{2}}$ in radical form?

How to evaluate $\mathrm{sin}\left(\frac{-5\pi}{4}\right)$?

What is the derivative of ${\mathrm{cot}}^{2}x$ ?

How to verify the identity: $\frac{\mathrm{cos}\left(x\right)-\mathrm{cos}\left(y\right)}{\mathrm{sin}\left(x\right)+\mathrm{sin}\left(y\right)}+\frac{\mathrm{sin}\left(x\right)-\mathrm{sin}\left(y\right)}{\mathrm{cos}\left(x\right)+\mathrm{cos}\left(y\right)}=0$?

Find $\mathrm{tan}\left(22.{5}^{\circ}\right)$ using the half-angle formula.

How to find the exact values of $\mathrm{cos}22.5\xb0$ using the half-angle formula?

How to express the complex number in trigonometric form: 5-5i?

The solution set of $\mathrm{tan}\theta =3\mathrm{cot}\theta $ is

How to find the angle between the vector and $x-$axis?

Find the probability of getting 5 Mondays in the month of february in a leap year.

How to find the inflection points for the given function $f\left(x\right)={x}^{3}-3{x}^{2}+6x$?

How do I find the value of sec(3pi/4)?