Calculus of Finite Differences Part-2

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.

Definition and Preliminaries Notation #

Let us define a polynomial $f(x)$ to be $$f(x) = \sum_{i = 0}^n a_i x^i$$ for some $a_i \in \mathbb{C}$, for all $0 \le i \le n$ and $n \in \mathbb{N}_0$. We define the degree of a polynomial to be the largest non-negative integer $n$ such that $a_n \not= 0$ and let degree of the polynomial $f(x) = 0$ be $0$. Degree of a polynomial $f$ will be denoted as $\text{deg}(f)$.

Binomial Theorem #

The binomial theorem states that for $a,,b\in \mathbb{R}$ and $n\in\mathbb{N}$: $$(a+b)^n = \sum_{i=0}^{n} \binom{n}{i}a^ib^{n-i}$$

Part (a): A few examples with $\Delta$ #

Let us look at a few examples with the operation $\Delta$.

(1) $$\Delta(7-3x) = 7-3(x+1)-(7-3x) = 7-3x-3 - 7 + 3x = -3$$

(2) $$\Delta(x^2) = (x+1)^2 - x^2 = x^2 + 2x + 1 - x^2 = 2x+1$$

(3) $$\Delta(x^3) = (x+1)^3-x^3 = x^3 + 3x^2 + 3x + 1 - x^3 = 3x^2 + 3x + 1$$

Part (b): Iterations with the operator $\Delta$ #

We define $\Delta^n(f)$ recursively as $\Delta(\Delta^{n-1}(f))$. We now explore more about $\Delta^n(f)$.

Lemma 1. If $\Delta^n(f) = 0$ for $n\in\mathbb{N}$ and some function $f$, then $\Delta^{n + 1} (f) = 0$. Proof. It suffices to show that $\Delta(f) = 0$ if $f$ is the zero polynomial. This is true since

(4) $$\Delta(f) = f(x+1) - f(x) = 0 - 0 = 0. \:\:\square$$

For the first part of the problem, we have $\Delta(f) = -3$.
Therefore,

(5) $$\begin{aligned} \Delta^2(f) = \Delta(\Delta(f)) = \Delta(-3) = -3 - (-3) = 0 \end{aligned}$$

It now follows from Lemma 1 that $\Delta^{n}(f) = 0$ $\forall n \ge 2$. For the second part of the problem, we have $\Delta(f) = 2x + 1$. Therefore,

(6) $$\begin{aligned} \Delta^2(f) &= \Delta(2x + 1) = 2(x + 1) + 1 - (2x + 1) = 2 \\ \Delta^3(f) &= \Delta(2) = 2 - 2 = 0 \end{aligned}$$

and hence by Lemma 1, $\Delta^n(f) = 0$ $\forall n \ge 3$. For the third part, we have

(7) $$\begin{aligned} \Delta(f) &= 3x^2 + 3x + 1 \\ \Delta^2(f) &= \Delta(3x^2 + 3x + 1) \\ &= 3(x + 1)^2 + 3(x + 1) + 1 - (3x^2 + 3x + 1) \\ &= 6x + 6 \\ \Delta^3(f) &= \Delta(6x + 6) = 6(x + 1) + 6 - (6x + 6) = 6 \\ \Delta^4(f) &= \Delta(6) = 0\end{aligned}$$

and by Lemma 1, $\Delta^n(f) = 0$ $\forall n \ge 4$.

Part (c): Finding a function given its difference #

Say we are given $\Delta(f)$. Can we find the function $f$? We explore more about this in this section.

