# Calculus of Finite Differences Part-2

*Achyut Bharadwaj, Saee Patil, Valentio Iverson, Danny Li*

##### August 2021

# 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$.

# 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

Therefore,

# 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.

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

Similarly,

**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

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

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

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

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

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

# 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: #

## 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.

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,

Chain rule:

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

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

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

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

We know that

# 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 #

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

### Hockey Stick Identity #

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

## 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}$$