Black Mold

After facing much difficulty in the derivations from this post, and doing some cursory digging into the "advanced" techniques for solving the troublesome recurrence relations enclosed within, I uncovered some information about the Umbral Calculus, developed by one Rev. John Blissard¹ in an 1860s series of articles on symbolic different "Generic Equations,"^2,3 which is all together more esoteric and fascinating.

The idea is symbolic in nature, and aims to (amongst other things) find a relationship between discrete and continuous calculus. What it lacks in rigor, it more than makes up for with clever and seemingly magical symbolic derivations which may have foreshadowed Heiner's unified Algebra.⁴

This post is rather unstructured, and more or less serves as a meandering random walk through some applications of the Umbral Calculus which I found interesting and/or useful.

Operators

We'll begin by introducing some notation which simplifies some of the algebra to come. If we consider the fundamental theorem of calculus:

we'll rewrite the derivative and integral operators as $\mathcal {\color{#00B4CE}D\color{black}}$ and $\mathcal{\color{#006EB8}I\color{black}}$:

Theory of Discrete Calculus

Similarly, we can rewrite the discrete analogs of derivations and integrations (differences and summations):

Our goal is to find a relationship to bridge the gap between discrete and classical calculus via some additional operator we'll denote $\color{#613F99}\phi\color{black}$ such that:

From pre-calc, we know that the derivative is a continuous rate of change of the line tangent to each point on a curve. For some function such as $f(x) = x^2$, the derivative with respect to $x$ is $2x$:

In Discrete Calculus, we're concerned with the discrete rate of change which we measure with $\mathcal {\color{Orange}\Delta\color{black}}$:

If we know the value of $\mathcal {\color{Orange}\Delta\color{black}}f(x)$ for a specific value of $x$, we can also compute the value of $f(x+1)$:

so we arrive at a value of $2x + 1$ for the discrete rate of change, where $\mathcal {\color{Orange}\Delta\color{black}}$ is known at the forward difference operator, the general form of which is:

Linear Operators

An important property of $\mathcal {\color{Orange}\Delta\color{black}}$ is its linearity – or that it preserves addition and scalar multiplication such that:

1. $\mathcal {\color{Orange}\Delta\color{black}}f(x) + \mathcal {\color{Orange}\Delta\color{black}}g(x) = f(x+1) + g(x+1) - f(x) - g(x)$
2. $$\begin{aligned} \mathcal {\color{Orange}\Delta\color{black}}af(x) &= af(x+1) - af(x) \\ &= a\big[f(x+1) - f(x)\big] \\ &= a \mathcal {\color{Orange}\Delta\color{black}}f(x) \end{aligned}$$

And, just like in classical, continuous calculus where differentiation is inversely related to integration, forward differencing is the inverse of summation:

This should be evident from our plot of $f(x) = x^2$ above where:

We can prove that this generalization holds by expanding successive terms of a summation involving $\mathcal {\color{Orange}\Delta\color{black}}$:

which looks suspiciously similar to the Fundamental Theorem of Calculus... This is useful because it means that finding a summation formula for e.g. $n^2$ is equivalent to finding a function who's $\mathcal {\color{Orange}\Delta\color{black}}$ is $x^2$ like so:

We can rearrange and substitute some of these equations to get a general expression for $x^2$ in terms of the known expressions of $\mathcal {\color{Orange}\Delta x\color{black}}$ and $\mathcal {\color{Orange}\Delta x^2\color{black}}$:

And, since $\mathcal {\color{Orange}\Delta x\color{black}} = 1$, we can slap it on the end which will let us do some additional factoring:

an equation for $x^2$ in terms of $\mathcal{\color{Orange}\Delta\color{black}}$. By linearity, we can factor out the $\mathcal{\color{Orange}\Delta\color{black}}$:

which is (drum roll) a function who's delta is $x^2$.

If Frank Lloyd Wright tried his hand at exponentiation

As alluded to before, the inverse of the forward difference is given by indefinite summation:

which is unique up to a constant term, like the indefinite integral. Again, recall that our overarching goal is to devise some method of ""interpolating"" between discrete and continuous calculus. The crux of this translation $\color{#613F99}\phi\color{black}$ will be falling powers which is like a parameterized factorial function:

Since $x_{ \text{\textcircled{n-1}}}$ appears in both terms, we can sub it in:

Now lets consider the $\mathcal{\color{Orange}\Delta\color{black}}$ of $x$ falling $n$:

which is shaped the same as the power rule for differentiation, just with the exponent and subscript switched...

And therein lies the behavior of the umbral operator:

We can observe how $\mathcal{\color{#613F99}\phi\color{black}}$ composes with our difference/differentiation operators by tracing the diagram. E.g. from top left to bottom right, first taking the derivative of some number then applying $\mathcal{\color{#613F99}\phi\color{black}}$ to it, we get:

And, by linearity, this holds for all polynomials, as well as a bunch of other transcendental functions that can be expressed by series expansion by polynomials, so for concision we might just write:

which kind of begs the question, can't we just divide through by $\mathcal{\color{#613F99}\phi\color{black}}$? No! similar to matrix multiplication it's not multiplicatively commutative. We can, however, multiply through by (apply, composably) its inverse to yield expressions like the following:

(and of course, this also applies to summation and integrals by reading the diagram from bottom-right to top-left). This Umbral technique is roughly analogous to Galois Theory^5,6 insofar as we're taking taking a hard problem like integration, translating it into a comparatively easier setting of discrete summation, solving the problem there, and then exfiltrating our findings back out into the "harder" context via this $\mathcal{\color{#613F99}\phi\color{black}}$ operator.

As one last trivial example, we could concretely derive the formula for $\sum n^2$ as:

Nontrivial $\phi$

None of these techniques are useful unless we know $\mathcal{\color{#613F99}\phi\color{black}}$ and $\mathcal{\color{#613F99}\phi^{-1}\color{black}}$. For polynomials discussed so far, it's relatively straightforward to derive the values:

Using the same substitution strategy used for computing the forward difference, we can attain the inverse:

Stirling Numbers

And using this method, we can find $\mathcal{\color{#613F99}\phi\color{black}}$ and $\mathcal{\color{#613F99}\phi^{-1}\color{black}}$ for any polynomial:

These are known as the Signed Stirling Numbers of the first kind, and Unsigned Stirling Numbers of the second kind – respectively.

They have some nice properties. We can compute the coefficients of a row by multiplying the negated row index by the first term and adding it to the next term. For example, the second term of the fifth row would be:

For the unsigned Stirling numbers, we compute the next set of coefficients by multiplying the corresponding coefficient from the previous row by its exponent and add it to the next term:

In order to further underscore the apparent relationship to Pascal's triangle an binomial coefficients, we express these polynomials in brackets and braces:

These sequences lie at the heart of Umbral calculus, and have natural applications in combinatorics as well.

that is, $n$ choose $k$ can be though of as the number of $k$ objects we can take from $n$ objects and by the number of permutations of $k$ objects, the quotient of which is the number of ways to choose $k$ objects from $n$ objects, ignoring their orderings. We can use this identity to compute $\mathcal{\color{#613F99}\phi\color{black}}$ for some other functions like:

which looks an awful lot like the Binomial Theorem for $b=1$:

And, knowing $\mathcal{\color{#613F99}\phi e^{ax} \color{black}}$, we can also tap into some trigonometric functions to derive equations for their discrete $\leftrightarrow$ continuous mappings:

And similarly, we get a formula for $\mathcal{\color{#613F99}\phi \cos x \color{black}}$:

which in turn give rise to other classical results:

We can take the Umbral a step further, taking a step upwards in the direction of Category Theory by generalizing what we've observed about calculus operations to number theory and arithmetic.

Operational Calculus

Briefly revisiting the behavior of Umbral operations in conjunction with linear operators, we'll motivate discussion of their applicability to differential equations, recurrence relations, exponential shifting, and more.

Consider the number line of reals, together with arithmetic multiplication and addition (i.e. the field $\langle\mathbb F, +, \times\rangle$). Instead of thinking of a number as a point on the line, let's shift our representational understanding of them to be operations themselves, and addition and multiplication to be shifts and stretches applied to the numeral operators. E.g., the point $2$ together with other operators, can be thought of as:

The notion of addition can then be thought of as the translation which maps $0 \mapsto 2$ (shifting the whole number line accordingly), same with multiplication:

• two points combined via the extraneous notion of $\color{red}\times\color{black}$:

• two, as a point, on which we can apply the transformation $\color{red}\times3\color{black}$:

• The converse: three, as a point, on which we can apply the transformation $\color{red}\times2\color{black}$:

• and finally, the composition(s) of those transformations acting on $1$:

Considering numbers themselves as transformations acting on functions, we can also write:

Numbers as operators (distinct from the implicit shorthand multiplication where we place numbers next to one another sans $\times, \cdot$) are themselves linear operators since they maintain:

1. additivity: $\color{red}a(b+c) = ab + ac\color{black}$
2. and commutative under scalar multiplication

So, the above expression is more explicitly written:

And, similarly, this applies to addition as well:

Examining a non-trivial linear operation which purportedly ought to follow similar rules, can we make sense of something like:

In the context of composing operators, it's useful to divorce ourselves from the specifics of their application –only bearing in mind⁷ the category/domain of our contextual applicability, which for us so far is just $\Real$:

Visually, we don't have to know or care about the values of our unlabeled points, just the transformations connecting them. Let's zoom in on the derivative operator $\mathcal {\color{red}D \color{black}}$ (also colored red to emphasize the representational equivalence to numeral operators). As established before, it's also a linear operator, preserving scalar addition and distributing & commuting under scalar multiplication:

Note here that $a,b$ don't ever have to be scalars. They could also be any other linear operator. So, given an expression like:

we can apply intuitive rules of algebra to derive:

Which we can apply to a second order differential equation like so:

We can just factor it into two maybe-much-simpler equations:

by the principle of superposition, which we can combine to yield a general solution to the equation:

So we can discuss and manipulate differential equations of any order using purely algebraic mechanics.

Unit Shifting

Let's consider another "outside-the-box" linear operator called the unit shift, denoted $\mathcal{\color{red}T\color{red}}$, defined by:

We can express the forward difference operator $\mathcal{\color{Orange}\Delta\color{black}}$ then in terms of the unit shift $\mathcal{\color{red}T\color{red}}$:

Incidentally, just as the terms of $\color{#613F99}\phi\color{black}$ gave us Stirling numbers, $\mathcal{\color{red}T\color{red}}$ gives us binomial coefficients:

And, just as we used $\mathcal {\color{#00B4CE}D \color{black}}$ to solve differential equations, we can use $\mathcal{\color{Orange}\Delta\color{black}}$ to solve discrete difference equations:

Similarly, we can use $\mathcal{\color{red}T\color{red}}$ to solve recurrence relations:

which, in turn, means we can solve recurrence relations just like we would solve differential equations:

Concretely, for e.g. the Fibonacci sequence where:

We would express this in terms of unit shifts like so:

(Note that the $\varphi$ used here is the golden ratio and its conjugate, not to be confused with our transformation $\color{#613F99}\phi\color{black}$). Using the same superposition principle, we get a general solution:

And the constant are given by the initial conditions:

And so the closed form for the Fibonacci sequence via differential equations is:

What about a less-trivial example, i.e. one where the right hand side of the equation isn't zero:

So how do we find the inverse of something like this? The trick is to notice that the product rule for differentiation can give us something like:

such as:

which has the same form as our target equation, just multiplied by $e^{-x}$:

and we do know how to compute the inverse of the righthand side, albeit tediously, through integration by parts (not once, not twice, ...):

Which means that we can shift a differential equation to make it easier to solve by multiplying through by an exponential. This is the exponential shift theorem.

Series Expansion

Alternatively, we could've just expanded $(\mathcal{\color{#00B4CE}1 - D \color{black}})^{-1}$ as a geometric series:

We can use this approach to express any polynomial as a Taylor Series centered at an arbitrary point $a$ like so:

Here, $\mathcal{\color{red}D\color{black}}$ is still differentiation with respect to $x$, applied to $f$ evaluated at $a$. Not that the left hand side of this equation is a unit shift of $x$ units applied to $a$:

and the sum on the right is just the sum we get if we expand $e^{x\mathcal{\color{red}D\color{black}}}$:

So, just like exponentiating a complex number of the form $a + bi$ corresponds to the composition of a stretch action and an orthogonal rotation action, so too does exponentiation of the derivative operator produce a scalar stretch and orthogonal shift:

So, if we exponentiate $\mathcal{\color{red}a +bD\color{black}}$, we get the composition of scalar stretch and orthogonal shift:

which finds application in describing iterated functions of the form:

Footnotes