Calculus of Finite Differences Part-1

Achyut Bharadwaj, Saee Patil, Valentio Iverson, Danny Li

August 2021

calculus, finite difference, sequences, patterns, polynomials, chain rule

Acknowledgements #

This work was carried out as part of a research project at PROMYS-2021. I am a grateful recipient of the Mehta Fellowship to the PROMYS programs in 2021 and 2022.

Preliminary Definitions #

Finding Patterns #

(1)

1,4,7,10,\cdots\;\;?

Here’s a harder one:

(2)

3,4,6,9,13,\cdots\;\;?

Notations #

(3)

\Delta\left(f\right)(x)=f(x+1)-f(x)

(4)

\Delta^{n+1}(f)=\Delta\left(\Delta^n(f)\right)

What is $\Delta\left(f\right)$ when $f$ is $1,4,7,10,\cdots$ ?

What is $\Delta\left(f\right)$ when $f$ is $3,4,6,9,13\cdots$ ?

What is $\Delta^2(f)$ when $f$ is $3,4,6,9,13\cdots$ ?

Some Results #

$\Delta\left(f\right)$ is a polynomial iff $f$ is a polynomial.

(5)

\Delta^n(f)=c\Rightarrow \Delta^{n+1}(f)=0

Let

(6)

f(x)=a_mx^m+a_{m-1}x^{m-1}+\cdots+a_1x+a_0,a_m\neq0

The least

n

such that

\Delta^n(f)=0

m+1

$\Delta^{-1}$ #

We define $\Delta^{-1}(f(x))$ as a function $g(x)$ such that $\Delta\left(g(x)\right) = f(x)$ .

Patterns again! #

(7)

1^2 + 2^2 + 3^2 + \cdots + (n-1)^2 = ~?

What about

(8)

1^3 + 2^3 + \cdots + (n-1)^3 = ~?

Can you find

(9)

\sum_{i=0}^{n-1} i^k

recursively?

Generalizing #

Observe that

(10)

\sum_{i=0}^{n-1}(i+1)^k - \sum_{i=0}^{n-1}i^k = n^k

So,

(11)

\sum_{i=0}^{n-1}(i+1)^k - i^k = n^k

The above becomes:

(12)

\sum_{i=0}^{n-1}\sum_{j=1}^{k}\binom{k}{j}i^{k-j} = \sum_{i=0}^{n-1}(ki^{k-1} + \sum_{j=2}^{k}\binom{k}{j}i^{k-j}) = n^k

using the binomial theorem.

So, we have

(13)

n^k-\sum_{i=0}^{n-1}(\sum_{j=2}^{k}\binom{k}{j}i^{k-j}) = k\sum_{i=0}^{n-1}i^{k}

by rearranging the above.

Hence,

(14)

\sum_{i=0}^{n-1}i^k = \frac{n^k - \sum_{i=0}^{n-1}(\sum_{j=2}^{k}(\binom{k}{j}i^{k-j}))}{k}

Calculus vs Finite Differences #

Addition and multiplication under a finite difference #

(15)

\Delta\left(f(x)+g(x)\right) = \Delta\left(f(x)\right)+\Delta\left(g(x)\right)

(16)

\begin{aligned}\Delta\left(f(x)+g(x)\right) &= (f(x+1)+g(x+1)) - (f(x)+g(x)) \\ &= (f(x+1)-f(x)) + g(x+1) - g(x) \\ &= \Delta\left(f(x)\right) + \Delta\left(g(x)\right)\end{aligned}

Multiplication of finite difference #

We now try to find a generic formula for the product of two functions under a finite difference.

(17)

\Delta\left(f(x)\cdot g(x)\right) = f(x+1)\Delta\left(g(x)\right) + g(x)\Delta\left(f(x)\right)

(18)

\Delta\left(f(x)\cdot g(x)\right) = f(x+1)g(x+1) - f(x)g(x)

We add and subtract

g(x)f(x+1)

in the above to get:

(19)

\begin{aligned} \Delta\left(f\cdot g\right) &= f(x+1)g(x+1) - f(x)g(x) + f(x+1)g(x) - f(x+1)g(x) \\ &= f(x+1)(g(x+1) - g(x)) + g(x)(f(x+1)-f(x)) \\ &= f(x+1)\Delta\left(g(x)\right) + g(x)\Delta\left(f(x)\right) \end{aligned}

Division under a finite difference #

Before trying to find a formula for division, we try to find one for the multiplicative inverse, i.e. finding $\Delta\left(\frac{1}{f(x)}\right)$ in terms of $f(x)$

(20)

\Delta\left(\frac{1}{f(x)}\right) = \frac{1}{f(x+1)} - \frac{1}{f(x)} = \frac{f(x)-f(x+1)}{f(x+1)f(x)} = -\frac{\Delta\left(f(x)\right)}{f(x+1)f(x)}

Now,

(21)