(8) $$\begin{aligned} \Delta (f)(x) = 3 \implies f(x+1)-f(x) = 3 \\ \implies f(x+1)=f(x)+3 \implies f(x) = 3\cdot x + c \\ \end{aligned}$$
(9) $$\begin{aligned} \Delta (f)(x) = x \implies f(x+1)-f(x) = x \\ \implies f(x+1)=f(x)+x \implies f(x) = f(0)+ \sum_{i=0}^{x-1} i \\ \implies f(x) = c+\frac{x(x-1)}{2} \\ \end{aligned}$$
(10) $$\begin{aligned} \Delta (f)(x) = x^2 \implies f(x+1)-f(x) = x^2 \\ \implies f(x+1)=f(x)+x^2 \implies f(x) = c+ \sum_{i=0}^{x-1} i^2 \\ \implies f(x) = c+\frac{x(x-1)(2x-1)}{6} \\ \end{aligned}$$
(11) $$\begin{aligned} \Delta^2 (f)(x) = x \implies \Delta (f(x+1)-f(x)) = x \\ \implies \Delta (f(x)) = f(0)+\frac{x(x-1)}{2} \\ \implies f(x+1)-f(x)=f(0)+\frac{x(x-1)}{2} \\ \implies f(x) = f(0)+\sum_{i=0}^{n-1} \frac{x(x-1)}{2} = c+\frac{x(x-1)(x+1)}{6} \end{aligned}$$
We can find the set of polynomials $S$ satisfying $\Delta^n(f) = g(x)$ for any polynomial $g$.

Part (d): Finding a Polynomial that Fits Data #

We are given the following data: $f(0)=1, f(1)=0, f(2)=5, f(3) = -1$. Can we fit a quadratic polynomial to this data? What about a cubic polynomial? We answer these questions and generalize our observations in this section.

(12) $$x\quad0\quad1\quad2\quad3$$

(13) $$f(x)\quad1\quad0\quad5\quad-1$$

(14) $$\Delta(f(x))\quad-1\quad5\quad-6$$

(15) $$\Delta^2(f(x))\quad6\quad-11$$

(16) $$\Delta^3(f(x))\quad-17$$

Notice that $\Delta^n(f(x))$ is constant only when $n=3$.

$\Delta^2(P(x))$ where $\deg(P(x)) = 2$ must be constant as we have proven in the Results/Conjectures section. However, $\Delta^2(f(x))$ is not constant, since it varies from 6 to $-11$. So, we cannot fit a quadratic polynomial to the given data.

$\Delta^3(f(x))$ is constant. So, we could fit a polynomial of degree 3 to the data.

Since

(17) $$\begin{aligned}\Delta(\Delta^2(f(x))) &= -17 \\ \Delta^2(f(x)) &= -17x + c\end{aligned}$$

for some constant $c$. When $x=0$, $\Delta^2(f(x)) = 6$. Hence, $c=6$.

Similarly,

(18) $$\begin{aligned} \Delta(\Delta(f(x))) &= -17x+6 \\ \implies \Delta(f(x)) &= -17\frac{x^2-x}{2} + 6x + c' \\ &= -\frac{17}{2}x^2 + \frac{29}{2}x + c' \end{aligned}$$

for some constant $c’$. When $x=0$, $\Delta(f(x)) = -1$. Hence, $c’ = -1$.

(19) $$\begin{aligned} \Delta(f(x)) &= \frac{17}{2}x^2 + \frac{29}{12}x - 1 \\ \implies f(x) &= -\frac{17}{2}\frac{2x^3 - 3x^2 + x}{6} + \frac{29}{2}\frac{x^2-x}{2}-x + c'' \\ &= -\frac{17}{6}x^3 + \frac{17}{4}x^2 - \frac{17}{12}x + \frac{29}{4}x^2 - \frac{29}{4}x - x + c'' \\ &= -\frac{17}{6}x^3 + \frac{23}{2}x^2- \frac{29}{3}x+c''\end{aligned}$$

When $x=0$, $f(x) = 1$. Hence, $c’’=1$. Thus, the cubic polynomial that fits the given data is

(20) $$-\frac{17}{6}x^3+\frac{23}{2}x^2 - \frac{29}{3}x + 1$$

The answer is yes. In fact, we claim an even more generalized result.

Claim. 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. We’ll first prove that there exists such polynomial. Consider the polynomial

