A note on recurrences

1. A note on recurrences

Algebraic rearrangements are invariably dull to perform. In addition, they require permanent attention if we want to avoid any error that would render the final result useless. Occasionally, one encounters in such calculations a small problem which may be worth a few moments’ thought.

Thus, in the lengthy attempt to evaluate parities for observed counts, when the original Poisson process has been distorted by an extendable dead time, a problem was met which involves summing over alternate moments, defined [1] by

$m_{r}^{\pm} = \sum_{k = 0}^{\infty} {(- 1)}^{k} k^{r} p_{k} .$ (1)

If the probabilities $p_{k}$ follow the Poisson law (with mean value $μ$ ), the moment of order $r \geq 1$ is known [1] to be

$m_{r}^{\pm} = e^{- 2 μ} \sum_{j = 1}^{r} S (r, j) {(- μ)}^{j},$ (2)

where $S$ is a Stirling number of the second kind [2].

In the problem encountered, the expression to be evaluated is of the form

$F = \sum_{j = 0}^{r - 1} (\begin{matrix} r - 1 \\ j \end{matrix}) m_{j + 1}^{\pm},$

which can be rearranged to become

$F = e^{- 2 μ} \sum_{k = 1}^{j + 1} {(- μ)}^{k} T (r, k),$

where

$T (r, k) = \sum_{j = 0}^{r - 1} (\begin{matrix} r - 1 \\ j \end{matrix}) S (j + 1, k)$ (3)

is now the quantity in which we are interested.

Consider, for the sake of curiosity, both the binomial coefficients and the Stirling numbers as triangular matrices of infinite order. In a simplified notation, these are

$\underline{B} = [\begin{matrix} 1 \\ 1 & 1 \\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1 \\ \dots \end{matrix}]$

$r = 4$

and

$\underline{S} = [\begin{matrix} 1 \\ 1 & 1 \\ 1 & 3 & 1 \\ 1 & 7 & 6 & 1 \\ 1 & 15 & 25 & 10 & 1 \\ \dots \end{matrix}],$

$k = 2$

where we have put $(\begin{matrix} 0 \\ 0 \end{matrix}) = 1$ and omitted the Stirling numbers $S (j, 0)$ as they are not needed in Equation (3).

If we choose, for example. the values $r = 4$ and $k = 2$ , the evaluation of $T (4, 2)$ , according to Equation (3), involves pairwise multiplication of the terms within rectangles in the above matrices. It is readily seen that this corresponds to a matrix multiplication; hence we can write symbolically

$\underline{T} = \underline{B} \times \underline{S},$ (4)

where $\underline{T}$ is now also a matrix.

If we evaluate, for a few arguments, the numerical values of $T (r, k)$ , we find the coefficients assembled in Table 1.

Table 1. Some numerical values of $T (r, k)$ .

	$k = 1$	2	3	4	5	6
$r = l$	1
2	2	1
3	4	5	1
4	8	19	9	1
5	16	65	55	14	1
6	32	211	285	125	20	1

A closer inspection of Table 1 reveals that its values follow a simple recurrence relation¹, namely

$T (r, k) = (k + l) T (r - l, k) + T (r - l, k - l) .$ (5)

This reminds us of the fact that there exist similar recurrences for the binomial coefficients and for the Stirling numbers. These are known to be

$B (n, k) = B (n - l, k) + B (n - l, k - l)$

and

$S (n, k) = k S (n - l, k) + S (n - l, k - l),$ (6)

respectively.

A comparison with Equation (5) and Equation (4) immediately raises the question whether the “transfer’ of recurrences is a general feature of matrix multiplication.

To approach this problem, consider a general matrix multiplication $\underline{A} \times \underline{B} = \underline{C}$ and start with the assumed recurrences

$A_{i, j} = α_{1} A_{i - 1, j} + α_{2} A_{i - 1, j - 1},$

$B_{j, k} = β_{1} B_{j - 1, k} + β_{2} B_{j - 1, k - 1} .$ (7)

This gives for the element $C_{i, k}$ of the product matrix

$C_{i, k} = \sum_{j} A_{i, j} B_{j, k}$

$= \sum_{j} (α_{1} A_{i - 1, j} + α_{2} A_{i - 1, j - 1}) (β_{1} B_{j - 1, k} + β_{2} B_{j - 1, k - 1})$