\Delta\left(\frac{f(x)}{g(x)}\right) = \Delta\left(f(x)\cdot\frac{1}{g(x)}\right) = f(x+1)\Delta\left(\frac{1}{g(x)}\right) + \frac{1}{g(x)}\Delta\left(f(x)\right)

by the product formula. The above can be written as:

(22)

-f(x+1)\frac{\Delta\left(g(x)\right)}{g(x+1)g(x)} + \frac{\Delta\left(f(x)\right)}{g(x)} = \frac{g(x+1)\Delta\left(f(x)\right)-f(x+1)\Delta\left(g(x)\right)}{g(x+1)g(x)}

Chain Rule #

Evaluate $\Delta\left(f(x)\right)$ when $f(x)=(2x)^2$

$(2x)^2 = 4x^2$ . Now, $\Delta\left(4x^2\right) = 4\Delta\left(x^2\right) = 4(2x+1) = 8x+4$ .

We compare this with the calculus chain rule. Is it possible to let $u=2x$ , find $\Delta\left(f(u)\right)$ , and multiply it by $\Delta u$ to get the result as we do in calculus?

(23)

f(u)=u^2 \implies \Delta f(u) = 2u + 1 = 4x + 1

Also,

\Delta u = 2

. So,

(24)

\Delta f(u)\cdot \Delta u = (4x+1)\times2 = 8x + 2 \neq 8x+4

We explore why it does not work in the next few slides.

We think of the function $\Delta$ as finding the slope of a curve between two integral points.

So, we can conclude that

(25)

\Delta\left((f)(x)\right) = \frac{\Delta\left(f(x)\right)}{\Delta x}

We need

(26)

\frac{\Delta f}{\Delta g}\cdot\frac{\Delta g}{\Delta x} = f(g(x))\Delta\left(g(x)\right)

for the chain rule to work.

We know that

(27)

\frac{\Delta g(x)}{\Delta x} = \Delta g(x)

from the graph in Fig-1. Hence, we need

(28)

\frac{\Delta f(x)}{\Delta g(x)} = f(g(x))

for the chain rule to work. This however does not hold true for every

f(x),g(x)

as we saw in the example.

In calculus however, the difference is not finite. Hence, the above holds.

Some fun with $\Delta^{-1}$ #

Find $\Delta^{-1}(x + 1)$ . Can you find $\Delta^{-1}(f(x)+g(x))$ in terms of $f(x),g(x)$ ?

We know

(29)

\Delta^{-1}(2x+1) = x^2+c

. Also,

(30)

\Delta^{-1}x = \frac{x^2-x}{2}+c

So, one can guess that

(31)

\Delta^{-1}(2x+1) = x^2 - \frac{x^2-x}{2} = \frac{x^2 + x}{2}+c

for some constant

c

. Indeed, we can check to see that this is true! Notice that this is the same as

(32)

\Delta^{-1}(x) + \Delta^{-1}(1)

This leads to a proposition.

Addition under $\Delta^{-1}$ #

(33)

\Delta^{-1}(f+g) = \Delta^{-1}(f)+\Delta^{-1}(g)

for all

f,g

whose differences are defined.

We know that

(34)

\Delta\left(f'+g'\right) = \Delta\left(f'\right)+\Delta\left(g'\right)

Now,

(35)

\Delta^{-1}(\Delta\left(f'+g'\right)) = f'+g'

Hence,

(36)

\Delta^{-1}(\Delta\left(f'\right)+\Delta\left(g'\right))=f'+g'

Also,

(37)

\Delta^{-1}(\Delta\left(f'\right)) + \Delta^{-1}(\Delta\left(g'\right)) = f' + g'

Equating the LHS of the above two equations, we get:

(38)

\Delta^{-1}(\Delta\left(f'\right)+\Delta\left(g'\right))=\Delta^{-1}(\Delta\left(f'\right)) + \Delta^{-1}(\Delta\left(g'\right))

We let

(39)

\Delta\left(f'\right) = f, \Delta\left(g'\right) = g

Thus,

(40)

\Delta^{-1}(f+g) = \Delta^{-1}(f)+\Delta^{-1}(g)

for all

f,g

given that

f’,g’

exist. That is,

f

and

g

must have defined differences.

Generalizing #

A motivating question #

We are interested in the following question.

Can we find a polynomial that fits a certain given data?

Let us consider the following example. Can we find a quadratic polynomial $f$ such that

(41)

f(0) = 1, f(1) = 0, f(2) = 5, f(3) = -1~?

A motivating question indeed, and the answer is no. Suppose there exists such quadratic polynomial $f$ , then

(42)

\Delta^3 f(x) = 0, \forall x \in \mathbb{R}

However, we can check that

(43)

\Delta^3 f(0) = f(3) - 3f(2) + 3f(1) - f(0) = -17

Consider a variant of the question before: Can we find a cubic polynomial $f$ such that

(44)

f(0) = 1, f(1) = 0, f(2) = 5, f(3) = -1~?

The answer is yes! The polynomial

(45)