(21) $$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 $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.

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

(22) $$\sum_{k \ge 0} a_k \binom{n + k}{k}$$

for real $a_k$.

We will prove this by induction on $\text{deg} \ P$. Indeed, if $\text{deg} \ n = 0$, then if $P(x) = c$, we could write $a_0 = c, a_i = 0$ for all $i \ge 1$: and we have

(23) $$\sum_{k \ge 0} a_k \binom{n + k}{k} = a_0 = c$$

which is what we wanted. Now, suppose this works for any polynomial with $\text{deg} \ P \le \ell$ for some $\ell \in \mathbb{N_0}$, then we will prove this for $\text{deg} \ P = \ell + 1$. Indeed, if we have $$P(x) = \sum_{i = 0}^{\ell + 1} b_i x^i$$where $b_{\ell+ 1} \not= 0$, then note that

(24) $$\binom{n + \ell + 1}{\ell + 1} = \frac{(n + \ell + 1) (n + \ell) \cdots (n + 1)}{(\ell + 1)!}$$

which is a polynomial of degree $\ell + 1$ in $n$, with leading coefficient $\frac{1}{(\ell + 1)!}$. Now, consider the polynomial

(25) $$Q(x) = P(x) - \frac{b_{\ell + 1}}{(\ell + 1)!} \binom{n + \ell + 1}{\ell + 1}$$

which is a polynomial of degree less than $\ell + 1$ because the coefficient of $x^{\ell + 1}$ cancels out.

Furthermore, this choice of coefficient is unique because $\binom{n + i}{i}$, for $i \le \ell$ won’t contribute any coefficient to $x^{\ell + 1}$ and if there exists any coefficient of $\binom{n + i}{i}$ where $i > \ell + 1$ that contributes a nonzero coefficient, then take such maximal $i$, then the coefficient of $x^i$ is nonzero, which has degree greater than $n + 1$. Therefore, by inductive hypothesis, $Q$ has a representation in $$\sum_{k \ge 0} a_k \binom{n + k}{k}$$Therefore, we are done by induction.

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

(26) $$\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

(27) $$\begin{aligned}\Delta \binom{n + k}{k} &= \binom{n +k + 1}{k} - \binom{n + k}{k} \\ &= \frac{(n + k)!}{k!(n + 1)!} \cdot (n + k + 1 - n - 1) \\ &= \binom{n + k}{k - 1}\end{aligned}$$

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,

(28) $$\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.

Now, we will prove the existence of such polynomial. Indeed, consider Using this fact, note that if $P(x) \not= 0$, then

(29) $$\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}$$

Therefore, we could backtrack and retrieve $\Delta^{-1}(P(x))$ whenever we have $P(x)$

Part (e): Summing consecutive powers #

While trying to find a closed form for $\sum_{i=0}^{n-1}i^k$ using its recursive form, we found a few patterns (Recursive formula in the Results/Conjectures Section).

Patterns #

The sum of the coefficients of the terms in the expansion of the numerator of the summation is 0 (for $k\geq 1$)
The sum of the absolute values of the coefficients of the terms in the expansion of the numerator of the summation is always $1$.
The product of the first $n$ denominators of the coefficients of the terms in the expansion of the summation is equal to the $(n+1)$th term’s coefficient’s denominator for all even $k$.
The signs of the coefficients alternate for a given value of $n$.

Part (f): Calculus vs Finite Differences #

There are many similarities between calculus and finite differences. The operator $\Delta$ has properties similar to that of $\frac{d}{dx}$ in calculus. In this section, we will compare calculus with finite differences.

Product formula: #

(30) $$\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(g(x)) + g(x)\Delta(f(x)) \\\end{aligned}$$

Division under $\Delta$: #

We first find a formula for $\Delta(\frac{1}{f(x)})$ in terms of $f(x)$ and $\Delta(f(x))$. Then, we can write $\frac{f(x)}{g(x)}$ as $f(x)\frac{1}{g(x)}$ and use the product formula to get the result.

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

