The Elements of the Calculus of Finite Difference
1. The fundamental theorem of summation theory.
Let f : Z → R be a function from the integers, Z, to the real num-
bers, R. We wish to find methods to evaluate sums of the form
b
X
f (k) = f (a) + f (a + 1) + f (a + 2) + · · · + f (b)
k=a
and in particular the special case
X n
f (k) = f (1) + f (2) + · · · + f (n).
k=1
Definition 1. Let f : Z → R. Then the diffenence, ∆f , of f is the
function
∆f (x) = f (x + 1) − f (x).
The operator ∆ is called the difference operator .
For example if f (x) = 3x + 2, then
∆f (x) = f (x + 1) − f (x) = (3(x + 1) + 2) − (3x + 2) = 3.
If f (x) = x2 , then
∆f (x) = f (x + 1) − f (x) = (x + 1)2 − x2 = 2x + 1
In the following table a, b, c, r are constants.
f (x) ∆f (x)
c 0
ax + b a
crx c(r − 1)rx
Problem 1. Verify these.
Theorem 1 (Fundamental Theorem of Summation Theory).
Let f : Z → R and let F be an anti-difference of f . That is ∆F = f .
Then for a, b ∈ Z with a < b
b
X
f (k) = F (b + 1) − F (a).
k=a
In particular
n
X
f (k) = F (n + 1) − F (1).
k=1
1
2
Proof. This uses the basic trick about telescoping sums:
b
X b
X
f (k) = (F (k + 1) − F (k))
k=a k=a
b
X b
X
= F (k + 1) − F (k)
k=a k=a
= F (a + 1) + F (a + 2) + · · · + F (b) + F (b + 1)
− F (a) + F (a + 1) + · · · + F (b − 1) + F (b)
= F (b + 1) − F (a)
as required.
Theorem 1 makes it interesting to find anti-differences of functions.
Here are some basic examples of functions f (x) defined on the integers
and their anti-differences (a, r and b are constants).
f (x) F (x)
x(x − 1)
ax + b a + bx
2
arx
arx
1−r
Problem 2. Verify these. (You just need to check F (x + 1) − F (x) =
f (x)).
arx
Problem 3 (Sum of finite geometric series). Use that as the
1−r
anti-difference of arx and Theorem 1 to show
a − arn+1 first − next
a + ar + ar2 + · · · + arn = = .
1−r 1 − ratio
2. Falling factorial powers and sums of powers.
For Theorem 1 to be useful we need more functions f (x) where we
know the anti-difference F (x). As a start we give
Definition 2. For natural number p define the falling factorial
power of x ∈ R as x0 = 1 and for p ≥ 1
xp = x(x − 1)(x − 2) · · · (x − (p − 1)).
(This product has p terms.)
3
For small values of p this becomes
x0 = 1
x1 = x
x2 = x(x − 1)
x3 = x(x − 1)(x − 2)
x4 = x(x − 1)(x − 2)(x − 3)
x5 = x(x − 1)(x − 2)(x − 3)(x − 4).
Proposition 1. If f (x) = xp where p is a natural number, then
∆f (x) = pxp−1 . That is
∆xp = pxp−1 .
Problem 4. Prove this.
d p
Remark 1. The formula should remind you of the c formula dx
x =
pxp−1 for derivatives.
Proposition 2. If f (x) = xp where p is a non-negative integer, then
1
F (x) = xp+1 is an anti-difference of f .
p+1
Problem 5. Prove this as a corollary of Proposition 1 by noting (by
replacing p by p+1), that ∆xp+1 = (p+1)xp and dividing by (p+1).
Problem 6. Show that if p ≥ 2 that 1p = 0. (For example 13 =
1(1 − 1)(1 − 2) = 0.)
Proposition 3. If p is a positive integer, then
n
X
p (n + 1)p+1
k = .
k=1
p+1
x
xp+1
Z
Remark 2. This should remind you of the formula tp dt = .
0 p+1
xp+1
Problem 7. Prove this. Hint: Let f (x) = xp . Then F (x) = is
p+1
an anti-difference of f (x) and thus by Theorem 1
X n
f (k) = F (n + 1) − F (1)
k=1
and use Problem 6 to see that F (1) = 0.
4
Proposition 4. The equalities
x = x1
x2 = x 2 + x1
x3 = x3 + 3x2 + x1
x4 = x4 + 6x3 + 7x2 + x1
x5 = x5 + 10x4 + 25x3 + 15x2 + x1
hold.
Problem 8. Verify the first three of these.
Problem 9. Find formulas for
Xn n
X
k2, k3.
k=1 k=1
Pn 2
Hint: Here is the idea for k . Using the last problem and Propo-
k=1
sition 3
Xn n
X
2
k = (k 2 + k 1 )
k=1 k=1
n
X n
X
2
= k + k1
k=1 k=1
3
(n + 1) (n + 1)2
= +
3 2
3
(n + 1) (n + 1)2
= + .
3 2
We can leave the answer like this, or expand and factor to get
n
X n(n + 1)(2n + 1)
k2 = .
k=1
6
Do similar calculations for nk=1 k 3 .
P
3. A couple of trigonometric sums.
For your convenience we recall some trig identities:
cos(α + β) = cos(α) cos(β) − sin(α) sin(β)
cos(α − β) = cos(α) cos(β) + sin(α) sin(β)
sin(α + β) = sin(α) cos(β) + cos(α) sin(β)
sin(α − β) = sin(α) cos(β) − cos(α) sin(β)
5
Problem 10. Let θ be a constant with sin( 2θ ) 6= 0. Use the identities
above to show
1 1 θ
sin θ x + − sin θ x − = 2 sin cos (θx)
2 2 2
and therefore
sin θ x − 21
F (x) = .
2 sin( 2θ )
is an anti-difference of
f (x) = cos(θx).
Proposition 5. If sin 2θ 6= 0, then
n
sin n + 21 θ − sin 2θ sin n + 21 θ
X 1
cos(kθ) = θ
= θ
− .
k=1
2 sin 2 2 sin 2 2
Problem 11. Use Problem 10 and Theorem 1 to prove this.
There is a similar formula for sums for the sine function.
Proposition 6. If sin( 2θ ) 6= 0, then
n
X cos( 2θ ) − cos((n + 21 )θ)
sin(kθ) = .
k=1
2 sin( 2θ )
Problem 12. Prove this.