4. One step transformations

The grids for most of the standard series transformations (such as Kummer’s or Euler’s) are just “railroad tracks”. One rail (call it the j = 0 rail) is labeled with the original matrix sequence N_{0,n}, and the “ties”, labeled with matrices J_{n}, mechanize the transformation to the j = 1 rail. This same geometry mechanizes the termwise transformation of a composition of arbitrary homographic functions (possibly a sum!) into a (typically, nonregular) continued fraction. That is, let

N_{0,n} := ( \begin{matrix}a_{n} & b_{n} \\ c_{n} & d_{n} \end{matrix} )

be the matrix for the homographic function

f_{n}(x) := \frac{a_{n}x + b_{n}}{c_{n}x + d_{n}} ,

and define

g_{n} := a_{n} + \frac{c_{n}}{c_{n−1}} d_{n−1}, h_{n} := −\frac{c_{n+1}}{c_{n}} (a_{n}d_{n} − b_{n}c_{n}).

Here, we must have c_{n} ≠ 0, so any sum must be via b_{n} = 0. Then the “tie” matrices are

J_{n} := ( \begin{matrix}1 & a_{n} − g_{n} \\ 0 & c_{n} \end{matrix} )

and the continued fraction (j = 1) rail has matrices

N_{1,n} := ( \begin{matrix}g_{n} & h_{n} \\ 1 & 0 \end{matrix} ) .

Path invariance follows from mechanically verifying N_{0,n}J_{n+1} = J_{n}N_{1,n}. Then the equivalence of the paths (0, 1) → (0, m) → (1, m) and (0, 1) → (1, 1) → (1, m), after multiplying on the right by the columnating equation defining x,

( \begin{matrix}(y + \frac{d_{m}}{d_{m+1}} ) c_{m+1} \\ 1 \end{matrix} ) =: \binom{x}{1},

and equating the ratios of the upper and lower elements, gives the desired identity:

f_{1}(f_{2}(… (f_{m}(y))...)) = −\frac{d_{0}}{c_{0}} + \frac{1}{c_{1}} (g_{1} + \frac{h_{1}}{g_{2} + \frac{h_{2}}{\begin{matrix}. & . & . \\ g_{m} + \frac{h_{m}}{x} \end{matrix}}} ).

To convert a sum from the standard form (c_{n} = 0), adjoin it as a N_{−1,n} “third rail” via ties J′_{n} := ({0 \atop 1} {1 \atop 0}), or any other matrix which unzeros the lower left element of N_{0,n} = J_{n}^{′−1}N_{−1,n}J′_{n+1}.

Even the artifice of multiplication by \binom{x}{1} fits into the path invariance scheme, merely by connecting a new, “black hole” node to all existing nodes via edges labeled with this (uninvertible) matrix.

Another transformation, summation by parts, is applicable either before or after conversion to ratio form, via a “double decker” railroad track in the form of a square tube. Let p_{n} and q_{n} be two arbitrary functions of the summation index n. Traditional summation by parts transpires on the bottom (j = 0) track, via the matrices

N_{0,0,n} := ( \begin{matrix}1 & q_{n}(p_{n+1} − p_{n}) \\ 0 & 1 \end{matrix} ) , N_{0,1,n} = ( \begin{matrix}1 & p_{n+1}(q_{n+1} − q_{n}) \\ 0 & 1 \end{matrix} )

K_{0,0,n} := ( \begin{matrix}−1 & −p_{n}q_{n} \\ 0 & 1 \end{matrix} ) ,

where the subscript order is j, k, n. Now suppose that

ρ_{n} := \frac{p_{n+1}}{p_{n}} , and σ_{n} := \frac{q_{n+1}}{q_{n}}

are “nicer” functions of n than the corresponding p_{n} and q_{n}, perhaps by virtue of factorials or nth powers in the latter. Then one can jump to the upper track, where summation by parts looks like

N_{1,0,n} = ( \begin{matrix}ρ_{n}σ_{n} & ρ_{n} − 1 \\ 0 & 1 \end{matrix} ) , N_{1,1,n} = ( \begin{matrix}ρ_{n}σ_{n} & ρ_{n}(σ_{n} − 1) \\ 0 & 1 \end{matrix} )

K_{1,0,n} = ( \begin{matrix}−1 & −1 \\ 0 & 1 \end{matrix} )

if one labels the “vertical ties” with

J_{0,k,n} := ( \begin{matrix}p_{n}q_{n} & 0 \\ 0 & 1 \end{matrix} ) .

For example, with

ρ_{n} := \frac{n + c}{n + e} \frac{n + d}{n + c + d − e}, σ_{n} := \frac{n + a + 1}{n + 1} \frac{n + b + 1}{n + a + b + 1},

the path equivalence (1, 0, 0) → (1, 1, 0) → (1, 1, ∞) = (1, 0, 0) → (1, 0, ∞) → (1, 1, ∞), i.e.

K_{1,0,0} ∏_{n≥0} N_{1,1,n} = (∏_{n≥0} N_{1,0,n}) K_{1,0,∞},

gives, after negating the upper right elements,