Notice, that the product formula is similar to the product formula in calculus, except that we have $f(x+1)\Delta(g(x))$ instead of $f(x)\Delta(g(x))$. This is because, in calculus, the difference (say $h$) approaches 0. Thus, $f(x+h) \to f(x)$, so $f(x+h)g’(x) \to f(x)g’(x)$.

Another interesting observation is that we have $f(x+1)\Delta(g(x))$, but we only have $g(x)\Delta(f(x))$. Note the absence of the $+1$ in the second term. However, commutativity still holds. When we evaluated $\Delta(f\cdot g)$, we added and subtracted $f(x+1)f(x)$ to $f(x+1)g(x+1)-f(x)g(x)$. So, when we evaluate $\Delta(g\cdot f)$, must add and subtract $f(x)g(x+1)$ to $f(x+1)g(x+1)-f(x)g(x)$. Doing so will still give us the same value, since we are not adding any net value by adding and subtracting the same term.

Now,

(32) $$\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(f(x))$$

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

(33) $$-f(x+1)\frac{\Delta(g(x))}{g(x+1)g(x)} + \frac{\Delta(f(x))}{g(x)} = \frac{g(x+1)\Delta(f(x))-f(x+1)\Delta(g(x))}{g(x+1)g(x)}$$

Chain rule:

The chain rule does not work under finite differences. We can see this by an example. Say,

(34) $$f(x) = (2x)^2$$

We can evaluate $\Delta(f(x))$ by expanding $(2x)^2$. We have,

(35) $$f(x) = (2x)^2 = 4x^2$$

So,

(36) $$\Delta(f(x)) = 4(\Delta(x^2)) = 4(2x+1) = 8x+4$$

Now, we apply the chain rule as in calculus. Let $u=2x$. So, $f(u) = u^2$.

(37) $$\Delta(f(u)) = 2u+1 = 4x+1$$

and $\Delta(u) = 2$. So,

(38) $$\Delta(f(u))\Delta(u) = 2(4x+1) = 8x+2 \neq 8x+4$$

Let us explore the reason that the chain rule does not work in finite differences.

We know that

(39) $$\Delta(f(x)) = \frac{\Delta f}{\Delta u}\cdot\frac{\Delta u}{\Delta x}$$

Also, for the chain rule to work, we need

(40) $$\Delta(f(x)) = \Delta(f(u))\Delta(u)$$

Thus, we need

(41) $$\Delta(f(u))\Delta(u) = \frac{\Delta f}{\Delta u}\cdot\frac{\Delta u}{\Delta x}$$

to be true. We know that $\Delta x = 1$. So, the above is true iff

(42) $$\Delta(f(u))\Delta(u) = \frac{\Delta f}{\Delta u}\cdot{\Delta u} \iff \frac{\Delta f}{\Delta u} = \Delta(f(u))$$

This however, is not a true statement. In calculus, the statement is true, since we are not dealing with differences that are finite.

Results/Conjectures #