$= \sum α_{1} A_{i - 1, j} (β_{1} B_{j - 1, k} + β_{2} B_{j - 1, k - 1}) + \sum α_{2} A_{i - 1, j - 1} β_{1} B_{j - 1, k} + \sum α_{2} A_{i - 1, j - 1} β_{2} B_{j - 1, k - 1}$

$= \sum α_{1} A_{i - 1, j} B_{j, k} + α_{2} β_{1} C_{i - 1, k} + α_{2} β_{2} C_{i - 1, k - 1}$

$= α_{1} C_{i - 1, k} + α_{2} β_{1} C_{i - 1, k} + α_{2} β_{2} C_{i - 1, k - 1}$

$= (α_{1} + α_{2} β_{1}) C_{i - 1, k} + α_{2} β_{2} C_{i - 1, k - 1}$ (8)

As expected, we return to the situation given in Equation (5) by putting $α_{1} = α_{2} = 1, β_{1} = k$ and $β_{2} = 1$ .

It is interesting to note in Equation (8) that the coefficients $γ$ , for the product element

$C_{i, k} = γ_{1} C_{i - 1, k} + γ_{2} C_{i - 1, k - 1},$ (9)

involve not only sums, but also products of the coefficients $α$ and $β$ . The coefficients $γ$ are thus not symmetric in $α$ and $β$ .

It may therefore be worthwhile also to consider triple recurrences, i.e. relations of the form

$A_{i, j} = α_{1} A_{i - 1, j} + α_{2} A_{i - 1, j - 1} + α_{3} A_{i - 1, j - 2},$

$B_{j, k} = β_{1} B_{j - 1, k} + β_{2} B_{j - 1, k - 1} + β_{3} B_{j - 1, k - 2} .$ (10)

After a similar, although longer calculation, we can show that the form of the product element $C_{i, k}$ is

$C_{i, k} = [α_{1} + β_{1} (α_{2} + α_{3} β_{1})] C_{i - 1, k} + β_{2} (α_{2} + 2 α_{3} β_{1}) C_{i - 1, k - 1}$

$+ [β_{3} (α_{2} + 2 α_{3} β_{1}) + α_{3} β_{2}^{2}] C_{i - 1, k - 2} + 2 α_{3} β_{2} β_{3} C_{i - 1, k - 3} + α_{3} β_{3}^{2} C_{i - 1, k - 4} .$ (11)

Obviously, for $α_{3} = β_{3} = 0$ this reduces to Equation (8).

It is worth noting that not only the new coefficients $γ$ , introduced in Equation (9), become more complicated, but also that their number no longer agrees with those of $α$ and $β$ .

I have just been informed by Mme M. Boutillon, a colleague at the BIPM, that the following general rule holds: If the recurrence formulae for both $A$ and $B$ have $m$ terms (in $α$ and $β$ ), the recurrence for $C$ includes ${(m - 1)}^{2} + 1$ terms ( $γ$ ).

This nice result explains why we find five terms in the product of triple recursions $(m = 3)$ . In addition, it shows that only in the case of a double recursion $(m = 2)$ — the case $m = 1$ is of no interest — the elements of the product matrix have the same number of terms in the recurrence.

References

[1] J.W. Müller: “Alternate moments and parity moments”, Rapport bipm92-5 (1992)

[2] J. Riordan: “An Introduction to Combinatorial Analysis” (Wiley, New York, 1958)

[3] J.W. Müller: “Shifted developments of power functions”, Rapport bipm92-9 (1992)

¹Note that the quantities $T (r, k)$ are identical with coefficients that have been listed before in another context [3], and which were then denoted by $β_{j} (r, 2)$ . The correspondence is $β_{j} (r, 2) = T (r + 1, j + 1)$ . In fact, it now turns out that all the coefficients evaluated in [3] allow simple recurrences, namely (in the original notation) $α_{j} (r, t) = t α_{j} (r - 1, t) + α_{j - 1} (r - 1, t)$ and $β_{j} (r, t) = (j + t) β_{j} (r - 1, t) + β_{j - 1} (r - 1, t)$ , a property which has not been recognized previously. These relations also provide a convenient means for checking the numerical values.

↩