6.3: Operators - Euler-MacLaurin summation

The next analogy studies unusual functions. Most functions turn numbers into other numbers, but special kinds of functions operators turn functions into other functions. A familiar example is the derivative operator D. It turns the sine function into the cosine function, or the hyperbolic sine function into the hyperbolic cosine function. In operator notation, \(D(\sin) = \cos\) and \(D(\sin h) = \cos h\); omitting the parentheses gives the less cluttered expression \(D \sin = \cos\) and \(D \sin h = \cos h\). To understand and learn how to use operators, a fruitful tool is reasoning by analogy: Operators behave much like ordinary functions or even like numbers.

Left shift

Like a number, the derivative operator \(D\) can be squared to make \(D^{2}\) (the second-derivative operator) or to make any integer power of \(D\). Similarly, the derivative operator can be fed to a polynomial. In that usage, an ordinary polynomial such as \(P(x) = x^{2} + x/10 + 1\) produces the operator polynomial \(P(D) = D^{2} + D/10 + 1\) (the differential operator for a lightly damped spring–mass system).

How far does the analogy to numbers extend? For example, do \(\cos hD \text{ or } \sin D\) have a meaning? Because these functions can be written using the exponential function, let’s investigate the operator exponential \(e^{D}\).

Question

What does \(e^{D}\) mean?

The direct interpretation of \(e\) is that it turns a function \(f\) into \(e^{Df}\).

However, this interpretation is needlessly nonlinear. It turns \(2f\) into \(e^{2Df}\), which is the square of \(e^{Df}\), whereas a linear operator that produces \(e^{Df}\) from \(f\) would produce 2\(e^{Df}\) from \(2f\). To get a linear interpretation, use a Taylor series as if \(D\) were a number to build \(e^{D}\) out of linear operators.

\[e^{D} = 1 + D + \frac{1}{2}D^{2} + \frac{1}{6}D^{3} + ... .\label{6.4} \]

Question

What does this \(e^{D}\) do to simple functions?

The simplest nonzero function is the constant function \(f = 1\). Here is that function being fed to \(e^{D}\):

\[\underbrace{(1 + D + ...)}_{e^{D}} \underbrace{1}_{f} = 1. \label{6.5} \]

The next simplest function \(x\) turns into \(x + 1\).

\[(1 + D + \frac{D^{2}}{2} + ...)x = x + 1. \label{6.6} \]

More interestingly, \(x^{2}\) turns into \((x + 1)^{2}\).

\[(1 + D + \frac{D^{2}}{2} + \frac{D^{3}}{6} ...) x^{2} = x^{2} + 2x + 1 = (x + 1)^{2}. \label{6.7} \]

Problem 6.14 Continue the pattern

What is \(e^{D}x^{3}\) and, in general, \(e^{D}x^{n}\)?

Question

What does \(e^{D}\) do in general?

The preceding examples follow the pattern \(e^{D}x^{n} = (x+1)^{n}\). Because most functions of \(x\) can be expanded in powers of \(x\), and \(e^{D}\) turns each \(x^{n}\) term into \((x + 1)^{n}\), the conclusion is that \(e^{D}\) turns \(f(x)\) into \(f(x + 1)\). Amazingly, \(e^{D}\) is simply L, the left-shift operator.

Multiple problems

Problem 6.15 Right or left shift

Draw a graph to show that \(f(x) \rightarrow f(x + 1)\) is a left rather than a right shift. Apply \(e^{- D}\) to a few simple functions to characterize its behavior.

Problem 6.16 Operating on a harder function

Apply the Taylor expansion for \(e^{D}\) to sin x to show that \(e^{D} \sin x = \sin(x + 1)\).

Problem 6.17 General shift operator

If \(x\) has dimensions, then the derivative operator \(D = d/dx\) is not dimensionless, and \(e^{D}\) is an illegal expression. To make the general expression \(e^{aD}\) legal, what must the dimensions of a be? What does \(e^{aD}\) do?

Summation

Just as the derivative operator can represent the left-shift operator (as \(L = e^{D}\)), the left-shift operator can represent the operation of summation. This operator representation will lead to a powerful method for approximating sums with no closed form.

Summation is analogous to the more familiar operation of integration. Integration occurs in definite and indefinite flavors: Definite integration is equivalent to indefinite integration followed by evaluation at the limits of integration. As an example, here is the definite integration of \(f(x) = 2x\).