If $f$ is a polynomial, then $\Delta(f)$ is also a polynomial.
(43) $$\Delta^n(f + g) = \Delta^n (f) + \Delta^n(g)$$
Proof.
(44) $$\begin{aligned} \Delta(f + g) &= f(x + 1) + g(x + 1) - f(x) + g(x) \\ &= f(x + 1) - f(x) + g(x + 1) - g(x) \\ &= \Delta(f) + \Delta(g) \end{aligned}$$
If $\deg{f(x)} = n$, then $\Delta^n(f) = c$, where $c=f(0)$ Proof. Again, by induction.
(45) $$\Delta^{-1}(f+g) = \Delta^{-1}(f) + \Delta^{-1}(g)$$
We know that
(46) $$\Delta(f+g) = \Delta(f)+\Delta(g)$$
Now,
(47) $$\Delta^{-1}(\Delta(f+g)) = f+g$$
Hence,
(48) $$\Delta^{-1}(\Delta(f)+\Delta(g))=f+g$$
Also,
(49) $$\Delta^{-1}(\Delta(f)) + \Delta^{-1}(\Delta(g)) = f + g$$
Equating the LHS of the above two equations, we get:
(50) $$\Delta^{-1}(\Delta(f)+\Delta(g))=\Delta^{-1}(\Delta(f)) + \Delta^{-1}(\Delta(g))$$
We let
(51) $$\Delta(f) = f', \Delta(g) = g'$$
Thus,
(52) $$\Delta^{-1}(f'+g') = \Delta^{-1}(f')+\Delta^{-1}(g')$$
Thus for all functions whose difference is defined,
(53) $$\Delta^{-1}(f+g) = \Delta^{-1}(f) + \Delta^{-1}(g)$$
(54) $$\sum_{i=0}^{n-1}i^{k-1} = \frac{n^k - \sum_{i=0}^{n-1}(\sum_{j=2}^{k}(\binom{k}{j}i^{k-j}))}{k}$$
Observe that
(55) $$\sum_{i=0}^{n-1}(i+1)^k - \sum_{i=0}^{n-1}i^k = n^k$$
So,
(56) $$\sum_{i=0}^{n-1}(i+1)^k - i^k = n^k$$
The above becomes:
(57) $$\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$$
from the binomial theorem. So, we have
(58) $$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-1}$$
by rearranging the above. Hence,
(59) $$\sum_{i=0}^{n-1}i^{k-1} = \frac{n^k - \sum_{i=0}^{n-1}(\sum_{j=2}^{k}(\binom{k}{j}i^{k-j}))}{k}$$

Appendix #

Closed form of summation $i^k$ #

Taylor Series Equivalent #

(60) $$f(a+i) = \sum_{j=0}^\infty \Delta^j(f)(a)\binom{i}{j}$$

for some constant $a$.

Let $f(i) = i^k$. So, we have:

(61) $$\begin{aligned} f(i) = i^k = \sum_{j=0}^\infty\Delta^j(f)(0)\binom{i}{j}\end{aligned}$$

Now, we take summation on both sides with $i$ going from $0$ to $n-1$ where $n\in\mathbb{N}$. Doing so, we get:

(62) $$\begin{aligned} \sum_{i=0}^{n-1}i^k &= \sum_{i=0}^{n-1}\left(\sum_{j=0}^\infty\Delta^j(f)(0)\binom{i}{j}\right) = \sum_{j=0}^\infty\left(\sum_{i=0}^{n-1}\Delta^j(f)(0)\binom{i}{j}\right) \\ &= \sum_{j=0}^\infty\left(\Delta^j(f)(0)\sum_{i=0}^{n-1}\binom{i}{j}\right)\end{aligned}$$

Hockey Stick Identity #

(63) $$\sum_{i=0}^{n-1}\binom{i}{j} = \binom{n}{j+1}$$

(64) $$\sum_{i=0}^{n-1}\binom{i}{j} = \sum_{i=0}^{n-1}\left(\binom{i+1}{j+1}-\binom{i}{j+1}\right) = \binom{n}{j+1} - \binom{0}{j+1} = \binom{n}{j+1}$$

Now, substituting $\sum_{i=0}^{n-1}\binom{i}{j} = \binom{n}{j+1}$ into the above equation, we get:

(65) $$\begin{aligned} \sum_{i=0}^{n-1}i^k &= \sum_{j=0}^\infty\left(\Delta^j(f)(0)\binom{n}{j+1}\right)\end{aligned}$$

and we are done.

Questions to Think About #

add def of $\Delta_x$
Differential equations?
Chain rule equiv?
$e^x$ equiv: $2^x$ ($[e]=2$)
Fundamental thm?
Trigonometric fns?
log fns?
Local extremes?
Fundamental Theorem of Finite Differences:
(66) $$\begin{aligned} (\Delta)_x\left(\sum_{t=a}^{x-1}f(t)\right)=f(x) \end{aligned}$$