4F_{3} \left[{a,  b,  c,  d \atop a + b + 1, e, c + d − e}\right] = \frac{(a + b)! (c + d − e − 1)! (e − 1)!}{a! b! (c − 1)! (d − 1)!}

+\frac{e − c}{e} \frac{e − d}{e − c − d}_{4}F_{3} \left[{a + 1, b + 1,  c,  d \atop a + b + 1, e + 1, c + d − e + 1}\right].

When only one of σ_{n} and ρ_{n} is nice, it is straightforward to construct diagonal ties linking an upper rail with a lower one, getting a hybrid, partially rationalized summation by parts.

5. Telescopy

Telescopy takes place between a single rail and a black hole. The problem is to find columnar, “diving in” matrices which path-invariantly connect the black hole to all the nodes along the rail. Then the telescoping identity is the equivalence between diving straight in, and performing the sum prior to diving in.

•
( \begin{matrix}1 & b_{n} − b_{n−1} \\ 0 & 1 \end{matrix} )  \binom{−b_{n}}{1}  \binom{−b_{n+1}}{1}  ( \begin{matrix}1 & b_{n+2} − b_{n+1} \\ 0 & 1 \end{matrix} )

• •
( \begin{matrix}1 & b_{n+1} − b_{n} \\ 0 & 1 \end{matrix} )

A nontrivial choice of b_{n} might be

b_{n} := \frac{2^{−n}}{1 − x^{2^{−n}}} ⇒ ∑_{n≥1} \frac{2^{−n}}{1 + x^{2^{−n}}} = \frac{1}{log x} + \frac{1}{1 − x},

when the alternate paths dive in from n = 1 and n = ∞. Rationalized telescopy differs from regular telescopy only in the contents of the matrices.

( \begin{matrix}\frac{1 + f_{n}}{f_{n+1}} & 1 \\ 0 & 1 \end{matrix} ) \binom{−f_{n+1}}{1} = \binom{−f_{n}}{1} ⇒ ∏_{n=0}^{m} ( \begin{matrix}\frac{1 + f_{n}}{f_{n+1}} & 1 \\ 0 & 1 \end{matrix} ) \binom{−f_{m+1}}{1} = \binom{−f_{0}}{1}

An interesting choice of f_{n} is

f_{n} := −\frac{x^{2^{−n}} + c}{c^{2} + c} ⇒ ∑_{n≥0}(\sqrt{x} − c)(\sqrt{\sqrt{x}} − c) … (x^{2^{−n}} − c) = \frac{\frac{x}{c} + 1}{c + 1}, |1 − c| < 1.

Any hypergeometric sum, that is, one whose term ratio is a rational function of the summation index n, can be expressed in numerous ways as a product of matrices of polynomials in n. We now have infallible algorithms (decision procedures) for determining, where possible, arbitrary partial sums of such series. At least one of these algorithms [1] hinges on minimizing the degrees of the on-diagonal polynomials at the expense of the non-zero off-diagonal one. This canonicalization proceeds in a finite number of steps, and can be visualized as path invariant hopping between parallel rails to the minimal one. The minimality then reduces the search for the telescoper (“diving in”) matrix to a single system of simultaneous linear equations.

6. “Residues”, Euler-Maclaurin summation

Let f be sufficiently tame, and define

N_{k,n} := ( \begin{matrix}1 & ∫_{0}^{1} f^{(k)}(t + n)B_{k}(t) dt \\ 0 & 1 \end{matrix} ) , K_{k,n} := ( \begin{matrix}−\frac{1}{k + 1} & −\frac{B_{k+1}}{k + 1}f^{(k)}(n) \\ 0 & 1 \end{matrix} ) .

Then path invariance,

N_{k,n}K_{k,n+1} = K_{k,n}N_{k+1,n},  k > 0

follows from integration by parts, except when k = 0, where

N_{0,n}K_{0,n+1} = E_{n}K_{0,n}N_{1,n},

E_{n} := ( \begin{matrix}1 & f_{n+1} \\ 0 & 1 \end{matrix} ) = N_{0,n}K_{0,n+1}N_{1,n}^{−1}K_{0,n}^{−1},

because 1 is the only non-negative integer k for which B_{k}(0) ≠ B_{k}(1). Thus, path invariance breaks down between k = 0 and k = 1, and the residues are tallied by the E_{n}, which commute to the left. In the final formula, these residues comprise the ∑ f(n) to which the ∫ f(t) (from the k = 0 path) is the first approximation.

∏_{n=a}^{b} N_{0,n} ∏_{k=0}^{c} K_{k,b+1} = ∏_{j=a}^{b} E_{j} ∏_{k=0}^{c} K_{k,a} ∏_{n=a}^{b} N_{c+1,n}

⇔ ∫_{a}^{b+1} f(t) dt + ∑_{k=0}^{c} \frac{(−)^{k+1}}{(k + 1)!}B_{k+1}f^{(k)}(b + 1)

= ∑_{n=a}^{b} f(n + 1) + ∑_{k=0}^{c} \frac{(−)^{k+1}}{(k + 1)!}B_{k+1}f^{(k)}(a) + \frac{(−)^{c+1}}{(c + 1)!} ∑_{n=a}^{b} ∫_{0}^{1} f^{(c+1)}(t + n)B_{c+1}(t) dt