-\frac{17}{6}x^3+\frac{23}{2}x^2 - \frac{29}{3}x + 1

works. But how do we find this polynomial?

Since

(46)

\Delta\left(\Delta^2(f(x))\right) = -17

(47)

\Delta^2(f(x)) = -17x + c

for some constant

c

. When

x=0

(48)

\Delta^2(f(x)) = 6

Hence,

c=6

. Similarly,

(49)

\Delta^2(f(x)) = -17x+6 \implies \Delta\left(f(x)\right) = -\frac{17}{2}x^2 + \frac{29}{2}x + c'

for some constant

c’

. When

x=0

\Delta\left(f(x)\right) = -1

. Hence,

c’ = -1

. We could check that

(50)

\Delta\left(f(x)\right) = \frac{17}{2}x^2 + \frac{29}{12}x - 1

, which implies

(51)

f(x) = -\frac{17}{6}x^3 + \frac{23}{2}x^2 - \frac{29}{3}x + c''

When

x=0

f(x) = 1

. Hence,

c’’=1

. Thus, the cubic polynomial that fits the given data is

(52)

-\frac{17}{6}x^3+\frac{23}{2}x^2 - \frac{29}{3}x + 1

Can we generalize this? Therefore, we began to ask the following interesting question:

Given the values of $f(0), f(1), \dots, f(n)$ , can we find a polynomial $f$ of degree not greater than $n$ that fits this data? Is this polynomial unique?

And the answer is yes to both questions.

Finding a polynomial that passes through $n$ points #

Claim. For any $n,k, i \le k$ , we have

(53)

\Delta^i \binom{n + k}{k} = \binom{n + k}{k - i}

We will prove this by induction on $i$ . Indeed, this is true for $i = 1$ , since

(54)

\Delta \binom{n + k}{k} = \binom{n +k + 1}{k} - \binom{n + k}{k} = \binom{n + k}{k - 1}

Now, fix

n,k

. Suppose this result is true for

i = \ell < k

, Then we will prove that this is true for

i = \ell + 1

Indeed,

(55)

\begin{aligned} \Delta^{\ell + 1} \binom{n + k}{k} &= \Delta \left( \Delta^{\ell} \binom{n + k}{k} \right) \\ &= \Delta \binom{n + k}{k - \ell} \\ &= \binom{n + 1 + k}{ k - \ell} - \binom{n + k}{k - \ell} \\ &= \binom{n + k}{k - \ell - 1} \end{aligned}

which proves our assertion.

Every polynomial $P(x)$ can be uniquely represented as

(56)

\sum_{k} a_k \binom{n + k}{k}

for reals

a_k

Using this fact, note that if $P(x) \not= 0$ , then

(57)

\begin{aligned} \Delta^{-1}(P(x)) &= \sum_k a_k \Delta^{-1} \left( \binom{n + k}{k} \right) = \sum_k a_k \binom{n + k}{k + 1}\end{aligned}

The previous argument proves the existence of such a polynomial passing through $f(0), f(1), f(2), \dots, f(n)$ , ensuring the degree is not greater than $n$ . In fact, we claim an even more generalized result.

Let $x_1, x_2, \dots, x_n$ be $n$ distinct real values and $y_1, y_2, \dots, y_n$ be $n$ real numbers. Then there exists a unique polynomial $f \in \mathbb{R}[x]$ of degree less than $n$ such that $f(x_i) = y_i$ for $1 \le i \le n$ .

Proof #

Proof. We’ll first prove that there exists such polynomial. Consider the polynomial

(58)

f(x) = \sum_{i = 1}^n y_i \cdot \prod_{i \not= j} \frac{x - x_j}{x_i - x_j}

Now, check that

f(x_i) = y_i

for every

1 \le i \le n

, and we are done. Finally, we will prove uniqueness. Indeed, if there exists two working polynomials

Q,R

such that

(59)

Q(x_i) = R(x_i) = y_i

for

1 \le i \le n

. Then, either

Q - R = 0

, or

\text{deg} (Q - R) < n

. However, if

Q - R \not= 0

, the polynomial

Q - R

vanishes at

n

points, with degree less than

n

, which is a contradiction.

Calculus of Finite Differences Part-1

August 2021

Acknowledgements #

Preliminary Definitions #

Finding Patterns #

Notations #

Some Results #

Δ−1\Delta^{-1}Δ−1 #

Patterns again! #

Generalizing #

Calculus vs Finite Differences #

Addition and multiplication under a finite difference #

Multiplication of finite difference #

Division under a finite difference #

Chain Rule #

Some fun with Δ−1\Delta^{-1}Δ−1 #

Addition under Δ−1\Delta^{-1}Δ−1 #

Generalizing #

A motivating question #

Finding a polynomial that passes through nnn points #

Proof #

$\Delta^{-1}$ #

Some fun with $\Delta^{-1}$ #

Addition under $\Delta^{-1}$ #

Finding a polynomial that passes through $n$ points #