In general, the connection between an input function g and the result of indefinite integration is \(DG = g\), where \(D\) is the derivative operator and \(G = \int g\) is the result of indefinite integration.

Thus \(D\) and are inverses of one another \(D\int = 1\) or \(D = 1/\int\) a connection represented by the loop in the diagram. (\(\int D \nleq 1\) because of a possible integration constant.)

Question

What is the analogous picture for summation?

Analogously to integration, define definite summation as indefinite summation and then evaluation at the limits. But apply the analogy with care to avoid an off-by-one or fencepost error (Problem 2.24). The sum \(\sum_{2}^{4}f(k)\) includes three rectangles \(f(2), f(3)\), and \(f(4)\) whereas the definite integral \(\sum_{2}^{4}f(k)\)dk does not include any of the \(f(4)\) rectangle. Rather than rectifying the discrepancy by redefining the familiar operation of integration, interpret indefinite summation to exclude the last rectangle. Then indefinite summation followed by evaluating at the limits \(a\) and \(b\) produces a sum whose index ranges from \(a\) to \(b − 1\).

As an example, take \(f(k) = k\). Then the indefinite sum \(\sum\) f is the function \(F\) defined by \(F(k) = k(k − 1)/2 + C\) (where C is the constant of summation). Evaluating \(F\) between 0 and \(n\) gives \(n(n − 1)/2\), which is \(\sum_{0}^{n - 1}k\). In the following diagram, these steps are the forward path.

In the reverse path, the new Δ operator inverts \(\sum\) just as differentiation inverts integration. Therefore, an operator representation for Δ provides one for \(\sum\). Because Δ and the derivative operator \(D\) are analogous, their representations are probably analogous. A derivative is the limit

\[\frac{d f}{d x}=\lim _{h \rightarrow 0} \frac{f(x+h)-f(x)}{h} \label{6.8} \]

The derivative operator \(D\) is therefore the operator limit

\[D = lim_{h \rightarrow 0} \frac{L_{h} - 1}{h}, \label{6.9} \]

where the Lh operator turns \(f(x)\) into \(f(x + h)\) that is, \(Lh\) left shifts by \(h\).

Problem 6.18 Operator limit

Explain why \(L_{h} ≈ 1 + hD\) for small h. Show therefore that \(L = e^{D}\).

Question

What is an analogous representation of Δ?

The operator limit for D uses an infinitesimal left shift; correspondingly, the inverse operation of integration sums rectangles of infinitesimal width. Because summation \(\sum\) sums rectangles of unit width, its inverse Δ should use a unit left shift namely, \(L_{h}\) with \(h = 1\). As a reasonable conjecture,

\[Δ = lim_{h \rightarrow 1} \frac{L_{h} - 1}{h} = L - 1. \label{6.10} \]

This Δ called the finite-difference operator is constructed to be \(1/\sum\). If the construction is correct, then \((L − 1)\sum\) is the identity operator 1. In other words, (L − 1)\(\sum\) should turn functions into themselves.

Question

How well does this conjecture work in various easy cases?

To test the conjecture, apply the operator \((L−1)\sum\) first to the easy function \(g = 1\). Then \(\sum g\) is a function waiting to be fed an argument, and (\(\sum g)(k)\) is the result of feeding it \(k\). With that notation, (\(\sum g)(k) = k + C\). Feeding this function to the \(L − 1\) operator reproduces \(g\).

\[[(L - 1) \sum g](k) = \underbrace{(k + 1 + C)}_{(L\sum g)(k)} - \underbrace{(k + C)}_{(1\sum g)(k)} = \underbrace{1}_{g(k)}. \label{6.11} \]

With the next-easiest function defined by \(g(k) = k\) the indefinite sum (\(\sum g)(k)\) is \(k(k − 1)/2 + C\). Passing \(\sum g\) through \(L − 1\) again reproduces \(g\).

