Finite Differences
Chaang Tze Shen Tristan
January 22, 2022
1 Operators
We define ∆f (x) = f (x + 1) − f (x) as the first order finite difference. The symbol ∆ is
said to be the finite difference operator. Generally we define
∆r f (x) = ∆(∆r−1 f (x)) (1)
as the r-order finite difference. Also we define the following operators:
1. Ef (x) = f (x + 1)
2. If (x) = f (x)
Hence
E n f (x) = f (x + n)
I n f (x) = f (x)
∆=E−I
These operations will be very useful in proving some of the propositions below.
2 Finite Differences
Let’s start by finding a pattern in finite differences of various orders:
∆2 f (x) = f (x + 2) − 2f (x + 1) + f (x)
∆3 f (x) = f (x + 3) − 3f (x + 2) + 3f (x + 1) − f (x)
∆4 f (x) = f (x + 4) − 4f (x + 3) + 6f (x + 2) − 4f (x + 1) + f (x)
As such, we propose the following:
1
Proposition 1. Let r be a positive integer, then
n
k n
X
n
∆ f (x) = (−1) f (x + n − k) (2)
k
k=0
Proof. Since ∆ = E − I,
n
X n
∆n = (E − I)n = (−1)k E n−k
k
k=0
Let’s look from a different perspective from Proposition 1, where we write a function
in terms of finite differences instead.
f (x + 1) = ∆f (x) + f (x)
f (x + 2) = ∆2 f (x) + 2∆f (x) + f (x)
f (x + 3) = ∆3 f (x) + 3∆2 f (x) + 3∆f (x) + f (x)
Hence we propose the following:
Proposition 2. For any non-negative integer n,
n
X n
f (x + n) = ∆k f (x) (3)
k
k=0
Proof. Since ∆ = E − I,
n
X n
E n = (∆ + I)n = ∆k
k
k=0
Again, this directly brings us to
Proposition 3. For any non-negative integer n,
n
X n
f (n) = ∆k f (0)
k
k=0
Proof. Proposition 2. x = 0.
2
We take one step further: Writing f (1) + · · · + f (n) as a sum of finite differences.
Proposition 4. The sum of the first n terms of f (n) is
n
X n
f (1) + · · · + f (n) = ∆k−1 f (1) (4)
k
k=1
Proof. Since ∆ = E − I,
n
En − I (∆ + I)n − I X
n
E 0 + · · · + E n−1 = = = ∆k
E−I ∆ k+1
k=0
3 Polynomials
Next let’s see what happens if we apply finite differences to polynomials:
f (x) = an xn + . . .
∆f (x) = nan xn−1 + . . .
∆2 f (x) = n(n − 1)an xn−2 + . . .
Proposition 5. If f (x) is an n-degree polynomial with leading coefficient an , then
∆n f (x) = n! · an (5)
Proof. Induct in terms of the leading coefficient.
The following proposition may be very useful and it is very straightforward. We can
use it to deal with the degree of a certain polynomial.
Proposition 6. If f (x) is an n-degree polynomial , then
∆n+1 f (x) = 0 (6)
Proof. From proposition 5 we have ∆n+1 f (x) = n! · an − n! · an = 0.
From proposition 3, we can also generalise n to x, writing f (x) as a sum of what we
call finite difference polynomials (which is deep down just a binomial choose function!)
3
Proposition 7. For any n-degree polynomial,
n n
X
k x X x
f (x) = ∆ f (0) or simply ck
k k
k=0 k=0
Pn k x
Proof. f (x) − k=0 ∆ f (0) k has n + 1 roots, hence 0.
In fact, the expansion in proposition 7 is unique, and a polynomial is integer valued if
and only if ∀ci ∈ Z.
Example 1. Let m ≥ n be positive integers. Prove that
n
X m − k n
(−1)k = 1.
n k
k=0
Solution. Note that ∆n f (x) is constant if we let
m−x
f (x) =
n
n
X n
∴ LHS = (−1)k f (k)
k
k=0
= (−1)n ∆n f (0)
= (−1)n ∆n f (m − n)
n
X n
= (−1)k f (m − n + k)
k
k=0
= 1 + 0 + 0 + 0 + ··· = 1
Example 2. Let P (x) be a polynomial of degree n such that
−1
n+1
P (k) =
k
for k = 0, 1, . . . , n. Find the value of P (n + 1).
4
Solution. We start with
∆n+1 P (x) = 0
n+1
X n + 1
(−1)i P (n + 1 − i) = 0
i=0
i
n+1
X
P (n + 1) + (−1)i = 0
i=1
(
0 if n is even;
∴ P (n + 1) =
1 if n is odd.
4 Falling Factorials
Let’s introduce and define falling factorials.
k (n) = k(k − 1) . . . (k − n + 1).
Yes, it is precisely another definition of Pnk . Take the finite difference
∆k (n) = (k + 1)(n) − k (n)
= (k + 1)k (n−1) − k (n−1) (k − n + 1)
= n · k (n−1)
and we see it resembles the definition of the derivative! Hence the backward process is
analogous, it is called finite integration.
Example 3. Find the value of
14 + · · · + n4 .
Solution.
n
X n
X
4
k = (k (4) + 6k (3) + 7k (2) + k (1) )
k=0 k=0
n
X 1 (5) 3 (4) 7 (3) 1 (2)
= ∆ k + k + k + k
5 2 3 2
k=0
1 (5) 3 (4) 7 (3) 1 (2)
= (n + 1) + (n + 1) + (n + 1) + (n + 1) −0
5 2 3 2
1
= n(n + 1)(2n + 1)(3n2 + 3n − 1)
30
5
Example 4. Find the value of
23 + 53 + 83 + · · · + (3n + 2)3
Solution. We have f (n) = (3n + 2)3 . Then
n
X n
X
3
(3k + 2) = (27k (3) + 135k (2) + 117k (1) + 8)
k=0 k=1
n
X 27 (4) 117 (2)
= ∆ k + 45k (3) + k + 8k (1)
4 2
k=1
27 117
= (n + 1)(4) + 45(n + 1)(3) + (n + 1)(2) + 8(n + 1)(1)
4 2
1
= (n + 1)(3n + 4)(9n2 + 21n + 8)
4
Example 5. Find the value of
n
X n n+2
(−1)k k
k
k=0
Solution. We basically want (I − E)n xn+2 = (−1)n ∆n xn+2 evaluated at x = 0.
n + 2 n + 2
∆n (xn+2 ) = ∆n x(n+2) + x(n+1) + x(n) + · · ·
n+1 n
so the answer is
n n+2 (n + 2)(n + 1)n(3n + 1) (n + 2)!(3n + 1)n
(−1) n! = (−1)n n! · = (−1)n · .
n 24 24
