Logo
Published on

Discrete calculus and sums of powers

Authors
  • avatar
    Name
    Vu Hung
    Twitter

Problem Statement

∇\nabla is the backward difference operator, defined as ∇f(n)=f(n)−f(n−1)\nabla f(n)=f(n)-f(n-1) for discrete functions f(n)f(n). In this problem, you will explore the properties of the backward difference operator and its applications to sums of powers.

For example, The first order of ∇\nabla is

∇(n2)=n2−(n−1)2=2n−1\nabla(n^2)=n^2-(n-1)^2=2n-1.

The second order of ∇\nabla is ∇2f(n)=∇(∇f(n))=∇(f(n)−f(n−1))=f(n)−2f(n−1)+f(n−2)\nabla^2 f(n)=\nabla(\nabla f(n))=\nabla(f(n)-f(n-1))=f(n)-2f(n-1)+f(n-2) and the third order of ∇\nabla is ∇3f(n)=∇(∇2f(n))=∇(f(n)−2f(n−1)+f(n−2))=f(n)−3f(n−1)+3f(n−2)−f(n−3)\nabla^3 f(n)=\nabla(\nabla^2 f(n))=\nabla(f(n)-2f(n-1)+f(n-2))=f(n)-3f(n-1)+3f(n-2)-f(n-3).

In this problem, we use the ∇\nabla operator to derive formulas for sums of powers.

  • Show n3−(n−1)3=3n2−3n+1n^3-(n-1)^3=3n^2-3n+1.
  • Sum this identity from 11 to NN to derive
∑n=1Nn2=N(N+1)(2N+1)6.\sum_{n=1}^N n^2=\frac{N(N+1)(2N+1)}{6}.
  • Evaluate ∇3(n3)\nabla^3(n^3)

% where ∇f(n)=f(n)−f(n−1)\nabla f(n)=f(n)-f(n-1) is the backward difference operator % ∇3=∇∘∇∘∇\nabla^3 = \nabla \circ \nabla \circ \nabla is the third-order backward difference operator, % e.g. ∇3(n3)=n3−3(n−1)3+3(n−2)2−(n−3)3\nabla^3(n^3) = n^3 - 3(n-1)^3 + 3(n-2)^2 - (n-3)^3.

  • State the leading term of ∑n=1Nnk\sum_{n=1}^N n^k.

Hints

Use telescoping on the left and known formulas for ∑n\sum n.

Solutions

Expansion gives part (i). Summing:

N3=3∑n=1Nn2−3∑n=1Nn+N,N^3=3\sum_{n=1}^N n^2-3\sum_{n=1}^N n+N,

which simplifies to

∑n=1Nn2=N(N+1)(2N+1)6.\sum_{n=1}^N n^2=\frac{N(N+1)(2N+1)}{6}.

Also ∇3(n3)=6\nabla^3(n^3)=6. In general,

∑n=1Nnk=1k+1Nk+1+(lower powers of N).\sum_{n=1}^N n^k=\frac{1}{k+1}N^{k+1}+\text{(lower powers of }N\text{)}.

Further Readings

Connect with me