\[[(\mathrm{L}-1) \Sigma \mathrm{g}](\mathrm{k})=\underbrace{\left(\frac{(\mathrm{k}+1) \mathrm{k}}{2}+\mathrm{C}\right)}_{(\mathrm{L} \Sigma \mathrm{g})(\mathrm{k})}-\underbrace{\left(\frac{\mathrm{k}(\mathrm{k}-1)}{2}+\mathrm{C}\right)}_{(1[\mathrm{~g})(\mathrm{k})}=\underbrace{\mathrm{k}}_{\mathrm{g}(\mathrm{k})} . \label{6.12} \]

In summary, for the test functions \(g(k) = 1\) and \(g(k) = k\), the operator product \((L − 1)\sum\) takes g back to itself, so it acts like the identity operator. This behavior is general \((L−1)\sum 1\) is indeed 1, and \(\sum = 1/(L−1)\). Because \(L = e^{D}\), we have \(\sum = 1/(e^{D} − 1)\). Expanding the right side in a Taylor series gives an amazing representation of the summation operator.

\[\sum = \frac{1}{e^{D} - 1} = \frac{1}{D} - \frac{1}{2} + \frac{D}{12} - \frac{D^{3}}{720} + \frac{D^{5}}{30240} - ... .\label{6.13} \]

Because \(D = 1\), the leading term \(1/D\) is integration. Thus, summation is approximately integration a plausible conclusion indicating that the operator representation is not nonsense.

Applying this operator series to a function f and then evaluating at the limits a and b produces the Euler–MacLaurin summation formula

\[\begin{aligned}
\sum_{a}^{b - 1} f(k)=& \int_{a}^{b} f(k) d k+\frac{f(b)+f(a)}{2}+\frac{f^{(1)}(b)-f^{(1)}(a)}{12} \\
&-\frac{f^{(3)}(b)-f^{(3)}(a)}{720}+\frac{f^{(5)}(b)-f^{(5)}(a)}{30240}-\cdots
\end{aligned} \label{6.14} \]

where \(f^{(n)}\) indicates the nth derivative of \(f\).

The sum lacks the usual final term \(f(b)\). Including this term gives the useful alternative

\[\begin{aligned}
\sum_{a}^{b} f(k)=& \int_{a}^{b} f(k) d k+\frac{f(b)+f(a)}{2}+\frac{f^{(1)}(b)-f^{(1)}(a)}{12} \\
&-\frac{f^{(3)}(b)-f^{(3)}(a)}{720}+\frac{f^{(5)}(b)-f^{(5)}(a)}{30240}-\cdots
\end{aligned} \label{6.15} \]

As a check, try an easy case: \(\sum_{0}{n}k\). Using Euler–MacLaurin summation, \(f(k) = k, a = 0\), and \(b = n\). The integral term then contributes \(n^{2}/2\); the constant term \([f(b) + f(a)]/2\) contributes \(n/2\); and later terms vanish. The result is familiar and correct:

\[\sum_{0}^{n}k = \frac{n^{2}}{2} + \frac{n}{2} + 0 = \frac{n(n + 1)}{2}. \label{6.16} \]

A more stringent test of Euler–MacLaurin summation is to approximate \(lnn!\), which is the sum \(\sum_{1}^{n}ln k\) (Section 4.5). Therefore, sum \(f(k) = ln k\) between the (inclusive) limits \(a = 1 \text{and} b = n\). The result is

\[\sum_{1}^{n} ln k = \int_{1}^{n} ln k dk + \frac{ln n}{2} + ... . \label{6.17} \]

The integral, from the \(1/D\) operator, contributes the area under the \(ln k\) curve. The correction, from the 1/2 operator, incorporates the triangular protrusions (Problem 6.20). The ellipsis includes the higher-order corrections (Problem 6.21) hard to evaluate using pictures (Problem 4.32) but simple using Euler–MacLaurin summation (Problem 6.21).

Multiple problems

Problem 6.19 Integer sums

Use Euler–MacLaurin summation to find closed forms for the following sums:

(a) \(\sum_{0}^{n} k^{2}\) (b) \(\sum_{0}^{n} (2k + 1)\) (c) \(\sum_{0}^{n} k^{3}\).

Problem 6.20 Boundary cases

In Euler–MacLaurin summation, the constant term is \([f(b) + f(a)]/2\) one half of the first term plus one-half of the last term. The picture for summing \(ln k\) (Section 4.5) showed that the protrusions are approximately one-half of the last term, namely \(ln n\). What, pictorially, happened to one-half of the first term?

Problem 6.21 Higher-order terms

Approximate \(ln 5!\) using Euler–MacLaurin summation.

Problem 6.22 Basel sum

The Basel sum \(\sum_{1}^{\infty}n^{-2}\) may be approximated with pictures (Problem 4.37).

However, the approximation is too crude to help guess the closed form. As Euler did, use Euler–MacLaurin summation to improve the accuracy until you can confidently guess the closed form.

Hint: Sum the first few terms explicitly.