Colten Andrade
2022-09-23
Answered

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

You can still ask an expert for help

Solomon Fernandez

Answered 2022-09-24
Author has **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

Answered 2022-09-25
Author has **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$.

asked 2021-09-08

A restaurant offers a $12 dinner special with seven appetizer options, 12 choices for an entree, and 6 choices for a dessert. How many different meals are available when you select an appetizer, an entree,and a dessert?

asked 2021-09-09

In a fuel economy study, each of 3 race cars is tested using 5 different brands of gasoline at 7 test sites located in different regions of the country. If 2 drivers are used in the study, and test runs are made once under each distinct set of conditions, how many test runs are needed?

asked 2021-02-25

Can two events with nonzero
probabilities be both independent and
mutually exclusive? Explain your
reasoning.

asked 2022-06-15

Assuming seven standard dice are rolled, what is the probability their sum equals 17? Show a general approach to solving this problem analytically, using conditional probability, combinatorics, etc

asked 2021-05-05

If John, Trey, and Miles want to know how’ |
many two-letter secret codes there are that dont

asked 2021-11-07

What is the probability that Bo, Colleen, Jeff, and Rohini win the first, second, third, and fourth prizes, respectively, in a drawing if 50 people enter a contest and a) no one can win more than one prize. b) winning more than one prize is allowed.

asked 2022-11-21

The supreme court has given a 6 to 3 decisions upholding a lower court; the number of ways it can give a majority decision reversing the lower court is:

Actually in this question, how to get the statement what does the statement "6 to 3 decisions upholding a lower court" mean and then what we have to find ?

Actually in this question, how to get the statement what does the statement "6 to 3 decisions upholding a lower court" mean and then what we have to find ?